Олимпиадные задачи из источника «38 турнир (2016/2017 год)» для 1-10 класса - сложность 4 с решениями

В Чикаго живут 36 гангстеров, некоторые из которых враждуют между собой. Каждый гангстер состоит в нескольких бандах, причём нет двух банд с совпадающим составом. Оказалось, что гангстеры, состоящие в одной банде, не враждуют, но если гангстер не состоит в какой-то банде, то он враждует хотя бы с одним её участником. Какое наибольшее число банд могло быть в Чикаго?

На прямой сидит конечное число лягушек в различных целых точках. За ход ровно одна лягушка прыгает на 1 вправо, причём они по-прежнему должны быть в различных точках. Мы вычислили, сколькими способами лягушки могут сделать <i>n</i> ходов (для некоторого начального расположения лягушек). Докажите, что если бы мы разрешили тем же лягушкам прыгать влево, запретив прыгать вправо, то способов сделать <i>n</i> ходов было бы столько же.