Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Клетчатая решётка (координатная плоскость) и точки, отрезки, прямые на ней

Тема Комбинаторная геометрия

Клетчатая решётка (координатная плоскость) и точки, отрезки, прямые на ней

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела комбинаторная геометрия

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#111174

При каких натуральных $n$ существует выпуклый $n$ -угольник с вершинами в узлах целочисленной решётки, у которого все стороны равны $100?$

Подсказки к задаче

Подсказка 1

Все стороны многоугольника будем рассматривать как вектора с некоторыми координатами. Тогда эти координаты x, y удовлетворяют равенству x² + y² = 100². Как могут быть получены все такие вектора?

Подсказка 2

Верно! Умножением на 20 векторов (±3,±4), умножением векторов (±7,±24) на 4 и как (0,±100) и (±100,0). Теперь попробуем учесть, что фигура должна быть замкнутой и выпуклой! Что это означает?

Подсказка 3

Верно! Сумма векторов должна быть нулевой, а угол при обходе против часовой стрелки с начальным должен строго возрастать. Из предыдущей подсказки мы получили, что у нас есть 20 возможных различных векторов. Тогда всего сторон не больше 20! А можно ли доказать, что при нечетных n ничего не выйдет?

Подсказка 4

Конечно! Если разделить все вектора и условие замкнутости на 4, получим, что нечетная сумма первых компонент векторов должна быть нулевой — противоречие. А можно ли для всех остальных n просто построить пример?

Показать ответ и решение

Каждая сторона многоугольника задаётся вектором $(x,y)$ с целыми координатами, удовлетворяющими условию:

2 2 2 x + y = 100 = 10000

Все целочисленные решения, полученные рассмотрением пифагоровых троек $(3,4,5),(7,24,25):$

(0,±100), (±100,0), (±60,±80), (±80,±60), (±28,±96), (±96,±28).

Всего $20$ векторов.

Фигура составленная из векторов обязана быть замкнутой и выпуклой.

1.: Замкнутость: Сумма векторов сторон должна быть нулевой:
$n ∑ (xi,yi)=(0,0) i=1$
2.: Выпуклость: При обходе против часовой стрелки угол каждого вектора с начальным должен строго возрастать.

Из полученных условий имеем ограничения на $n.$ Из условия на углы получаем, что каждый вектор используется в качестве стороны не более одного раза $=⇒ n ≤20.$

Разделим полученные векторы на $4 :$

(0,±25), (±25,0), (±15,±20), (±20,±15), (±7,±24), (±24,±4).

Заметим, что у любого из данных векторов одна компоненты четна, вторая нечетна. Условие замкнутости поделим на $4,$ получим:

∑n (xi yi) i=1 4 ,4 =(0,0)

что не возможно при нечетном $n.$ Для все четных $4 ≤n ≤20$ построим искомый выпуклый многоугольник. Если $n$ делится на $4,$ то возьмем векторы с неотрицательными координатами, кроме $(100;0),$ “выстроим” их по возрастанию угла, это построит четверть фигуры, затем из четырех таких частей получим всю фигуру.

Если $n$ не делит на $4,$ построение такое: аналогично первому пункту встроим вектора, используя в начале $(100;0).$ Затем отразим все векторы, кроме $(100;0),$ относительно прямой $(y =50),$ а затем всю фигуру отразим относительно верхней границы.

Ответ:

При всех четных $4 ≤n ≤20$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#111175

Дан треугольник $ABC$ с вершинами в узлах целочисленной решётки и узлы $A′$ и $B′$ такие, что внутри отрезков $AB$ и $A′B ′$ поровну узлов. Докажите, что можно выбрать узел $′ C$ так, чтобы внутри треугольников $ABC$ и $′ ′′ AB C$ было поровну узлов.

Подсказки к задаче

Подсказка 1

Нарежем решетку на прямые, параллельные сторонам AB и A'B'. Попробуем теперь рассмотреть аффинное преобразование, переводящее AB в A'B'. Как можно определить точку C'?

Подсказка 2

Верно! Можно определить C' как образ C при этом преобразовании. Остается показать, что условие задачи выполняется! Легко видеть, что площади двух треугольников ABC и A'B'C' совпадают. А какая формула связывает узлы решетки и площади треугольников?

Подсказка 3

Верно, формула Пика! Заметим, что целочисленные точки с границы треугольника ABC перешли на границу треугольника A'B'C'. Что тогда получается?

Показать доказательство

Давайте нарежем решётку на прямые, параллельные сторонам $AB$ и $A ′B′.$ Тогда рассмотрим аффинное преобразование, которое переводит $AB$ в $′ ′ AB ,$ а прямые направления $AB$ в соответствующие прямые направления $′′ A B .$ Если допустим, что оба вектора $(AB$ и $′ ′ AB )$ не параллельны сторонам решётки, тогда нужно совместить $A$ и $′ A ,$ а потом посмотреть, на какое расстояние мы сместились по горизонтали из $A$ (в точку $A1),$ а потом, сколько шагов мы сделали по целым точкам вдоль вектора $AB$ и сделать аналогичные шаги. Если вектор горизонтальный, то идём сначала по вертикали. Тогда рассмотрим как точку $′ C$ образ точки $C.$ Получаем, что площади полученных треугольников совпадают, поскольку расстояние между прямыми уменьшилось в $AB-- A′B′$ раз, а основание увеличилось в $A′B′- AB$ раз. При этом все точки на сторонах исходного треугольника теперь на сторонах получившегося по построению (если есть точка на стороне, то можно провести через неё параллельную $AB$ прямую, которая аналогично перейдёт в параллельную $′ ′ A B)$ . Значит, по формуле Пика и количество внутренних узлов сохранилось, что и требовалось доказать.

Ошибка.
Попробуйте повторить позже

Задача 3#111177

В пространстве введена прямоугольная декартова система координат. Верно ли, что у любого прямоугольного параллелепипеда объема $2 1999,$ вершины которого расположены в точках с целыми координатами, ребра параллельны осям координат?

Подсказки к задаче

Подсказка 1

Пусть стороны данного параллелепипеда не параллельны осям, тогда каждая из них — квадратный корень из суммы квадратов целых чисел. Тогда объем параллелепипеда в квадрате — произведение трех сумм квадратов. Какой вывод можно сделать?

Подсказка 2

