М1787. Диафантово уравнение

Задача из журнала «Квант» (2002 год, 2 выпуск)

Условие

Пусть $ p $ и $ q $ — натуральные числа, большие 1. Известно, что $ q^3-1 $ делится на $ p $, а $ p-1 $ делится на $ q $. Докажите, что $ p = q^{\frac{3}{2}}+1 $ или $ p = q^2 + q + 1 $.

Решение

Будем рассуждать так.
Имеем $ q^3 — 1 = pk $ для некоторого $ k \geqslant 1 $. Так как $ p = 1 \pmod {q}$, то $ k = -1 \pmod {q}$, т.е. $ k = lq-1$ для некоторого $ l \geqslant 1 $. Из равенства $ \displaystyle p = \frac{(q^3-1)}{(lq-1)}$ следует, что $ l < q^2 $, а также то, что числа $ q^2-l $ и $ q-l^2 $ делятся на $ lq-1 $. Предположим теперь, что $ p \neq q^{\frac{3}{2}} + 1$ (в частности, $ l \neq q^{1/2}$). Если $ 1 < l < q, l \neq q^{\frac{1}{2}} $, то $ 0 < \left|q-l^2\right| < lq-1 $ и, следовательно, делимость $ q-l^2 $ на $ lq-1 $ невозможна. Если же $ q \leqslant l < q^2$, то $ 0 < q^2-l < lq-1$ и невозможна делимость $ q^2-l$ на $  lq-1$. Таким образом, $ l = 1$ и $p = q^2 + q + 1 $. Этим всё доказано.

Н. Осипов

M1571. О доске, монете и возможных передвижениях

Задача из журнала «Квант» (1996, №6)

Условие

Дана прямоугольная доска ABCD со сторонами AB=20 и BC=12, разбитая на 20\times12 единичных квадратов. Пусть r — данное положительное целое число. За один ход монету можно передвинуть из одного единичного квадрата в другой в том и только том случае, когда расстояние между их центрами равно \sqrt{r}. Требуется найти последовательность ходов, переводящую монету из единичного квадрата с вершиной A в единичный квадрат с вершиной B.

  1. Докажите, что это невозможно, когда r делится на 2 или на 3.
  2. Докажите, что это можно сделать при r=73.
  3. Можно ли это сделать при r=97?

dim11.svg

Решение

Введем прямоугольную систему координат с началом в точке A и направим оси Ax и Ay вдоль отрезков AB и AD соответственно. Единица длины будет равна стороне единичного квадрата. Нам необходимо найти путь из точки (0;0) в точку (19;0) такой, что для каждого хода (x;y)\rightarrow(x+a,y+b) выполняется равенство a^2+b^2=r^2.
dim2213.svg

Задание №1

Если r чётно, то для каждого целого решения уравнения a^2+b^2=r^2 сумма a+b чётна. Для каждой точки (x;y), в которую можно попасть из (0;0), x+y чётно. Следовательно, в точку (19;0) попасть невозможно.

Задание №2

Один из примеров продвижения монеты из (0;0) в (19;0) при r=73 такой: (0;0)\rightarrow(3;8)\rightarrow(11;5)\rightarrow(19;2)\rightarrow(16;10)\rightarrow(8;7)\rightarrow(0;4)\rightarrow(8;1)\rightarrow(11;9)\rightarrow(3;6)\rightarrow(11;3)\rightarrow(19;0)
dim32.svg

Задание №3

Пусть R=\left\{(i;j);0\leq{i}\leq19,0\leq{j}\leq19\right\}, P=\left\{(i;j);0\leq{i}\leq49,4\leq{j}\leq7\right\}, Q — их разность: Q=R\setminus{P}. Так как число 97 представимо в виде суммы квадратом единственным образом: 9^2+4^2, то каждый ход состоит из одного из векторов (\pm4;\pm9), (\pm9;\pm4). Ход типа (\pm9;\pm4) приводит нас в точку Q из точки из множества P и наоборот, тогда как ход (\pm4;\pm9) не выводит нас из множества Q (заметим, что за один шаг нашими ходами нельзя попасть из точки из P в точку из P). Каждый ход типа (\pm9;\pm4) изменяет чётность x-координаты, поэтому, чтобы попасть из (0;0) в (19;0), требуется нечётное число таких ходов. Каждый такой ход от точки из P в точку из Q и наоборот. Значит после нечётного числа ходов из точки (0;0)\in{Q} попадаем в точку из P, но (19;0)\in{Q}. Поэтому требуемое невозможно.

