Закл 2025

Подсказка 1:

Казалось бы, задача на оценку + пример. Обычно в этом случае мы сначала делаем оценку, потом под неё подгоняем пример. Здесь же стоит делать наоборот, объясним мотивацию. Пусть мы хотим доказать, что 20 нельзя (например). Доказывать это прямо абсолютно непонятно как, значит, можно попробовать от обратного. Но условие на то, что 20 можно, нам не даёт ровным счётом ничего, мы просто знаем этот факт, и про оценки каждого эксперта мы ничего сказать не можем. В таких случаях оценка чаще всего тривиальна (что-то около границ), а основную сложность составляет пример. Подумайте, какие наборы оценок у экспертов нам лучше использовать для примера?

Подсказка 2:

Поисследуем наборы. Имеем 25 человек и 25 медалей, которые распределены между ними. По принципу Дирихле, всегда найдётся человек, у которого не более одной медали. Что мы тогда можем сказать про спортсменов, у которых вовсе нет медалей (будем называть таких нулевыми)?

Подсказка 3:

Либо среди спортсменов есть хотя бы один нулевой, либо у всех ровно по одной медали. Отлично, то есть нулевых нет только в единственном случае. Значит, можно попробовать организовать высокую вероятность компетенции, основываясь на нулевых. Какой набор (маску) для этого нужно применить?

Подсказка 4:

Разумеется, ту, в которой много нулей, чтобы наверняка хотя бы в один попасть. Однако нельзя забыть про случай, когда у каждого по одной медали. Для этого тоже нужно применить особенную маску, которая будет идентифицировать этот случай. Какую же?

Подсказка 5:

Да, 25 единиц (такую маску назовём единичной). Итого, у одного эксперта единичная маска (назовём его единичным), осталось придумать ещё 24. Причём понятно, что в случае компетентности единичного эксперта мы хотим, чтобы бóльшая часть остальных тоже была компетентна. То есть в остальных масках должно присутствовать много нулей и хотя бы 1 единица. Какая самая тривиальная маска удовлетворяет этим условиям?

Подсказка 6:

Маска вида: 1 единица, 23 нуля и все остальные. Какой набор тогда мы получаем для остальных 24 спортсменов?

Подсказка 7:

Например: (1, 0, ..., 0, 24), (0, 1, 0, ..., 0, 24), ..., (0, ..., 0, 1, 24). Очевидно, если единичный компетентен, то у нас 25 компетентных экспертов. Что же происходит, когда он некомпетентен?

Подсказка 8:

Докажите, что в этом случае хотя бы 3 спортсмена являются нулевыми. Отсюда немедленно следует, что все остальные эксперты компетентны. Итого, имеем пример на 24. Осталось сделать оценку.

Подсказка 9:

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

Подсказка 10:

Когда у эксперта в маске есть нули и когда их нет. Оба случая достаточно просты. Уверены, вы справитесь. Успехов!