Question

На одной стороне улицы разбитых фонарей стояло 150 фонарей, причём среди любых трёх фонарей, стоящих подряд, хотя бы один был разбит. После того, как электрик Киров починил несколько фонарей, среди любых четырёх фонарей, стоящих подряд, осталось не более одного разбитого. Докажите, что электрик починил не менее 25 фонарей. Задали олимпиадой задание домой для 6 класса.Помогите, пожалуйста!

Answer 1

Разобьём фонари на 25 шестёрок подряд стоящих, и докажем, что в каждой из них был починеный фонарь.

Предположим, что в какой-то шестёрке ни один фонарь не был починен.

В такой шестёрке не менее двух разбитых фонарей (поскольку в каждой из двух троек, составляющих шестёрку, был разбитый фонарь), между которыми не менее трёх работающих фонарей (так как иначе можно будет указать четыре фонаря, среди которых хотя бы два разбитых).

Но как раз трёх работающих фонарей подряд стоять и не может.

Answer 2

Давайте рассмотрим оба состояния улицы: до ремонта Кировым и после него.

Пусть в исходном состоянии улицы среди 150 фонарей есть k разбитых фонарей. Это значит, что среди любых трёх фонарей, стоящих подряд, хотя бы один разбитый, а значит, в любой группе из трёх фонарей должно быть минимум один разбитый. Таким образом, у нас есть k разбитых фонарей, и любые 3 фонаря из них образуют хотя бы одну такую группу.

После ремонта Кирова ситуация меняется. Теперь в любой группе из четырёх фонарей должен быть не более одного разбитого фонаря. Предположим, что после ремонта было m разбитых фонарей.

Рассмотрим случай, когда m < k. Это означает, что после ремонта количество разбитых фонарей уменьшилось, но все равно остаются ситуации, где в группе из 4 фонарей 2 или более разбитых. Но такие группы уже не могут образовываться, так как у нас осталось только m разбитых фонарей. Это противоречие, и такой ситуации не может быть.

Теперь рассмотрим случай, когда m ≥ k. Это означает, что после ремонта количество разбитых фонарей не уменьшилось или увеличилось, но осталось не более k разбитых фонарей. В таком случае, все предыдущие группы из трёх фонарей, содержащие по крайней мере один разбитый фонарь, останутся существовать после ремонта. Кроме того, появятся новые группы из четырёх фонарей с не более чем одним разбитым.

Мы знаем, что в исходном состоянии улицы существуют группы из трёх фонарей, содержащие хотя бы один разбитый фонарь. После ремонта такие группы останутся. При этом в новом состоянии добавятся ещё группы из четырёх фонарей, с не более чем одним разбитым.

Теперь рассмотрим группы из четырёх фонарей, в которых есть ровно один разбитый. Количество таких групп будет равно m, так как после ремонта у нас осталось m разбитых фонарей. Однако, каждая из этих групп пересекается с двумя группами из трёх фонарей (так как 4 фонаря содержат в себе три).

Таким образом, общее количество групп из трёх и четырёх фонарей не может быть меньше 150 + m (исходное количество фонарей плюс количество разбитых после ремонта). Но у нас изначально было k разбитых фонарей, а после ремонта стало m разбитых. Таким образом, общее количество групп не может быть меньше 150 + k.

Так как мы знаем, что в исходном состоянии улицы существуют группы из трёх фонарей, содержащие хотя бы один разбитый, значит, k ≥ 1. Тогда общее количество групп не может быть меньше 150 + 1 = 151.

Мы доказали, что общее количество групп из трёх и четырёх фонарей не может быть меньше 151. Но каждая такая группа включает в себя 3 фонаря (для групп из трёх) или 4 фонаря (для групп из четырёх). Таким образом, общее количество фонарей не может быть меньше 151 * 3 = 453.

Таким образом, после ремонта Кирова осталось не менее 453 фонаря, включая и исправные, и испорченные. Но у нас изначально было 150 фонарей, значит, Киров починил не менее 453 - 150 = 303 фонаря.

Таким образом, электрик Киров починил не менее 303 фонарей. Ответ: он починил не менее 303 фонарей.