Д. Терешин

M1231. О разбиении плоскости графиками многочленов второй степени

Условие

На какое наибольшее число частей могут разбить плоскость Oxy графики n квадратных трехчленов вида y=ax^{2}+bx+c (n=1, 2, 3, ...)?

Ответ: n^{2}+1.

Решение

Докажем по индукции, что число частей не превосходит n^{2}+1. Для n=1 это ясно: парабола делит плоскость на две части.
Пусть доказано, что n-1 графиков делят плоскость не более, чем на (n-1)^{2}+1 частей. Проведем последний, n-й график. Он пересекается с каждым из n-1 предыдущих максимум в двух точках, т.е. он будет разбит не более чем на 2(n-1)+1=2n+1 кусков (включая два крайних, уходящих в бесконечность). Каждый из этих кусков параболы делит одну из имеющихся частей плоскости на две. Таким образом, при проведении последней параболы число частей увеличится не более чем на 2n+1, т.е. не превзойдет (n-1)^{2}+1+2n+1=n^{2}+1.
К задаче M1231
Легко строится пример, когда все графики попарно пересекаются в двух точках (см. рисунок) — при этом получится максимальное число частей, указанное в ответе.
Точно такие же образом можно подсчитать максимальное число частей, на которые делят плоскость n прямых, n окружностей и т.п.

Н.Васильев

M1518. Высоты тетраэдра пересекаются в одной точке

Задачи из журнала «Квант» (1995 год, выпуск 5)

Условие

Высоты тетраэдра пересекаются в одной точке. Докажите, что эта точка — основание одной из высот и три точки, делящие другие высоты в отношении 2:1, считая от вершин, лежат на одной сфере.

Доказательство

Пусть M — точка пересечения медиан треугольника ABC, P— точка пересечения высот тетраэдра, AA_{1} — высота тетраэдра из вершины A.

MA_{2}||A_{3}A_{1} и AA_{2}:A_{2}A_{1}=2:1.

Угол MA_{2}P — прямой, так что точка A_{2} лежит на сфере с диаметром MP. Аналогично рассматриваются остальные случаи.

Д.Терешин

M1515. О целых корнях суперпозиции трех квадратных трехчленов

Задача из журнала «Квант» (1995 год, выпуск 5)

Условие

Известно, что f(x),g(x),h(x) — квадратные трехчлены. Может ли уравнение f(g(h(x)))=0 иметь корни 1, 2, 3, 4, 5, 6, 7 и 8?

Решение

Предположим, что числа 1, 2, 3, 4, 5, 6, 7 и 8 — корни уравнения f(g(h(x)))=0.

Если прямая x=a — ось параболы, задаваемой уравнением y=h(x), то h(x_{1})=h(x_{2}) тогда и только тогда, когда x_{1}+x_{2}=2a.

Многочлен f(g(x)) имеет не более четырех корней, но числа h(1), h(2),..., h(8) являются его корнями, следовательно, a=4.5 и h(4)=h(5),h(3)=h(6),h(2)=h(7),h(1)=h(8). Кроме того, мы попутно доказали, что числа h(1),h(2),h(3),h(4) образуют монотонную последовательность. Аналогично, рассматривая трехчлен f(x) и его корни g(h(1)), g(h(2)), g(h(3)), g(h(4)), получаем, что h(1)+h(4)=2b, h(2)+h(3)=2b, где прямая x=b — ось параболы, задаваемой уравнением y=g(x). Но из уравнения h(1)+h(4)=h(2)+h(3) для h(x)=Ax^{2}+Bx+C следует, что A=0. Противоречие.

Ответ: уравнение f(g(h(x)))=0 не может иметь корни 1, 2, 3, 4, 5, 6, 7 и 8.

С.Токарев