Задача М893 / Задачи // Архив журнала «Квант»

Условие задачи (1984, № 11) Задача М893 // Квант. — 1984. — № 11. — Стр. 35; 1985. — № 3. — Стр. 29.

Каждые два из $n$‍‍ блоков ЭВМ соединены проводом. Можно ли каждый их этих проводов покрасить в один из $n-1$‍‍ цветов так, чтобы от каждого блока отходило $n-1$‍‍ проводов разного цвета, если

$n=6$‍;‍
$n=13$‍?‍

В. Б. Алексеев

Московская математическая олимпиада (1984 год)

Открыть в номере

Изображения страниц

‍

Скачать PDF

Решение задачи (1985, № 3) Задача М893 // Квант. — 1984. — № 11. — Стр. 35; 1985. — № 3. — Стр. 29.

a) Ответ: можно. Нужная раскраска показана на рисунке.

б) Ответ: нельзя. Действительно, если было использовано $m$‍‍ проводов какого-то одного цвета, то число блоков — $2m$‍‍ (столько концов у всех этих проводов, а каждый конец подсоединён ровно к одному блоку). Но 13 — нечётное число.

Рисунок

Эту задачу часто формулируют как задачу о составлении расписания кругового турнира: — при этом проводам одного цвета отвечает разбиение участников турнира на пары для одного тура. Мы видели, что при нечётных $n$‍‍ эта задача неразрешима. Можно доказать, что при чётных $n$‍‍ она всегда имеет решение (см., например, книгу О. Оре «Приглашение в теорию чисел» (М.: Наука, 1980, гл. 8, § 3), а также решение задачи 1.16 в книге «Заочные математические олимпиады» (М.: Наука, 1981, с. 19)).

В. Б. Алексеев

Открыть в номере

Метаданные Задача М893 // Квант. — 1984. — № 11. — Стр. 35; 1985. — № 3. — Стр. 29.

Предмет

Математика

Условие

Алексеев В. Б.

Решение

Алексеев В. Б.

Номера

1984. — № 11. — Стр. 35 [условие]

1985. — № 3. — Стр. 29 [решение]

Описание

Задача М893 // Квант. — 1984. — № 11. — Стр. 35; 1985. — № 3. — Стр. 29.

Ссылка

https://www.kvant.digital/problems/m893/