М697. Пузатость прямоугольника

Задача

разделение квадрата на прямоугольники

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

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

Будем считать что длина стороны квадрата равна 1. Тогда пусть мы разбили квадрат на n прямоугольников размерами a_k\times b_k причем при всех k a_k\leq b_k

Одно из возможных разбиений квадрата на прямоугольники

тогда:

{\textstyle1\geq b_k\Rightarrow\frac1{b_k}\geq b_k\Rightarrow\frac{a_k}{b_k}\geq a_k\times b_k\Rightarrow\sum_{k=1}^n}\frac{a_k}{b_k}\geq{\textstyle\sum_{k=1}^n}a_k\times b_k=1 (сумма {\textstyle\sum_{k=1}^n}a_k\times b_k является суммой площадей прямоугольников и по свойству площади равна площади квадрата (то есть 1)).

А это значит что:

{\textstyle\sum_{k=1}^n}\frac{a_k}{b_k}\geq1 . А это и значит, что как бы не резать квадрат на прямоугольники, сумма их пузатостей будет не меньше 1.

Что и требовалось доказать.

М1762. Две тысячи делителей

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

Условие

Существует ли натуральное число $n$ такое, что $n$ имеет ровно $2000$ различных простых делителей и $2^n+1$ делится на $n$?

Решение

Докажем по индукции, что для любого натурального $k$ существует натуральное $n_k$, имеющее $k$ различных простых делителей, делящееся на $3$ и такое, что $2^{n_k}+1$ делится на $n_k$.

Для $k=1$ можно взять $n=3$. Пусть число $n_k=n$, кратное $3$, имеет $k$ различных простых делителей, причём $2^n+1$ делится на $n$.

Число $2^{3n}+1=\left(2^n+1\right)\left(2^{2n}-2n+1\right)$ делится на $3n$. Это следует из того, что $2^n+1$ делится на $n$, а
$$2^{2n}-2^n+1=\left(2^n-2\right)\left(2^n+1\right)+3\;\;\;(*)$$ делится на $3$ (поскольку при нечётном $n$ числа $2^n+1$ и $2^n-2$ делятся на $3$).

Далее, число $2^{2n}-2^n+1$ не делится на $9$, поскольку на $9$ делится произведение $\left(2^n-2\right)\left(2^n+1\right)$. Значит, поскольку $2^{2n}-2^n+1>3$ при $n>1$, то это число имеет при $n>1$ простой делитель $p>3$. Так как НОД $\left(2^n+1, 2^{2n}-2^n+1\right)=3$ (это тоже ясно из равенства $(*)$), то $p$ — не делитель $n$.

Из сказанного следует, что число $3pn$ имеет $k+1$ простой делитель, причём $2^{3pn}+1$ делится на $3pn$. Последнее следует, например из равенства
$$\left(2^{3n}\right)^p+1=\left(2^{3n}+1\right)\left(\left(2^{3n}\right)^{p-1}-\left(2^{3n}\right)^{p-2}+\cdots+1\right)$$

Для завершения решения достаточно положить $n_{k+1}=3pn=3pn_k$.

А.Егоров, В.Сендеров

М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 $. Этим всё доказано.

Н. Осипов

M927. Замена пересекающихся отрезков

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

Условие

На плоскости дано конечное множество точек, никакие три из которых не лежат на одной прямой. Проведено несколько отрезков с концами в данных точках. Эти отрезки разрешается менять: если какие-то два из них, AC и BD, пересекаются, их можно стереть и провести

  1. отрезки AB и CD
  2. AB и BC.

(Если «новый» отрезок уже проведён, проводить его второй раз не нужно.)
Можно ли после нескольких таких замен (только по правилу 1 или по правилу 2, но не по обоим) вернуться к исходному набору отрезков?

