1) 16 девятиклассников рассадили на стулья, расположенные в квадрате 4×4. Каждый девятиклассник заявил, что все его соседи — девочки. Известно, что дети одного пола все сказали правду, а дети другого пола могли сказать как правду, так и ложь. Докажите, что девочек не могло быть ровно 7.

Предположим, что девочек ровно 7. Девочки говорят правду, поэтому у каждой девочки все соседние с ней ученики — тоже девочки.

Рассмотрим граф: его вершины — 16 мест, а ребро соединяет соседние места. Этот граф связен: из любого места можно попасть в любое другое, переходя между соседними местами по рядам и столбцам. Значит, если одна вершина принадлежит множеству девочек, то все вершины, достижимые по рёбрам, тоже принадлежат ему. Следовательно, девочками должны быть все 16 учеников — противоречие с предположением, что их 7.

Ответ: девочек не могло быть ровно 7.