воскресенье, 27 марта 2016 г.

Шесть чисел в ряд

Задача.

(«Покори Воробьёвы горы!», 2012, 9) 
Сколькими способами можно выписать в ряд числа 1, 2, 3, 4, 5, 6 так, чтобы для любых трёх подряд идущих чисел a, b, c величина ac − b2 была кратна 7?

Решение.
Первый способ.
1) Для ряда чисел 132645 условие задачи:
132        1 * 2 - 3 * 3 = -7
326        3 * 6 - 2 * 2 = 14
264        2 * 4 - 6 * 6 = -28
645        6 * 5 - 4 * 4 = 14
451        4 * 1 - 5 * 5 = -21
513        5 * 3 - 1 * 1 = 14
Очевидно, что для рядов, полученных перемещением первого числа ряда на последнее место, условие задачи также выполняется:  326451, 264513, 645132, 451326, 513264.
Всего получилось 6 вариантов.
2) При перестановках в тройках вида "132 меняется на 231" условие "ac − b2 кратно 7" также будет выполнятся.
231        2 * 1 - 3 * 3 = -7 и т.д.
А значит получится еще 6 рядов: 231546, 315462, 154623, 546231, 462315, 623154.
Итого получилось 12 способов.

Второй способ (указан на rsr-olymp.ru).
Каждый следующий член будет получаться из предыдущего умножением на некоторую фиксированную величину (по модулю 7). В качестве этой величины можно брать только 3 или 5. А первый член - любой, значит всего 12 вариантов.

Ответ: 12 способов.

Ресурсы:

Комментариев нет:

Отправить комментарий