Решение

  1. Докажем, что через конечное число операций «типа 1» — замены пересекающихся AB и CD — мы придём к конфигурации, в которой уже не будет пересекающихся отрезков.

    Рассмотрим сумму s длин всех отрезков конфигурации. При каждой операции «типа 1» она уменьшается:
    AB + CD < AC + BD (*)
    (для треугольников APB и CPD, где P — точка пересечения AC и BD — рис. 1, выполнены неравенства AB < AP + PB и CD < CP + PD; сложив их, получим (*)).

    рисунок2

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

    Это решение даёт очень грубую верхнюю оценку для максимального количества T_n операций, которое может быть проделано с конфигурацией на n точках — можно сказать лишь что оно меньше числа всех конфигураций, то есть 2^{n\cdot(n-1)/2}, n\cdot(n-1)/2 — это число различных отрезков с концами в данных n точках.

    рис1

    Приведём идею другого решения, дающего значительно лучшую оценку. Рассмотрим произвольное разбиение f данных точек на два непустых множества, каждое из которых лежит целиком по одну сторону от некоторой прямой l. Таких прямых для данного разбиения, конечно, бесконечно много, но одну из них всегда можно получить, повернув по часовой стрелке прямую, соединяющую две какие-либо точки A и B на очень маленький угол вокруг середины отрезка AB (рис. 2); эту прямую обозначим l_i. Число прямых l_i, и значит, что число рассматриваемых «выпуклых» разбиений не превосходит числа пар точек n\cdot(n-1)/2.

    Назовём балансом конфигурации суммарное число b пересечений её отрезков со всеми прямыми l_i; ясно, что 0 \le b \le (n\cdot(n-1)/2)^2. При операции типа 1 число пересечений любой прямой l_i с отрезками конфигурации не увеличивается, а по крайней мере для одной прямой оно уменьшается на 2. Следовательно, T_n \le n^2 \cdot (n-1)^2 / 8. Интересно было бы получить ещё более точную оценку для T_n.

  2. рисунок1Приведём пример, показывающий, что для операции «типа 2» — замены пересекающихся отрезков AC и BD не имеющих общий конец AB и BC — процесс может «зациклиться» и тем самым продолжаться неограниченно. Расположим 18 точек в вершинах правильного 18-угольника и обозначим через D(k, l) конфигурацию из 36 отрезков, в которой каждая из 18 точек соединена k-й и l-й от неё по счёту.

    Чтобы пройти за 54 операции путь D(4, 8) \to D(5, 9) \to D(6, 7) \to D(4, 8) (рис. 3), достаточно каждую из операций, изображенных на рисунке 4, проделать по 18 раз (поворачивая картинку каждый раз на 20^{\circ}).

    По-видимому, существуют и примеры с существенно меньшим числом точек n и длинной цикла T, чем n = 18 и T = 54.

  3. рисунок4

    Н.Б. Васильев, В.Е. Колосов

M1722. Количество целых точек

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

Условие

Пусть a,b — натуральные числа. Проведем через точку (a;b) прямую, отсекающую от первого координатного угла треугольник.
а) Докажите, что количество точек с целыми неотрицательными координатами, которые лежат внутри или на сторонах этого треугольника, больше, чем 2 \cdot a \cdot b + a + b.
б) Докажите, что эта оценка точная: через точку (a;b) можно провести прямую, отсекающую от первого координатного угла треугольник, внутри и на сторонах которого всего 2 \cdot a \cdot b + a + b точек с целыми неотрицательными координатами.

Решение

Рассмотрим прямоугольник OABC с центром в точке P(a;b), и сторонами, параллельными осям координат(рис.1). Внутри и на сторонах этого прямоугольника всего (2 \cdot a + 1) \cdot (2 \cdot b+1) =  4\cdot a \cdot b + 2\cdot a + 2 \cdot b +1 целочисленных точек.
 
method-draw-image (8)
Pис.1
 
Чуть-чуть сдвинем точку A вправо. Через полученную точку A' и точку P проведем прямую до пересечения с осью ординат в точке C'. Если сдвиг был достаточно мал, то в треугольнике OA'C' не появится ни одной точки с целыми координатами, которой не было бы в треугольнике OAC.
При центральной симметрии относительно P любая целочисленная точка прямоугольника OABC переходит в целочисленную точку этого же прямоугольника. Поэтому все отличные от P целочисленные точки прямоугольника разбиваются на пары точек, симметричных относительно P.
Итак, если A' достаточно близка к точке A, то внутри и на границе треугольника OA'C' расположена ровно половина отличных от P целочисленных точек, т.е. 2 \cdot a \cdot b + a + b точек. Вместе с точкой P получаем всего 2 \cdot a \cdot b + a + b + 1 точек. Мы решили пункт б).
 
Теперь займемся пунктом а). Для определенности, пусть прямая отсекает от первого координатного угла треугольник OA_1C_1, где точка A_1 расположена правее точки A(рис.2).
 
method-draw-image (9)
Рис.2
 
Чтобы получить треугольник OA_1C_1 из треугольника OAC, достаточно «отрезать» от последнего треугольник CC_{1}P и добавить треугольник AA_{1}P.
Но при центральной симметрии относительно точки P треугольник CC_{1}P переходит в треугольник, являющийся частью треугольника AA_{1}P(закрашенный на рисунке 2). Целочисленные координаты при этом переходят в целочисленные. Задача решена.