РЕШУ ОЛИМП: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 0 № 1879 Добавить в вариант

В экзамене 25 тем, по каждой из которых заготовлено 8 вопросов. В билет входят 4 вопроса по разным темам. Можно ли заготовить 50 билетов так, чтобы каждый вопрос встречался в них ровно один раз и для любых двух тем был билет, в котором есть вопросы по ним обеим?

Спрятать решение

Решение.

Отождествим темы и пары остатков $левая круглая скобка x, y правая круглая скобка$ по модулю 5. Каждый билет будем пони- мать как четвёрку тем, тогда требуется предъявить 50 четвёрок так, что каждая тема находится ровно в 8 четвёрках и каждая пара тем  — ровно в одной четвёрке. Работая с парами остатков по модулю 5, мы можем складывать (покоординатно по модулю 5). Рассмотрим 25 сдвигов четвёрки

$A= левая фигурная скобка левая круглая скобка 0, 0 правая круглая скобка , левая круглая скобка 0, 1 правая круглая скобка , левая круглая скобка 1, 0 правая круглая скобка , левая круглая скобка 2, 2 правая круглая скобка правая фигурная скобка ,$

т. е. все четвёрки вида

$левая фигурная скобка левая круглая скобка x, y правая круглая скобка , левая круглая скобка x, y плюс 1 правая круглая скобка , левая круглая скобка x плюс 1, y правая круглая скобка , левая круглая скобка x плюс 2, y плюс 2 правая круглая скобка правая фигурная скобка . \quad левая круглая скобка * правая круглая скобка$

и 25 сдвигов удвоенной четвёрки

$2 A= левая фигурная скобка левая круглая скобка 0, 0 правая круглая скобка , левая круглая скобка 0, 2 правая круглая скобка , левая круглая скобка 2, 0 правая круглая скобка , левая круглая скобка 4, 4 правая круглая скобка правая фигурная скобка : левая фигурная скобка левая круглая скобка x, y правая круглая скобка , левая круглая скобка x, y плюс 2 правая круглая скобка , левая круглая скобка x плюс 2, y правая круглая скобка , левая круглая скобка x плюс 4, y плюс 4 правая круглая скобка правая фигурная скобка . \quad левая круглая скобка ** правая круглая скобка$ $2 A= левая фигурная скобка левая круглая скобка 0, 0 правая круглая скобка , левая круглая скобка 0, 2 правая круглая скобка , левая круглая скобка 2, 0 правая круглая скобка , левая круглая скобка 4, 4 правая круглая скобка правая фигурная скобка : левая фигурная скобка левая круглая скобка x, y правая круглая скобка , левая круглая скобка x, y плюс 2 правая круглая скобка , левая круглая скобка x плюс 2, y правая круглая скобка , левая круглая скобка x плюс 4, y плюс 4 правая круглая скобка правая фигурная скобка . \quad$
$\quad левая круглая скобка ** правая круглая скобка$

Каждая тема $левая круглая скобка u, v правая круглая скобка$ содержится ровно в 8 четвёрках, поскольку она единственным образом представима в каждом из видов (*) или (**). Докажем, что любые две различные темы $левая круглая скобка a, b правая круглая скобка , левая круглая скобка u, v правая круглая скобка$ содержатся вместе ровно в одной четвёрке. Для этого надо установить, что их разность $левая круглая скобка u минус a, v минус b правая круглая скобка$ представима единственным образом либо как разность двух тем из A, либо как разность двух тем из $2A.$ Несложно про- верить, что эти 24 разности  — 12 разностей для A и 12 разностей для $2A$   — по разу покрывают все пары остатков, кроме (0, 0).

Ответ: можно.

Санкт-Петербургская олимпиада школьников, 10 класс, 2 тур (заключительный), 2020 год

Классификатор: Разное. Да или нет?, Разное. Логические задачи

Спрятать решение · Помощь