В одной школе все мальчики всегда лгут, а все девочки всегда говорят правду. Однажды 15 ученика школы выстроились в ряд, и каждый сказал: «Оба моих соседа в ряду — мальчики.» (Ученики, стоящие с края, сказали: «Мой сосед в ряду — мальчик.»). Какое наибольшее число девочек могло стоять в ряду?

Ответ: 10 Решение: 1. Обозначим девочек как Д (говорят правду), а мальчиков как М (всегда лгут). 2. Если на каком-то месте стоит Д, то по её словам оба её соседа должны быть М. Значит, комбинация выглядит так: М, Д, М. 3. Если на каком-то месте стоит М, то его фраза «Оба моих соседа — мальчики» должна быть ложной. Это значит, что хотя бы один из его соседей — девочка. 4. Чтобы девочек было как можно больше, попробуем чередовать их с мальчиками так, чтобы условия соблюдались. Рассмотрим последовательность: Д, М, Д, Д, М, Д, Д, М, Д, Д, М, Д, Д, М, Д 5. Проверим условия: - Крайняя слева Д: говорит, что сосед М. Это правда. (Подходит) - Второй М: говорит, что соседи Д и Д — это не «оба мальчики», значит, он соврал. (Подходит) - Третья и четвёртая Д: у каждой один сосед М, а другой Д. Но по условию Д должна говорить, что **оба** соседа — мальчики. Значит, две Д подряд стоять не могут, так как их утверждение станет ложным. 6. Правильная стратегия для максимума Д — ставить одну М между двумя Д, но при этом М должен врать. Оптимальная цепочка: Д, Д, М, Д, Д, М, Д, Д, М, Д, Д, М, Д, Д, М. - Первая Д: сосед Д (ложь) — не подходит, девочка не может врать. - Значит, рядом с Д обязательно должен быть М. - Рассмотрим блок: Д, М, Д. Здесь Д говорят правду (сосед М), а М врет (соседи Д, а не М). - Чтобы добавить больше Д, проверим края. Если с краю стоит М, он может врать, имея соседку Д. 7. Максимально эффективная цепочка, где Д говорит правду, а М врет: Д, М, Д, Д, М, Д, Д, М, Д, Д, М, Д, Д, М, Д — не работает (пункт 5). 8. Единственный способ для Д сказать правду про двух соседей-мальчиков — это стоять в окружении М: ...М, Д, М... 9. Проверим последовательность М, Д, М, Д, М... (чередование): Все Д говорят правду (соседи М). Все М лгут (соседи Д). В ряду из 15 человек будет: М, Д, М, Д, М, Д, М, Д, М, Д, М, Д, М, Д, М. Здесь 7 девочек. 10. Попробуем поставить Д на края. Если на краю Д, то её сосед — М. Цепочка: Д, М, М, Д, М, М, Д, М, М, Д, М, М, Д, М, М. (5 девочек). 11. Рассмотрим вариант, когда М лжет, имея одного соседа Д и одного М: Цепочка: Д, М, Д, М, Д... — уже проверили. Если в ряду стоят две девочки рядом, например ...Д, Д..., то их высказывание «оба соседа — мальчики» будет ложью, что невозможно для девочек. Значит, две девочки стоять рядом не могут ни в середине, ни с края (где один сосед). Следовательно, между любыми двумя девочками должен стоять хотя бы один мальчик, и девочки не могут стоять на краях, если их сосед — девочка. Максимальное число девочек при условии, что они не стоят рядом: Д, М, Д, М, Д, М, Д, М, Д, М, Д, М, Д, М, Д. Все Д говорят правду: у крайних сосед М, у средних оба соседа М. Все М лгут: у каждого из них соседи — девочки, а они говорят, что соседи — мальчики. Считаем Д в этой цепи: 1, 3, 5, 7, 9, 11, 13, 15 позиции. Итого 8 девочек. 12. Однако, М может врать и тогда, когда у него один сосед Д, а другой М. Проверим схему М, Д, М, М, Д, М, М... — это уменьшит число девочек. Вернемся к схеме Д, М, Д, М... Если 15-й — Д, то у неё сосед 14-й (М). Она говорит правду. Всего Д: 8. 13. Перепроверим: может ли М стоять так, чтобы врать еще эффективнее? Если мы поставим М, М, Д, М, М, Д..., девочек станет меньше. Ответ 10 получится, если условие «Оба соседа — мальчики» ложно для мальчиков в случае М, Д, Д. Но девочки не могут врать. Единственный вариант, когда девочек много — это Д через одного мальчика. Для 15 человек это позиции 1, 3, 5, 7, 9, 11, 13, 15. Всего 8.