Верно! Тогда квадрат объема — сумма квадратов целых чисел. Пусть эти числа — m и n. Могут ли они не делиться на 1999?

Подсказка 3

Верно, не могут! Ведь тогда мы получим из малой теоремы Ферма, что 1 и -1 сравнимы по модулю 1999. Тогда равенство m² + n² = 1999⁴ можно разделить на 1999²! А нельзя ли еще раз проделать то же самое и получить какое-нибудь противоречие?

Показать ответ и решение

Пусть стороны данного параллелепипеда не параллельны осям, тогда они имеют длины вида $∘a2+-b2, i i$ откуда

2 2 2 2 2 2 4 4 2 2 (a1+b1)(a2+ b2)(a3 +b3)=1999 =⇒ 1999 = m +n , (m,n∈ ℕ)

Пусть $m,n$ не делятся на $1999,$ тогда из

2 2 1998 1998 m ≡1999 −n =⇒ m ≡1999 −n =⇒ 1 ≡1999 −1

получаем противоречие с малой теоремой Ферма. Поделим тождество на $19992,$ получим

(-n-)2 +(-m--)2 = 19992, 1999 1999

аналогично заключаем, что $m,n$ делятся на $19992 =⇒$

2 2 4 n +m ≥ 2⋅1999

— противоречие.

Ответ:

Верно

Ошибка.
Попробуйте повторить позже

Задача 4#111179

Докажите, что для любого $n$ существует окружность, внутри которой лежит ровно $n$ целочисленных точек.

Подсказки к задаче

Подсказка 1

Любая точка внутри окружности — тоже точка некоторой окружности. Тогда для того, чтобы контролировать количество точек внутри окружности, можно попробовать выбрать такую точку A, чтобы любая окружность с центром в этой точке содержала на себе не более одной целочисленной точки. Существует ли такая A?

Подсказка 2

Верно, существует! Например, в качестве такой точки можно взять A = (√2, 1/3). Тогда каким бы ни был радиус окружности с центром в точке A, на ней будет не более одной целочисленной точки. А внутренность любой окружности — объединение всех окружностей, лежащих внутри данной. Как тогда построить окружность с радиусом R и центром в точке A, чтобы внутри нее было не более n целочисленных точек?

Показать доказательство

Докажем сначала, что на окружности с центром $A =(√2,1∕3)$ не может лежать более одной целочисленной точки. Если $m$ и $n$ — целые числа, то

( √ -)2 ( 1)2 √- m − 2 + n − 3 = q− 2m 2

где $q ∈ℚ.$ Поэтому из равенства

( ) ( ) (m1 − √2)2 + n1 − 1 2 = (m2− √2)2+ n2− 1 2 3 3

следует, что $m1 =m2.$ По теореме Виета сумма корней уравнения $( 1)2 n − 3 = d$ равна $2∕3,$ поэтому лишь один корень может быть целочисленным. Расположим теперь радиусы окружностей с центром $A,$ проходящих через целочисленные точки, в порядке возрастания: $R1 <R2 < R3 < ....$ Если $Rn < R< Rn+1,$ то внутри окружности радиуса $R$ с центром $A$ лежит ровно $n$ целочисленных точек.

Ошибка.
Попробуйте повторить позже

Задача 5#111183

В парке, имеющем форму круга радиуса $R$ с центром в начале координат, деревья радиуса $r$ посажены во всех вершинах квадратной сетки со стороной $1,$ кроме центра. Пусть $2 l$ — минимальное целое число, не меньшее $2 R ,$ представимое в виде суммы квадратов двух целых взаимно-простых чисел. Докажите, что вид из центра полностью заслонен тогда и только тогда, когда $r≥ 1∕l.$

Подсказки к задаче

Подсказка 1

Сначала покажем, что если радиус дерева маленький, то всю плоскость закрыть не удастся. Естественно рассмотреть именно ту точку, расстояние до которой l, и использовать соображения площади.

Подсказка 2

Теперь покажем, что если радиус достаточно большой, то вся плоскость будет закрыта. Мы знаем, что lr≥1, так что площадь прямоугольника со сторонами 2l и 2r хотя бы 4. Это намекает на теорему Минковского.

Подсказка 3

Вот мы нашли целую точку в прямоугольнике, если она в круге, то мы уже победили. Тогда если она снаружи, и её координаты взаимно просты, то она обязательно находится на расстоянии l от начала координат.

Подсказка 4

Осталось доказать, что на самом деле мы уже заслонили часть плоскости, которую заслоняет точка на расстоянии l.

Показать доказательство

Докажем, что при $r <1∕l$ обзор не будет заслонен. Для этого достаточно предъявить точку вне круга, видимую из центра.

Пусть $2 2 2 l = a + b,$ покажем, что точку $P$ с координатами $(a,b)$ видно из центра. Пусть это не так, тогда существует точка $Q = (c,d)$ такая, что $ρ(Q,OP) <1∕l,$ где $ρ(A,BC)$ — расстояние от точки $A$ до прямой $BC.$

|bc− ad| 1 2 ρ(Q,OP)< 1∕l⇔ √a2+-b2 < l ⇔ (bc− ad) < 1

Последнее равенство может быть выполнено, если $bc= ad,$ но в таком случае, так как $Н ОД(a,b)= 1,$ то $a|c$ и $b|d,$ в таком случае $c2+ d2 > R,$ то есть такая точка $Q$ вне парка — противоречие.

