СПбГУ 2025, 8–9 классы, задача 8

Сложная

Источник:

Олимпиады школьников СПбГУ, Отборочный этап, 2025, 8–9 классы

( баллов) По кругу стоят человечков, каждый из которых или зелёный, или красный. Каждый красный человечек всегда говорит правду, а каждый зелёный человечек врёт. Назовём двух человечков, между которыми стоят не более двух человечков, близкими; т. е. у каждого человечка ровно близких. Каждый человечек заявил: «Среди моих близких хотя бы зелёных человечка». Какое наибольшее количество зелёных человечков может быть?

Ответ

Ответ: .

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

Пример расположения человечков, на котором достигается полученная оценка:

З-З-К-К-К-З-З-К-К-К-З-З-К-К-К-З-З-К-К-К

Верное решение

Максимум: 40

Похожие задачи

СПбГУ 2026, 10-11 классы, задача 8

(40 баллов) В ячейках таблицы 19 × 19 расставлены натуральные числа. Оказалось, что сумма чисел в любых двух соседних по стороне ячейках равна 29 или 30. Посчитаем сумму чисел в каждой строке и каждом столбце. Могут ли все эти 38 сумм быть попарно различны?

Сложная

Теория чисел

Комбинаторика

СПбГУ 2025, 8–9 классы, задача 9

(40 баллов) В вершинах правильного 100-угольника расположены целые числа, сумма которых равна 2025. Два игрока по очереди берут себе по одному числу. Первый игрок начинает, выбирая любое число. Со второго хода разрешается брать числа только из вершин, соседних с теми, откуда уже были взяты числа. По

Сложная

Комбинаторика

СПбГУ 2024, 10–11 классы, задача 6

(40 баллов) На доске написаны числа 1, 2, 3,..., 2023. Раз в минуту к доске подбегает Жора. Он выбирает некоторое натуральное число k, но не обязательно написанное на доске. После этого каждое число на доске, не меньшее k, уменьшает на k. После нескольких операций на доске осталось ровно одно ненуле

Сложная

Комбинаторика

СПбГУ 2025, 10–11 классы, задача 13

(40 баллов) Несколько экспертов оценивают 5 фильмов оценками от 0 до 10. Известно, что для любых двух экспертов найдётся хотя бы два фильма, за каждый из которых эксперты поставили разные оценки. Какое наибольшее число экспертов может быть?

Сложная

Комбинаторика