В некоторых клетках шахматной доски стоят фигуры. Известно, что на каждой горизонтали стоит хотя бы одна фигура, причём в разных горизонталях – разное число фигур. Докажите, что всегда можно отметить 8 фигур так, чтобы в каждой вертикали и каждой горизонтали стояла ровно одна отмеченная фигура.

   Решение

Темы:    [ Простые числа и их свойства ] [ Делимость чисел. Общие свойства ] [ Разложение на множители ] [ Уравнения в целых числах ]

Сложность: 3 Классы: 8,9

Прислать комментарий

Условие

Найдите все такие тройки простых чисел p, q, r, что четвёртая степень каждого из них, уменьшенная на 1, делится на произведение двух остальных.

Решение

  Ясно, что любые два числа тройки различны (если  p = q,  то  p⁴ – 1  не делится на q). Пусть p – наименьшее из чисел тройки. Число
p⁴ – 1 = (p – 1)(p + 1)(p² + 1)  делится на qr. Но  p – 1  меньше любого из простых чисел q и r, а значит, взаимно просто с ними. Число  p² + 1  не может делиться на оба числа q и r, так как  p² + 1 < (p + 1)(p + 1) < qr.  Значит,  p + 1  делится на одно из них (для определённости, на q). Поскольку  q > p,  это возможно лишь при  q = p + 1.  Следовательно,  p = 2,  q = 3.  r является простым делителем числа  p⁴ – 1 = 15,  отличным от  q = 3,  значит,  r = 5.
  Осталось проверить, что тройка {2, 3, 5} удовлетворяет условиям задачи.

Ответ

{2, 3, 5}.

Источники и прецеденты использования