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

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

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

Ответ :не может.

Рассмотрим некоторые случаи. Пусть строй начинается с девочки. Вторым человеком может быть или мальчик или девочка. Если это девочка, то третий обязательно мальчики, в противном случае условие не выполняется. Четвертый - мальчик по той же причине. Так как мальчиков на 2 меньше, то пятым будет девочка. Таким образом они чередуются,но в таком случае девочек и мальчиков поровну, что противоречит условию.

Если второй после направляющей девочки стоит мальчик, то получим тоже самое, но со сдвигом на 1 человека. В таком строю два человека перед последним будут девочки. Чтобы выполнить условие, нужно,чтобы девочек было 31, но в таком случае не выполняется условие в конце строя(3 девочки подряд ). Если же строй начинается с мальчиков,то достигнуть условия не удастся тоже.

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

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