Question

На карусели расположены по кругу. Когда пришёл Рома покататься на карусели, на некоторых сиденьях уже сидели девочки. Оказалось, что он не может сесть так, чтобы на соседнем сиденье не было девочек. Какое минимальное число девочек могло быть?

Answer 1

Так как в комментариях к задаче есть пояснение, что на карусели 30 мест, то решаю задачу для n = 10.

Пусть на карусели было 3n мест, докажем, что на карусели хотя бы n девочек:

Оценка:

Разобьём карусель на n "групп" по 3 подряд стоящих сидения. Если в какой либо "группе" сидений на сиденьях не сидит ни одна девочка, то Рома может сесть на среднее сидение, так как тогда с ним рядом точно не будет сидеть девочка. Значит, девочек не меньше n.

Пример:

Разобьём карусель на n "групп" по 3 подряд стоящих сидения. Пусть в каждой "группе" на среднем сидении сидит девочка. Тогда девочек n, а Рома не сможет сесть, не сев рядом с девочкой, так как он садится в одну из "групп", а тогда он садится на соседнее с девочкой место.

30 : 3 = 10

Ответ: 10 девочек.

Answer 2

Предположим, что на карусели всего N сидений. Когда Рома пришел, некоторые из сидений были уже заняты девочками. Чтобы он не сел на сиденье с девочкой, рядом с которым тоже сидит девочка, нужно, чтобы девочки занимали сиденья чередующимися группами по одной и две девочки.

Теперь мы можем рассмотреть случаи, когда на карусели от 3 до 7 сидений, чтобы найти минимальное число девочек.

1. При 3 сиденьях: Минимальное число девочек = 2 (Мальчик-Девочка-Мальчик).
2. При 4 сиденьях: Минимальное число девочек = 3 (Мальчик-Девочка-Мальчик-Девочка).
3. При 5 сиденьях: Минимальное число девочек = 4 (Мальчик-Девочка-Мальчик-Девочка-Мальчик).
4. При 6 сиденьях: Минимальное число девочек = 4 (Мальчик-Девочка-Мальчик-Девочка-Мальчик-Девочка).
5. При 7 сиденьях: Минимальное число девочек = 5 (Мальчик-Девочка-Мальчик-Девочка-Мальчик-Девочка-Мальчик).

Таким образом, минимальное число девочек, которое могло быть на карусели, составляет 2, 3, 4, 4 или 5, в зависимости от числа сидений на карусели (от 3 до 7 сидений).