Задача 67589
|
|
 |
Условие
По кругу стоят 30 мальчиков и 30 девочек. Докажите, что можно выбрать 10 мальчиков и 10 девочек так, чтобы никакие двое из выбранных не стояли рядом.Решение 1
Выберем произвольно первого ребенка. Двигаясь от него по часовой стрелке, будем выбирать каждого второго и объявлять негодными пропущенных, пока не наберётся 10 детей одного пола. Пусть в этот момент выбрано, например, 10 мальчиков и $k < 10$ девочек. Объявим негодным следующего по кругу. Остались не рассмотренными не менее $30 - k - (10 + k) = 20 - 2k$ девочек. Выберем $10 - k$ (не более половины) из следующих девочек, начиная с первой из них и беря их через одну, не обращая внимания на мальчиков.Решение 2
Будем доказывать индукцией по $n$, что среди $3n$ мальчиков и $3n$ девочек, стоящих по кругу, можно выбрать $n$ мальчиков и $n$ девочек, среди которых никто не стоит рядом друг с другом. База $n=1$ очевидна.Пусть утверждение доказано для $n-1$, докажем его для $n$. Рассмотрим все возможные шестёрки подряд стоящих детей. Заметим, что не может во всех шестёрках быть больше мальчиков (так как, просуммировав по всем шестёркам, получили бы, что и всего мальчиков больше). Аналогично не может во всех шестёрках быть больше девочек. Поэтому найдётся шестёрка, где девочек не меньше половины, и аналогично найдётся шестёрка, где мальчиков не меньше половины. Двигаясь от первой из них ко второй по кругу, мы найдём шестёрку, где ровно 3 мальчика и 3 девочки. Заметим, что среди оставшихся детей (вне выбранной шестёрки) можно найти $n-1$ мальчиков и $n-1$ девочек, не стоящих рядом (по предположению индукции), выберем их.
Теперь рассмотрим в выделенной шестёрке четверых детей, не стоящих с краю. Среди них найдутся два ребёнка разного пола, не стоящие рядом (возьмём двух крайних детей, а если они одного пола, то среди двух детей, стоящих посередине, возьмём ребёнка другого пола и добавим к нему крайнего ребёнка, не стоящего рядом). Добавим этих двоих детей к уже выбранным, получим искомое.
Решение 3
Занумеруем детей по часовой стрелке числами 1, 2, 3, …, 60 и разделим на три группы: первая — номера которых имеют остаток 1 от деления на 3, вторая — номера которых имеют остаток 2 от деления на 3, третья — номера которых делятся на 3. В каждой группе 20 человек, и если хотя бы в одной группе мальчиков и девочек поровну, то задача решена — надо просто выбрать эту группу. Иначе найдутся две «соседние» группы, в одной из которых больше мальчиков, а в другой — больше девочек. Пусть это первая и вторая группы. Будем постепенно заменять в первой группе людей одного за другим на людей из второй группы: №1 на №2, потом №4 на №5, потом №7 на №8, и т. д. При каждой замене число мальчиков в изменяемой первой группе меняется не более чем на 1. Так как изначально их было больше половины, а после полной замены исходной первой группы на вторую мальчиков станет меньше половины, в какой-то промежуточный момент мы получим искомую группу, в которой мальчиков и девочек поровну.Решение 4
Докажем, что можно выбрать даже 14 девочек и 14 мальчиков. Шаблоном назовем 28 мест «через 1», то есть набор мест вида $m$, $m+2$, $m+4$, …, $m+54$. Шаблон назовём «Д», если в нём больше девочек, и «М» — если в нём больше мальчиков.Если нет шаблона, в котором мальчиков и девочек поровну, то должны существовать и «М»-шаблон, и «Д»-шаблон (иначе, суммируя (усредняя) по всем шаблонам, получили бы, что всего в круге больше мальчиков или больше девочек). Тогда найдутся два «соседних» шаблона разного типа — скажем, «М»-шаблон $n$, $n+2$, $n+4$, …, $n+54$ и «Д»-шаблон $n+1$, $n+3$, $n+5$, …, $n+55$. Далее двигаемся от одного шаблона к другому, каждым ходом заменяя одного человека среди текущих 28: а именно, сначала сдвинем $n+54$ в $n+55$, затем $n+52$ в $n+53$ и т. д. В промежутках у нас будут получаться уже не шаблоны, но по-прежнему 28 человек, не стоящие рядом. После каждого хода число девочек в выбранных 28 ребятах изменяется не более чем на 1. Значит, в какой-то момент мы получим набор из 28 человек, в котором мальчиков и девочек поровну (так как изначально было больше мальчиков, а в конце больше девочек).
