Задача 35226

Темы:    [ НОД и НОК. Взаимная простота ] [ Процессы и операции ] [ Целочисленные решетки (прочее) ] [ Периодичность и непериодичность ] [ Мощность множества. Взаимно-однозначные отображения ]

Сложность: 4- Классы: 8,9,10,11

Условие

Можно ли расставить во всех точках плоскости с целыми координатами натуральные числа так, чтобы каждое натуральное число стояло в какой-нибудь точке, и чтобы на каждой прямой, проходящей через две точки с целыми координатами, но не проходящей через начало координат, расстановка чисел была периодической?

Подсказка

Поставьте в точке с координатами  (x, y)  число  НОД(x, y).
Другой подход: перебирайте прямые и делайте последовательно на каждой из них периодическую расстановку.

Решение 1

  Поставим в точке с координатами  (x, y)  число  НОД(x, y).  При этом каждое число стоит в какой-нибудь точке (например, число n стоит в точке  (n, n)).
  Пусть  ax + by = c  – уравнение прямой, не проходящей через начало координат и содержащей хотя бы две целые точки  (x₁, y₁)  и  (x₂, y₂).  Можно считать, что  c = 1.  Тогда числа a и b рациональны, как решения системы уравнений  ax₁ + by₁ = 1,  ax₂ + by₂ = 1.  Домножая теперь числа a, b, 1 на подходящее натуральное число, добиваемся того, что в уравнении  ax + by = с  коэффициенты a, b, c – целые числа.
  Пусть  (x, y)  – некоторая целая точка, лежащая на этой прямой. Тогда, очевидно,  НОД(x, y)  – делитель c. Точка  (x – bc, y + ac)  тоже лежит на нашей прямой, и  НОД(x – bc, y + ac) = НОД(x, y)  (действительно, если d делит x и y, и, следовательно, c, то d делит также  x – bc  и  y + ac;  наоборот – если d делит  x – bc  и  y + ac,  то d делит  a(x – bc) + b(y + ac) = ax + by = c,  и, следовательно, делит x и y). Это значит, что расположение чисел на прямой повторяется при сдвиге на – bc по оси Ox и на ac по оси Oy, то есть расположение чисел периодично.

Решение 2

  Прямых, проходящих через пару целых точек, счётное число. Перенумеруем их. Последовательно на первой, второй, ... прямых устраиваем периодическую расстановку чисел. Поскольку две прямые имеют не более одной общей точки, к моменту, когда периодическая расстановка уже имеется на 1-й, 2-й, ..., k-й прямых, на (k+1)-й прямой расставлено лишь конечное число чисел (не более k). Поэтому возможно устроить периодическую расстановку на (k+1)-й прямой (причём в выборе этой расстановки имеется большой произвол). Продолжаем этот процесс и дальше. Чтобы выполнялись все условия задачи, дополнительно следим за тем, чтобы на i-й прямой встречалось число i.

Ответ

Можно.

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

web-сайт

задача