Число путей

Три посёлка A, B и C связаны просёлочными дорогами, при этом любые два посёлка связывают несколько (больше одной) дорог. Движение на дорогах двустороннее. Назовём путём из одного посёлка в другой либо связывающую их дорогу, либо цепочку из двух дорог, проходящую через третий посёлок. Известно, что посёлки A и B связывают 34 пути, посёлки B и C — 29 путей. Какое наибольшее число путей может связывать посёлки A и C?

Пускай кол-во дорог А до B это x (максимум 34 может быть), A до C это y, B до С это z(максимум 29 может быть). Если между A и С добавляется одна дорога, то это уменьшает x и z как минимум на 1, тогда кол-во путей от A до С, равное до этого y + xz станет не больше, чем y+1 + (x-1)(z-1) = y + xz -x-z+2. В случае если сумма x и z больше 2-х это уменьшает кол-во путей между A и С. Рассмотрим случай когда их сумма не больше 2-х. x=1, z=1. Тогда y =28 и y =33 для того чтобы удовлетворить условию, чего быть не может. Следовательно это не так. Тогда добваление дороги между A и С уменьшает количество путей между ними. Тогда максимум будет при отсутвии дорог между A и C, тогда максимум будет ) 0 + 29*34 = 986. Вроде так. Эту задаче можно было также решить составлением уравнений для кол-ва путей между A и B x +yz = 34, B и С z + xy = 29, их вычитанием, вынесением за скобки (x-z) и решением в целых числах. Там очень ограниченное число решений, поэтому это тоже достаточно быстро.

У Гриши есть несколько карточек, хотя бы 3. На каждой написано целое число (числа не обязательно различны). Оказалось, что если выбрать любые три карточки, то сумма записанных на них чисел также записана на одной из карточек (не обязательно на одной из этих трёх). Какое количество ненулевых чисел может быть записано на карточках?

Дан квадрат 11×11, в каждой клетке которого нарисован либо «0», либо «х». За один ход можно поменять «0» на «х» и наоборот в кресте (крест − объединение произвольного столбца и произвольной строки). Можно ли из любого начального расположения получить квадрат со всеми «0»?

За круглым столом сидели 99 человек, все разного роста. Каждый честно ответил на два вопроса:
1. «Вы выше, чем ваш сосед справа?»
2. «Вы выше, чем оба ваших соседа — справа и слева?».
Какое наибольшее количество ответов «Да» могло быть дано?

На острове дружно живут 20 аборигенов, каждый из них либо рыцарь, либо лжец. Каждый абориген сказал: «Среди всех моих соседей по острову ровно 6 несовершеннолетних». Сколько лжецов может быть на острове? В ответ запишите сумму всех возможных вариантов ответа.