СПбГУ 2025, отборочный этап, 10–11 классы, задача 13

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

Ответ

Ответ: .

Решение. Оценка. Каждый фильм можно оценить -ю способами (от до ). Поэтому всевозможных наборов оценок для первых четырёх фильмов — . Покажем, что количество экспертов не может быть больше этого числа: если бы экспертов было больше, то по принципу Дирихле нашлись бы двое из них, чьи оценки первых четырёх фильмов идентичны; а, значит, могут различаться только оценки пятого фильма. А это противоречит условию о том, что любая пара экспертов отличается в оценках как минимум двух фильмов.

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

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

Максимум: 40

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

СПбГУ 2025, отборочный этап, 10–11 классы, задача 16

(40 баллов) В компании из 734 человек некоторые пары людей враждуют между собой (вражда взаимна). Известно, что у каждого в компании не более 19 врагов. Докажите, что можно разбить всех людей на не более чем 5 групп так, что количество пар врагов, оказавшихся в одной группе, будет не более 1101.

Сложная

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

СПбГУ 2023, отборочный этап, 10–11 классы, задача 10

(40 баллов) На доске написаны 1000 различных натуральных чисел. Оказалось, что для каждого написанного числа a на доске найдется еще хотя бы одно число b такое, что |a-b| — простое число. Докажите, что можно подчеркнуть не более 500 чисел так, чтобы для каждого неподчеркнутого числа a нашлось подчер

Сложная

Теория чисел

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

СПбГУ 2025, отборочный этап, 8–9 классы, задача 8

(40 баллов) По кругу стоят 20 человечков, каждый из которых или зелёный, или красный. Каждый красный человечек всегда говорит правду, а каждый зелёный человечек врёт. Назовём двух человечков, между которыми стоят не более двух человечков, близкими; т. е. у каждого человечка ровно 6 близких. Каждый ч

Сложная

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

СПбГУ 2022, отборочный этап, 10–11 классы, задача 13

(40 баллов) В лагерь приехали 90 школьников. Известно, что среди любых 10 школьников обязательно найдутся два друга. Скажем, что группа школьников образует цепочку дружб, если детей в группе можно занумеровать числами от 1 до k так, что 1-й и 2-й — друзья, 2-й и 3-й — друзья, ldots, (k-1)-й и k-й —

Сложная

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