Районная олимпиада, 2010-2011 учебный год, 9 класс

Учитель физкультуры хочет выстроить в шеренгу (линию) 60 школьников – 29 мальчиков и 31 девочку так, чтобы ни один из школьников (девочка или мальчик) не стоял между двумя девочками. Удастся ли ему это?

Комментарий/решение

Допустим, что удастся. Пронумеруем места, где стоят школьники как $1,2,3,......,60$. Достаточно доказать, что найдутся $2$ девочки стоящие на $n$ и $n+2$ местах, и выйдет противоречие. Разделим места на пары как $1$ и $3$ ; $2$ и $4$...$58$ и $60$

Заметим, что пар у нас $30$, а девочек $31$. По принципу Дирихле найдется пара из двух девочек, что и требовалось доказать. Ответ:нет