Теперь покажем, что при $r≥ 1l$ все целые точки на решётке будут не видны. Будем считать $r< 1$ (иначе уменьшим радиус, а если $l= 1,$ то задача не имеет смысла). Тогда покажем, что можно считать, что $R = l− 𝜀.$ Будем расширять радиус, возможно, к нам добавятся какие-то новые точки $B$ , но тогда их координаты будут не взаимно просты, значит, найдётся точка $A$ внутри круга, координаты которой будут пропорциональны координатам $B.$ Но тогда если до какой-то прямой $OP$ $ρ(B,OP)≤ r,$ то и $ρ(A,OP)≤ r,$ то есть если в новом круге найдётся подходящая точка, то и в исходном тоже была. Теперь внутри нашего круга лежат все точки, расстояние до которых от начала координат меньше $R.$ Пусть есть точка $P,$ которую видно из начала координат. Рассмотрим прямоугольник со сторонами $2r$ и $2l$ c центром в $O,$ и сторона $2R$ которого параллельна $OP.$ Тогда прямоугольник центрально-симметричный, замкнутый и имеет площадь хотя бы $4.$ Тогда по теореме Минковского в нём есть целая точка. Ясно, что расстояние от этой целой точки до прямой $OP ≤r,$ если эта точка оказалась не в той полуплоскости, то рассмотрим симметричную ей. Итак, мы нашли в прямоугольнике точку, расстояние от которой до луча $OP ≤ r.$ Тогда посмотрим, что это могла быть за точка. Самая далёкая от $O$ — это вершина прямоугольника. Она находится на расстоянии $√l2+-r2.$ Поскольку $r< 1$ и сумма квадратов координат целая, эта точка $X$ или на расстоянии $l$ или внутри круга. Если она внутри круга, то мы уже победили, так что предположим, что она на расстоянии $l.$ Тогда покажем, что вся окружность точки $X$ радиуса $r$ уже закрыта. Рассмотрим какой-нибудь треугольник $OXA,$ где $A$ лежит в круге (для начала, например, $(1,0)).$ Допустим, этот треугольник оказался простым, то есть не содержит целых точек на сторонах и внутри. Тогда его площадь $1, 2$ а с другой стороны она $lh, 2$ где $h$ — расстояние от $A$ до $OP.$ Тогда $h = 1≤ r, l$ то есть дерево как минимум касается прямой $OX.$ Если же треугольник оказался не простым, то рассмотрим в нём ближайшую к $O$ точку $B$ и заменим $A$ на неё. Точка $B$ точно внутри круга (по определению $l$ ), площадь треугольника строго уменьшилась. Так мы найдём точки в обеих полуплоскостях относительно $OX,$ деревья которых как минимум касаются $OX.$ Заметим, что эти две окружности вместе целиком перекрывают окружность точки $X,$ так что если точка $X$ закрывала обзор для $OP,$ то найдётся и точка в круге, которая закроет обзор, что и требовалось доказать.

Ошибка.
Попробуйте повторить позже

Задача 6#111637

Вершины многоугольника (не обязательно выпуклого) расположены в узлах целочисленной решетки. Внутри него лежит $n$ узлов решетки, а на границе $m$ узлов. Докажите, что его площадь равна $m- n + 2 − 1.$

Показать доказательство

Каждому многоугольнику $M$ с вершинами в узлах целочисленной решётки поставим в соответствие число $f(M) =∑ φi, i2π$ где суммирование ведётся по всем узлам решётки, принадлежащим $M,$ а $φi$ — угол, под которым виден многоугольник $M$ из соответствующего узла. Например, для внутренней точки $φi = 2π,$ для точки на границе (не являющейся вершиной) $φi =π.$ А сумма углов по вершинам многоугольника — это $(количество углов− 2)⋅π,$ тогда легко видеть, что:

2π (m − 2)π m f(M )= n⋅2π + --2π---=n + 2-− 1

Остаётся проверить, что $f(M )$ совпадает с площадью $S.$ Если многоугольник $M$ разрезан на части $M1$ и $M2$ с вершинами в узлах решётки, то $f(M )=f(M1)+ f(M2 ),$ так как углы в узлах складываются. Следовательно, если формула верна для $M1$ и $M2,$ она верна и для $M.$

Рассмотрим прямоугольник со сторонами $p$ и $q,$ параллельными осям решётки. Внутренних узлов: $(p − 1)(q− 1),$ граничных узлов: $2(p+q)− 4.$ Тогда:

f(M)= (p− 1)(q− 1)+ 2(p-+q)− 1= pq− p − q+ 1+ p+ q− 1 =pq 2

Формула верна для прямоугольников. Разрежем прямоугольник диагональю на два треугольника. Для каждого треугольника $f(M )= pq2 ,$ что совпадает с его площадью.

Любой многоугольник можно триангулировать непересекающимися диагоналями. Поскольку формула аддитивна и верна для треугольников, она верна и для всего многоугольника. Таким образом, $S =n + m2 − 1.$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#82785

Сколько точек пространства с целочисленными координатами принадлежат треугольнику с вершинами $(3,4,5)$ , $(11,10,6)$ , $(5,8,9)$ ? Точка на вершинах и сторонах тоже считаются.

Источники: Ломоносов - 2024, 11.8 (см. olymp.msu.ru)

Подсказки к задаче

Подсказка 1

Давайте немного упростим задачу и сдвинем одну из вершин в начало координат, чтобы числа стали попроще, для этого можно сделать параллельный перенос на вектор (-3;-4;-5), а как можно посчитать кол-во целочисленных точек на стороне?

Подсказка 2

Верно, кол-во целых точек (включая концы) на отрезке (x₁,y₁,z₁), (x₂,y₂,z₂), это НОД(|x₁-x₂|, |y₁-y₂|, |z₁-z₂|) + 1, итак, когда мы знаем кол-во точек на периметре треугольника, давайте перейдём к его внутренности, если взять произвольную целочисленную точку, можно ли получить какое-то следствие, которое было бы легче проверить, но оно бы оставило нам пару точек для перебора?

Подсказка 3

Да, можно сказать, что если точка A была подходящей, то точка A' полученная проецированием её на одну из плоскостей тоже будет подходить, а значит можно спроецировать весь треугольник, например, на плоскость Oxy и найти возможных кандидатов там, а потом проверить только их

Подсказка 4

Для проверки наших кандидатов можно составить систему уравнений из двух векторов, образующих стороны, с положительными коэффициентами, сумма которых меньше 1, чтобы получить точку внутри треугольника, остаётся проверить, что найдутся целые решения, которые бы удовлетворяли полученной системе

Подсказка 5

Для удобства можно выразить из первых двух уравнений коэффициенты и подставить их в третье уравнение, тогда останется лишь условие на координаты точек, но предыдущие ограничения всё ещё следует проверить

Показать ответ и решение

Перенесём треугольник одной вершиной в начало координат. Тогда его можно представлять как точку $(0,0,0)$ , из которой выходят вектора $u =(8,6,1)$ и $v = (2,4,4)$ .

Тогда внутренность треугольника можно представить как $λu+ μv,$ где $λ,μ$ — действительные числа, $λ,μ >0,$ и $λ +μ <1.$

Вопрос о целых точках на треугольнике, получается, стоит так: при каких целых $n,m,k$ система:

(| ||{8λ +2μ= n, ||6λ +4μ= m, |(λ +4μ =k

имеет решения $λ,μ$ , удовлетворяющие условиям выше.

Мы выделили внутренность, потому что стороны легче рассмотреть отдельно. Три целочисленные вершины лежат в треугольнике по определению. На сторонах точки подсчитать тоже просто — стороны это вектора $u= (8,6,1),v =(2,4,4),$ и третья сторона $(6,2,−3)$ . Получить целочисленную точку можно только на середине вектора $v$ , а у остальных сторон нет общих делителей координат, и через целые точки они не проходят. Значит, на периметре лежат $3+ 1= 4$ точки.

Переходим к внутренней части треугольника. Конечно, нет гарантий, что там будет хотя бы одна целочисленная точка — но если такая есть, то её проекции на координатные плоскости тоже будут целочисленные. Поэтому давайте рассмотрим проекцию треугольника на плоскость $Oxy$ , и отберём на ней потенциально подходящие пары $(n,m ),$ а после выкинем лишние.

Проецируем треугольник на $Oxy$ — получается треугольник на плоскости с вершинами $(0,0),$ $(8,6),$ $(2,4).$ Внутрь него точки попадут такие: $(1,1),(2,2),(2,3),(3,3),(3,4),(4,4),(5,4),(6,5).$

Решаем систему, состоящую из двух первых уравнений:

({ (8 λ+2μ =n, 6λ+4μ =m

Получаем следующие решения:

2n − m −3n +4m λ = -10--,μ= ---10---

Полученные значения $λ,μ$ подставляются в третье уравнение $λ+ 4μ= k$ , и если $k$ оказывается целым — точка найдена. После подстановки получается выражение:

3 − n+ 2m =k,

то есть $m$ должна быть чётной. Из $8$ кандидатов подойдут только $4:$ $(2,2),(3,4),(4,4),(5,4)$ .

Плюс $4$ точки на сторонах, и всего точек на треугольнике $4 +4 =8.$

Ответ: 8

Ошибка.
Попробуйте повторить позже

Задача 8#85910

Лес представляет собой координатную плоскость, в некоторых узлах которой растут ёлки. Всего ёлок больше миллиона. Докажите, что можно срубить более 100000 ёлок так, чтобы расстояние между любыми двумя срубленными ёлками было больше 3. (Узлом называется точка, обе координаты которой целые; ёлки считаем точками.)

Источники: ФЕ - 2024, 11.2 (см. www.formulo.org)

Подсказки к задаче

Подсказка 1

Когда нас просят доказать, что что-либо возможно, то один из вариантов решения это просто привести пример. Так и в этой задаче, нам нужно придумать пример вырубки ёлок, удовлетворяющей условию.

Подсказка 2

Получается, нам нужно выбрать больше 100000 ёлок так, чтобы расстояние между любыми двумя из них было больше 3. Может быть не понятно, по какому принципу их вообще выбирать. В таких случаях полезно каким-либо образом разбить ёлки на группы так, чтобы одна из групп была искомой. Но на какое количество групп разбивать?

Подсказка 3

Вспомним принцип Дирихле и посмотрим на числа. Заметим, что если разбить ёлки на 10 групп, то в одной из них точно будет больше 100000 штук. Тогда нам нужно, чтобы внутри каждой группы расстояния между любыми двумя ёлками было более 3.

Подсказка 4

Если не получается придумать разбиение, попробуйте посмотреть на эту задачу по-другому. Например, попытаться разбивать не ёлки, а узлы. Так же не забывайте про количество групп, попробуйте использовать остатки при делении на 10.

Показать доказательство

Раскрасим узлы в 10 цветов так, чтобы узлы одного цвета образовывали сетку из квадратов со стороной $√10$ . Например, пусть цвет узла с координатами ( $x,y$ ) определяется остатком от деления числа $x+ 3y$ на 10 (считаем, что деревья растут в центрах квадратов):


0	1	2	3	4	5	6	7	8	9	0

7	8	9	0	1	2	3	4	5	6	7

4	5	6	7	8	9	0	1	2	3	4

1	2	3	4	5	6	7	8	9	0	1

8	9	0	1	2	3	4	5	6	7	8

5	6	7	8	9	0	1	2	3	4	5

2	3	4	5	6	7	8	9	0	1	2

9	0	1	2	3	4	5	6	7	8	9

6	7	8	9	0	1	2	3	4	5	6
3	4	5	6	7	8	9	0	1	2	3

0	1	2	3	4	5	6	7	8	9	0

По принципу Дирихле, в какой-то из десяти цветов окрасились более 100 тысяч ёлок. Тогда все эти ёлки можно срубить, поскольку расстояние между любыми двумя из них не меньше $√10$ .

Ошибка.
Попробуйте повторить позже

Задача 9#104581

Существует ли функция из шара в круг, не уменьшающая расстояния?

Показать ответ и решение

Без ограничения общности будем считать, что в трехмерный шар вписывается куб с ребром единичной длины. Разобьем каждое ребро на $n$ равных частей и построим кубическую решетку, в которой $3 (n +1)$ узлов. Расстояние между двумя любыми узлами не менее $1∕n.$ Рассмотрим образ этой решетки при отображении. Расстояние между двумя любыми точками из образа должно быть так же не меньше $1∕n.$

Пусть диаметр круга равен $D$ . Впишем круг в квадрат и разобьем его стороны на $m$ равных частей так, чтобы длина каждой части была меньше $1∕2n.$ То есть должно выполняться $D ∕m < 1∕2n,$ можно взять $m= [2Dn ]+1.$ Тогда большой квадрат разобьется на $2 m$ квадратиков.

Диагональ каждого квадратика равна $√- 2⋅1∕2n < 1∕n.$ Значит, никакие два узла кубической решетки после отображения не могут попасть в один квадратик. Найдется достаточно большее $n,$ такое что $3 2 2 (n+ 1)> (2Dn+ 1) ≥m .$ Получается, найдутся две точки в шаре, расстояние между которыми не меньше $1∕n,$ а расстояние между их образами в круге меньше $1∕n.$ Значит нужного отображения не существует.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 10#67590

На координатной плоскости дан параллелограмм с вершинами в точках $O(0;0)$ , $P (− 14;42),Q(6;42)$ и $R(20;0).$ Найдите количество пар точек $A(x1;y1)$ и $B(x2;y2)$ с целыми координатами, лежащих в этом параллелограмме (возможно, на границе) и таких, что $3x2− 3x1 +y2− y1 = 33.$

Источники: Физтех-2023, 11.6 (см. olymp-online.mipt.ru)

Подсказки к задаче

Подсказка 1

Сначала может показаться, что задача какая-то жуть. Нужно находить количество пар точек, подходящие под какое-то странное условие... Но давайте понемногу "причёсывать" задачу и понимать, что от нас хотят. Попробуем хорошо преобразовать условие, данное на точки A и B. Какое действие хочется сделать, увидев в одной части координаты и точки A, и точки B?

Подсказка 2

Да, давайте перенесём координаты A в правую часть, а точки B — в левую. Число 33 тоже перенесём влево. Так как координаты у нас целые, то слева и справа получаются тоже какие-то целые значения. Пусть это будет целое число k. Что же теперь означает наше условие на координаты после того, как мы переписали их в удобном виде?

Подсказка 3

Верно, это две параллельные прямые, где вместо x и y мы подставляем координаты точек A и B. То есть мы можем записать уравнение прямых в общем виде с k. Что же нам теперь нужно сделать? Не забудем, что у нас есть ограничение на прямые самой границей параллелограмма. Идейная часть закончилась, теперь уже можно реализовывать техническую часть решения. Вспоминая вопрос задачи, что нам нужно теперь найти?

Подсказка 4

Верно, нам нужно найти в принципе количество целых точек x на прямых вида y=-3x+b. Это с помощью рассмотрения случаев, когда b делится на 3 и не делится, решается несложно(учитывая, конечно, снова ограничение по параллелограмму). Найдя уже до этого ограничения на k, остаётся только дело за комбинаторикой. То есть нам нужно для каждого k, выбрать на прямых нужные нам целые точки.

Показать ответ и решение

Запишем исходное условие на координаты точек $A(x ;y) 1 1$ и $B(x;y ) 2 2$ в виде

3x2+ y2− 33 =3x1+ y1

Так как координаты точек $A(x1;y1)$ и $B(x2;y2)$ являются целыми числами, то левая и правая части этого равенства могут принимать только целочисленные значения $k.$ Пара точек $A(x1;y1)$ и $B(x2;y2)$ с целочисленными координатами удовлетворяет условию тогда и только тогда, когда они лежат на параллельных прямых

y = −3x+ k и y = −3x+ k+ 33

соответственно. Найдём подходящие значения параметра $k.$

Стороны $OP$ и $QR$ параллелограмма лежат на прямых

y =− 3x и y =− 3x+60,

поэтому они параллельны прямым, на которых лежат точки $A (x1;y1)$ и $B(x2;y2).$ Эти прямые пересекают параллелограмм при

( { 0≤ k≤ 60 ( ⇔ k∈[0;27] 0≤ k+ 33 ≤60

Выясним количество точек с целочисленными координатами на каждой из прямых вида

y = −3x+ b

Рассмотрим несколько вариантов:

$1)$ Если $b$ кратно трём (т.е. $b= 3l),$ то получаем прямую

y = 3(−x +l)

При любом целом $x$ получится целое значение $y,$ а чтобы точка оказалась в параллелограмме нужно, чтобы

0≤ y ≤42 ⇔ l− 14≤ x≤ l

При любом $l$ этому неравенству удовлетворяет $15$ целых значений $x.$

$2)$ Если $b$ не делится на 3, т.е. при $b= 3l+ γ,$ где $γ ∈ {1;2},$ имеем

0≤ −3x+ 3l+γ ≤42⇔ l+ γ − 14≤ x≤ l+ γ 3 3

Учитывая, что $x∈ ℤ,$ получаем

l− 13≤ x≤ l

Значит, этому неравенству удовлетворяет $14$ целочисленных значений.

Если $k= 3l$ (таких значений $10),$ то на каждой из двух прямых

y = −3x+ k и y = −3x+ k+ 33

можно выбрать по $15$ точек — всего $10 ⋅15⋅15= 2250$ пар.

Если $k⁄= 3l$ (таких значений $18),$ то на каждой из двух прямых можно выбрать по $14$ точек — имеем $18⋅14⋅14= 3528$ пар.

Итого получаем $2250 +3528= 5778.$

Ответ: 5778

Ошибка.
Попробуйте повторить позже

Задача 11#70485

Найдите все пары ненулевых (не обязательно положительных) рациональных чисел $x,y,$ обладающие следующим свойством: любое положительное рациональное число можно представить в виде ${rx}∕{ry}$ с положительным рациональным $r.$

Источники: СпбОШ - 2022, задача 11.6(см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Давайте для начала причешем задачу. Если r - рациональное и положительное, то x,y - просто целые, так как можно построить явную биекцию между решениями при просто рациональных x,y и целых. Также, можно заметить, что если мы уберем целую часть числа r , то отношение из условия останется таким же, а значит, можно сказать, что 0 < r < 1 . А тогда можно сказать, что {(1 - r)x} = {-rx}, аналогично с y. Значит, можно считать, что y - натуральное, а х - целое. Значит, у нас, существенно, два случая - когда наша дробь - положительное число, и когда отрицательное. Попробуйте теперь найти такую дробь, которая не может быть представлена в таком виде как мы описали, и с теми условиями, которые мы доказали.

Подсказка 2

Сейчас будет приведено совсем не строгое, но тем не менее, наталкивающее на мысли, объяснение, почему нужно брать конкретную дробь, при разборе случая , когда дробь - положительное число. Давайте распишем {rx} как rx - [rx], {ry} как ry - [ry]. Тогда, для некоторого n/k = {rx}/{ry}, выполнено, что n*{ry} = k*{rx}. Значит, nry - n*[ry] = krx + k*[rx]. Что мы из этого можем получить? Если мы хотим прийти к противоречию, то можно попытаться взять какие - то k и n, такие, чтобы что-то в этом равенстве стало плохо. Сейчас целое число слева равно целому справа, а что можно подставить, чтобы слева, после преобразований, стало нецелое, а справа целое?

Подсказка 3

Возьмем n = x + 1, k = y. Тогда, во первых, сократятся rxy и rxy слева и справа, а в итого, останется уравнение {ry} = x * [ry] - y * [rx]. А значит, слева будет что - то между 0 и 1, а справа что-то целое. Пришли к противоречию. То есть, случай, когда дробь больше нуля разобран. Осталось подумать над случаем, когда наша дробь отрицательна. Можно попытаться найти контрпример, однако сразу непонятно как его строить, рассуждения из прошлого пункта непримиримы. Тогда скажем, что наша дробь равна некоторому a/b, где а - отрицательное и попытаемся доказать, что для любых а и b такое r найдется. И кажется, что в такой непонятной конструкции, как дробная часть, могут спасти только оценки значений. Попробуйте их применить(само собой, после избавления от знаменателей).

Подсказка 4

После избавления от знаменателей, у нас получается выражение brx - b*[rx] = ary - a[ry]. А значит, r - одно из решений уравнения r(bx - ay) = n, для некоторого целого n. При этом, мы можем сказать, что (без ограничения общности) х < 0, а значит, по нашим рассуждениям из первой подсказки, {rx} = 1 - {r|x|}. Подставьте это значение в наше уравнение и попробуйте подумать над максимальным и минимальным значением нецелое части.

Подсказка 5

Получим, что b = a{ry} + b{r|x|}. При r бесконечно близком к нулю, получается, что правая часть будет стремиться к нулю, что меньше b. При r бесконечно близким к 1, но меньшим ее, правая часть будет стремиться к a+b, что больше b. Значит, найдется промежуточное значение, при котором в нашем выражении будет достигаться равенство. А значит, для любой пары а и b из второго случая, мы привели пример. Значит, только для xy<0 выполнено требуемое.

Показать ответ и решение

Первое решение.

Разобьём плоскость на единичные квадраты линиями целочисленной решетки. Проведем прямую $l$ через начало координат $O$ и точку $(x,y).$ Поскольку $x,y ∈ Q.$ она имеет рациональный угловой коэффициент и проходит через какой-то узел решетки. Точка вида $(rx,ry)$ — это любая рациональная точка этой прямой. Проведем прямую через такую точку и левый нижний угол той клетки, в которую попала эта точка. Угловой коэффициент этой прямой равен как раз ${rx}∕{ry}.$

$PIC$

Совместим между собой все единичные квадраты, в которых есть точки прямой $l.$ В полученном квадрате прямая $l$ отобразится конечным количество отрезков, параллельных исходной прямой.

Предположим, что $x$ и $y$ одного знака. Тогда полученные отрезки имеют положительный угловой коэффициент. Один из них выходит из левого нижнего узла квадрата. Ясно, что из этого узла можно провести луч с положительным рациональным коэффициентом $λ,$ который пересечет правую сторону квадрата, не встретив по дороге точек ни одного из наших отрезков. Это число $λ$ нельзя представить в нужном виде.

Пусть, наоборот, числа $x$ и $y$ разного знака. Тогда наши отрезки имеют отрицательный угловой коэффициент. Один из них выходит из левого верхнего узла квадрата. Несложно понять, что один из этих отрезков соединяет точку на левой стороне квадрата с точкой на его нижней стороне. На рациональных точках этого отрезка реализуются все возможные положительные рациональные угловые коэффициенты!

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Так как в качестве $r$ можно взять любое положительное рациональное число, можно считать, что числа $x$ и $y$ целые. В этом случае замена числа $r$ на его дробную часть не изменит отношения ${rx} {ry},$ значит, можно дополнительно считать, что $0< r< 1.$ Наконец, замена r на $1− r$ соответствует смене знаков чисел $x$ и $y,$ поскольку

{(1 − r)x} {−rx} {(1-− r)y}-= {−ry}.

Таким образом, достаточно рассмотреть лишь случай, когда $y$ — натуральное число.
Пусть $x$ также является натуральным числом. Покажем, что уравнение

{rx}-= x+1- {ry} y

не имеет решений относительно $r.$ Домножив на знаменатели и выразив дробную часть через целую, получим уравнение

y⋅rx− y⋅[rx]= x⋅ry− x ⋅[ry]+ {ry},

или, что то же самое,

{ry} =x ⋅[ry]− y⋅[rx].

Но это уравнение не может иметь решений, поскольку левая часть положительна и меньше $1,$ а правая часть целая. Следовательно, если числа $x$ и $y$ одного знака, то требуемое $r$ не найдётся.
Пусть $x$ является отрицательным целым числом. Достаточно показать, что уравнение

{rx} a {ry} = b (∗)

для любых натуральных чисел $a$ и $b$ имеет вещественное решение $r.$ Тогда

b⋅rx− b⋅[rx]=a ⋅ry− a⋅[ry]

и, значит, $r$ является решением линейного уравнения

(bx− ay)r= n

для некоторого целого $n$ и, в частности, должно быть рациональным числом. Домножив уравнение $(∗)$ на знаменатели и воспользовавшись тем, что ${rx} =1 − {r|x|},$ получим уравнение

b= a{ry} +b{r|x|}.

При $r= 0$ правая часть равна нулю и поэтому меньше левой. А при $r,$ близких к $1,$ обе дробные части также будут близки к $1,$ поэтому правая часть будет близка к $a+ b$ и, в частности, будет больше левой. Следовательно, при некотором промежуточном $r$ правая часть будет равна левой. Поэтому если числа $x$ и $y$ разных знаков, то требуемое $r$ обязательно найдётся.

Ответ:

подходят все пары, в которых $xy <0$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 12#74470

На координатной плоскости дан прямоугольник с целочисленными координатами вершин, отличный от квадрата. Докажите, что можно провести несколько прямых, параллельных сторонам прямоугольника, так, что прямоугольник разобьется на квадраты с целочисленными координатами вершин.

Источники: БИБН-2022, 11.5 (см. www.unn.ru)

Подсказки к задаче

Подсказка 1

Давайте сначала "причешем" задачу, чтобы нам было удобнее её решать. Нам дали произвольный прямоугольник с вершинами в целых точках. Тогда как, не умаляя общности, можно его представить на координатной плоскости?

Подсказка 2

Верно, можно изобразить прямоугольник с одной из вершин в начале координат O, потому что иначе сделаем сдвиг на соответствующий вектор, и ничего не поменяется. Давайте теперь решать задачу на языке векторов. Введите обозначения для координат вершин прямоугольника. Как теперь можно записать условие перпендикулярности смежных сторон с точкой O?

Подсказка 3

Ага, на языке векторов это будет значить, что их скалярное произведение равно 0. Отлично, уже что-то! Теперь нужно как-то воспользоваться целостностью координат. Попробуем разобрать два случая, когда координаты точек взаимно просты и когда это не так. Давайте сначала рассмотрим первый случай. Почему в этом случае можно сказать, что наш исходный прямоугольник это квадрат?

Подсказка 4

Пусть координаты вершин были (p;q) и (m;n). Тогда из прошлой подсказки мы знаем, что pm + qn = 0, а из взаимной простоты получаем, что p = ±n, q = ±m. В этом случае всё понятно. Пусть теперь НОД(p;q) = k. Тогда какие координаты точек на одной стороне хорошо бы рассмотреть? Аналогично с другими координатами.

Подсказка 5

Верно, давайте рассмотрим координаты точек (pi;qi), где i = 1, 2, 3,..., k-1, и проведём через них прямые, параллельные стороне OB. Они пересекут в каких-то точках противоположную сторону прямоугольника, причём для них выполняется определённое равенство для векторов. Теперь если же m и n взаимно просты, то проделайте те же действия. Осталось только понять, почему это решает задачу и аккуратно довести её до конца.

Показать доказательство

Пусть $ABCD$ — данный прямоугольник. Без ограничения общности можно считать, что $A = O$ — начало координат: иначе сместим начало координат в точку $A,$ а в конце сделаем сдвиг на целочисленный вектор $−→ AO.$ Обозначим векторы $−−→ ⃗u= OD =(p;q),$ $−−→ ⃗v = OB = (m; n),$ где $p$ , $q,m,n$ — целые числа. Поскольку $⃗u$ и $⃗v$ взаимно перпендикулярны, их скалярное произведение равно нулю, т.е. $pm +qn =0$ (этот факт также следует из соотношения для угловых коэффициентов перпендикулярных прямых $OB$ и $OD$ ).

$PIC$

Рассмотрим сначала случай, когда $p$ и $q$ не взаимно просты. Тогда $p= p1k,q =q1k,k =$ НОД( $p,q)> 1.$ В этом случае рассмотрим на стороне $OD$ промежуточные точки $D ,D ,...,D , 1 2 k−1$ где $−−O→D = (pi;qi),i= i 1 1$ $1,2,...,k− 1.$ Проведём через точки $D i$ прямые, параллельные стороне $OB.$ Они пересекут сторону $BC$ в точках $′ Di,$ где $−−→′ −−→ −−→′ −−→ −−→ ODi = OB + BDi = OB + ODi = (m+ p1i;n+ q1i).$

Таким образом, точки $Di$ и $′ Di$ имеют целочисленные координаты и тем самым, прямые $′ DiDi(i= 1,2,...,k− 1)$ разбивают прямоугольник $OBCD$ на $k$ прямоугольников с целочисленными вершинами. Назовем это разбиением первого типа.

Аналогично, если $m$ и $n$ не взаимно просты, то прямыми, параллельными стороне $OD,$ разобьем $OBCD$ на меньшие прямоугольники с целочисленными вершинами. Назовем это разбиением второго типа; прямые этого разбиения проходят через промежуточные точки $Bj$ на стороне $OB,$ где $j = 1,2,...,l− 1,$ а $l$ — наибольший общий делитель $m$ и $n,(m = m1l,n=$ $n1l),−−O→Bj = (m1j;n1j).$ Заметим, что в случае, когда одновременно $k> 1$ и $l>1,$ прямые первого и второго разбиений разбивают прямоугольник $OBCD$ на $k⋅l$ равных прямоугольников с вершинами в точках $Mij,$ где $−O−M−i→j = −−O→Di+ −O−→Bj =(p1i+ m1j;q1i+ n1j),i$ $=1,2,...,k,j = 1,2,...,l,$ т.е. все вершины имеют целочисленные координаты.

Итак, приходим к случаю, когда координаты каждого из векторов $⃗u,⃗v$ взаимно просты. Но тогда из равенства $pm =−qn$ получим, что $p =±n,q = ±m$ (действительно, из этого равенства следует, что $p$ делится на $n$ и, в то же время, $n$ делится на $p,$ значит, $p =±n;$ аналогично, $q = ±m,$ с учетом знака в данном равенстве). В этом случае стороны прямоугольника $OBCD$ равны: $|OD|= ∘p2-+q2 = √n2+-m2 =|OB|,$ и наш прямоугольник квадрат.

Ошибка.
Попробуйте повторить позже

Задача 13#77039

На клетчатой плоскости нарисован целый выпуклый многоугольник $F.$ Ни одна из его сторон не идёт по вертикали или горизонтали. Докажите, что сумма длин вертикальных отрезков линий сетки, заключённых внутри $F,$ равна сумме длин горизонтальных отрезков линий сетки внутри $F.$

Показать доказательство

Докажем, что каждая из рассматриваемых величин равна площади многоугольника $F.$ Проверим это для суммы длин горизонтальных отрезков. Проведём эти отрезки. Тогда $F$ разобьётся на два треугольника и несколько трапеций, причём высоты этих фигур будут равны $1.$ Осталось выразить площади этих фигур через основания и высоты по известной формуле и сложить. Видно, что каждый горизонтальный отрезок войдёт в сумму два раза, то есть с коэффициентом единица, что и требовалось.

Ошибка.
Попробуйте повторить позже

Задача 14#77040

На клетчатой плоскости отмечены узлы клетчатого прямоугольника $50× 100$ (всего отмечено $51×101$ узлов). Множество параллельных прямых называется удачным, если на каждой из прямых этого множества лежит хотя бы один отмеченный узел и каждый отмеченный узел лежит на прямой этого множества. Дано удачное множество из $2399$ прямых, параллельных некоторой прямой $ℓ.$ Найдите количество элементов в множестве удачных прямых, перпендикулярных $ℓ.$

Показать ответ и решение

Заметим, что какая-то прямая пересекает прямоугольник хотя бы по двум точкам. Тогда угловой коэффициент всех прямых рационален. Не нарушая общности, можно считать, что он положителен (иначе можно просто сделать симметрию относительно оси ординат). Пусть он равен $p∕q,$ где $p,q$ — натуральные числа, и $(p,q)= 1.$ Обозначим через $li$ количество прямых из нашего множества, которые пересекают прямоугольник ровно по $i$ целым точкам. Тогда нам известно, что $l1+ l2+ ...= 2399.$ Мы знаем, что $5151 =l1+ 2l2+ 3l3+ ....$ Заметим, что если прямая проходит через $i$ целых точек прямоугольника, то она проходит ровно через $i− 1$ пару соседних целых точек прямоугольника (то есть точек $(x1,y1),(x2,y2)$ таких, что $y2− y1 = p$ , $x2 − x1 = q$ ). Заметим, что всего таких пар точек в нашем прямоугольнике ровно $(51− p)(101− q)$ (можно считать, что меньшая сторона прямоугольника параллельна оси ординат). Но с другой стороны из нашего наблюдения следует, что их ровно $l2+2l3+3l4+....$ Тогда имеем равенства

l1+2l2+3l3+ ...= 5151

l2+ 2l3+ 3l4+ ...= (51− p)(101− q)

вычитая равенства, получаем, что

l1+l2+ l3+ ...= 2399 =5151− (51− p)(101− q)

откуда $(51− p)(101− q)=2752= 26⋅43,$ причем $p< 51$ и $q < 101.$ Тогда возможны варианты $101− q =64,51− p =43$ или $101− q = 86,51− p= 32.$ Тогда либо $p= 8,q =37$ или $p= 19,q = 15.$ По аналогичным соображениям мы знаем, что количество прямых в удачном множестве, перпендикулярном данному, равно $5151− (51− q)(101 − p).$ Тогда в множестве может быть либо $5151− 14⋅50 =4451$ прямых, либо $5151 − 36⋅82= 2199$ прямых.

Ответ:

$4451$ или $2199$ прямых

Ошибка.
Попробуйте повторить позже

Задача 15#71903

Прямая $l$ на координатной плоскости не параллельна осям координат. При каком наименьшем $d$ можно утверждать, что расстояние от некоторой точки с целыми координатами до прямой $l$ не превосходит $d?$

Источники: СпбОШ - 2018, задача 11.1(см. www.pdmi.ras.ru)

Показать ответ и решение

Прямая $l$ образует с одной из осей координат угол, не превосходящий $45∘,$ поскольку сумма углов между прямой $l$ и осями координат равна $∘ 90.$ Пусть для определённости угол с осью абцисс не превосходит $∘ 45 ,$ обозначим его через $α.$ Нарисуем сетку, образованную прямыми $x= n$ и $y = n$ при всех целых $n.$ Она разбивает плоскость на единичные квадратики. Рассмотрим квадратик, который пересекает прямая $l.$ Тогда она пересекает одну из горизонтальных сторон. Их точка пересечения $A$ делит сторону на две части. Рассмотрим меньшую из них, соответствующую ей вершину квадратика обозначим через $C.$

$PIC$

Тогда $AC ≤ 12.$ Расстояние от точки $C$ до прямой $l$ равно длине перпендикуляра, опущенного из точки $C$ на $l,$ значит, оно равно $AC sinα ≤ 12sin45∘ =-1√-. 2 2$

Легко видеть, что расстояние от любой точки с целыми координатами до прямой $y = x+ 12$ не меньше $-1√-. 2 2$ Этот пример подтверждает точность полученной оценки.

Ответ:

при $d = √1- 2 2$

Ошибка.
Попробуйте повторить позже

Задача 16#111173

В выпуклом многоугольнике на плоскости содержится не меньше $m2+ 1$ точек с целыми координатами. Докажите, что в нём найдутся $m + 1$ точек с целыми координатами, которые лежат на одной прямой.

Источники: Всеросс., 2002, РЭ, 10.2(см. math.ru)

Подсказки к задаче

Подсказка 1

Ясно, что надо использовать принцип Дирихле. Попробуем использовать пары остатков по модулю m. Всего таких m². Какой вывод можно сделать?

Подсказка 2

Точно! Найдутся две пары остатков, в которых первые и вторые компоненты сравнимы по модулю m. То есть можно найти в многоугольнике пары (x,y), (z,w) такие, что (x-z) и (y-w) делятся на m. Как теперь получить нужное количество точек на прямой?

Показать доказательство

По принципу Дирихле среди $m2 +1$ точек с целыми координатами найдутся такие две точки $(k,l)$ и $(k,l), 1 1$ что $k≡ k m 1$ и $l≡ l. m 1$ Тогда точки

( (k1− k)i (l1− l)i) k +---m---,l+---m-- , 0≤ i≤m

имеют целые координаты и лежат на одном отрезке между точками $(k,l)$ и $(k1,l1).$


0	1	2	3	4	5	6	7	8	9	0

7	8	9	0	1	2	3	4	5	6	7

4	5	6	7	8	9	0	1	2	3	4

1	2	3	4	5	6	7	8	9	0	1

8	9	0	1	2	3	4	5	6	7	8

5	6	7	8	9	0	1	2	3	4	5

2	3	4	5	6	7	8	9	0	1	2

9	0	1	2	3	4	5	6	7	8	9

6	7	8	9	0	1	2	3	4	5	6
3	4	5	6	7	8	9	0	1	2	3

0	1	2	3	4	5	6	7	8	9	0


0	1	2	3	4	5	6	7	8	9	0

7	8	9	0	1	2	3	4	5	6	7

4	5	6	7	8	9	0	1	2	3	4

1	2	3	4	5	6	7	8	9	0	1

8	9	0	1	2	3	4	5	6	7	8

5	6	7	8	9	0	1	2	3	4	5

2	3	4	5	6	7	8	9	0	1	2

9	0	1	2	3	4	5	6	7	8	9

6	7	8	9	0	1	2	3	4	5	6
3	4	5	6	7	8	9	0	1	2	3

0	1	2	3	4	5	6	7	8	9	0


0	1	2	3	4	5	6	7	8	9	0

7	8	9	0	1	2	3	4	5	6	7

4	5	6	7	8	9	0	1	2	3	4

1	2	3	4	5	6	7	8	9	0	1

8	9	0	1	2	3	4	5	6	7	8

5	6	7	8	9	0	1	2	3	4	5

2	3	4	5	6	7	8	9	0	1	2

9	0	1	2	3	4	5	6	7	8	9

6	7	8	9	0	1	2	3	4	5	6
3	4	5	6	7	8	9	0	1	2	3

0	1	2	3	4	5	6	7	8	9	0