Объявляю конкурс на самую сложную олимпиадную задачу

[zZoMROT]

serega57 в сообщении #365771 писал(а):

-- Вс окт 24, 2010 18:52:44 --

Задача 2 Задан произвольный произвольный отрезок постройте окружность с периметром равным данному отрезку.

-- Вс окт 24, 2010 18:58:19 --

пусть нам дан отрезок $P$
$P=2 \pi R$ => $R = \frac{P}{2\pi}$
разумеется, ни при каком $P$ такое $R$ не найти, ибо нельзя найти отрезок длиною $\pi$, при данном единичном и наоборот, доказательством чего является квадратура круга (в противном случае она разрешалась бы)

Да и остальные две задачки, походу, оттуда (из задач древности) вытекают и также не разрешимы

[zhoraster]

serega57, читайте правила форума!

[ins-]

Dear moderators/site admins. I think the idea for the "конкурс на самую сложную олимпиадную задачу" is very good. I understood Russian but if I should use it there will be for more comic situations if I use English. It is the reason I'm posting in English and don't follow the rules on the forum.

Предупреждение за оффтопик. А использование английского языка разрешено правилами форума.

[ha]

None of the school students except me was able to solve this problem yet.

Suppose that $a^n-1$ is divisible on $b^n-1$ for all $n\in\mathbb{N}$. Prove that $a=b^k$ for some $k\in\mathbb{Z}$.

Even harder problem.

Suppose that you have a infinite plane divided by square cells. Some cells are filled with soldiers. It is known that for every N in every square NxN there is no more that N empty cells. Proved that you can command each soldier to stay, go left or go down in such way that after their simultaneous movement the plane will be filled by soldiers completely. Cells can't hold more than one soldier.

[svv]

ha в сообщении #382368 писал(а):

Suppose that you have a infinite plane divided by square cells. Some cells are filled with soldiers. It is known that for every N in every square NxN there is no more that N empty cells. Proved that you can command each soldier to stay, go left or go down in such way that after their simultaneous movement the plane will be filled by soldiers completely. Cells can't hold more than one soldier.

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

[maxal]

ha в сообщении #382368 писал(а):

Suppose that $a^n-1$ is divisible on $b^n-1$ for all $n\in\mathbb{N}$. Prove that $a=b^k$ for some $k\in\mathbb{Z}$.

Ага, я уже номинировал эту задачу выше: post356101.html#p356101
Кто-нибудь голоса подсчитывает?

[Sonic86]

ha писал(а):

Suppose that $a^n-1$ is divisible on $b^n-1$ for all $n\in\mathbb{N}$. Prove that $a=b^k$ for some $k\in\mathbb{Z}$.

(Оффтоп)

Хе! Я сначала подумал, что задача сложная

$b^n-1 | a^n-1 \Leftrightarrow a^n \equiv 1 \pmod {b^n-1}$. Сравнение $x^n \equiv 1 \pmod {b^n-1}$ имеет ровно $n$ решений вида $b^{m_n}, 0 \leq m_n<n$, значит $(\forall n) a^n \equiv 1 \pmod {b^n-1} \Leftrightarrow (\forall n)(\exists k_n) a \equiv b^{k_n} \pmod {b^n-1}$. $a= \text{const}$, а при $n \to + \infty$ будет $b^n-1 \to + \infty$, значит, начиная с некоторого $n>n_0$ будет верно $k_n=k= \text{const}$ и $a \equiv b^{k} \pmod {b^n-1}$. Наконец, если $A-B$ делится на сколь угодно большое натуральное число, то $A=B$, отсюда заключаем, что $a=b^k$.

[Руст]

Sonic86 в сообщении #382745 писал(а):

ha писал(а):

Suppose that $a^n-1$ is divisible on $b^n-1$ for all $n\in\mathbb{N}$. Prove that $a=b^k$ for some $k\in\mathbb{Z}$.

(Оффтоп)

Хе! Я сначала подумал, что задача сложная

$b^n-1 | a^n-1 \Leftrightarrow a^n \equiv 1 \pmod {b^n-1}$. Сравнение $x^n \equiv 1 \pmod {b^n-1}$ имеет ровно $n$ решений вида $b^{m_n}, 0 \leq m_n<n$, значит $(\forall n) a^n \equiv 1 \pmod (b^n-1) \Leftrightarrow (\forall n)(\exists k_n) a \equiv b^{k_n} \pmod {b^n-1}$. $a= \text{const}$, а при $n \to + \infty$ будет $b^n-1 \to + \infty$, значит, начиная с некоторого $n>n_0$ будет верно $k_n=k= \text{const}$ и $a \equiv b^{k} \pmod {b^n-1}$. Наконец, если $A-B$ делится на сколь угодно большое натуральное число, то $A=B$, отсюда заключаем, что $a=b^k$.

Нет задача сложнее, чем вы думаете. Хотя и не самая сложная среди предлагавшихся здесь.
Ошибка в том, что при рассмотрении по модулю (не простому) появляются лишние корни. Например, при $n=2$ и $b=4$, $b^2-1=3*5$ произведение двух простых появляются 4 решения вместо 2. Чем больше простых множителей и степень n, тем больше лишних решений.
К тому же все $k_n$ являются решением. Соответственно выбор одного делается не из сравнения по модулю, а из величины а. Исходное а меньше некоторой степени b.

[Sonic86]

Руст, спасибо за подсказку, я понял , буду еще думать тогда...

[Edward_Tur]

Есть несколько квадратов, сумма площадей которых равна $1$. Поместите их без наложений в квадрат площади $2$.

[EtCetera]

Edward_Tur в сообщении #386072 писал(а):

Есть несколько квадратов, сумма площадей которых равна $1$. Поместите их без наложений в квадрат площади $2$.

См. статью "Упаковка квадратов" ("Квант", 1973, №4).

[nnosipov]

Руст в сообщении #382756 писал(а):

Sonic86 в сообщении #382745 писал(а):

ha писал(а):

Suppose that $a^n-1$ is divisible on $b^n-1$ for all $n\in\mathbb{N}$. Prove that $a=b^k$ for some $k\in\mathbb{Z}$.

(Оффтоп)

Хе! Я сначала подумал, что задача сложная

$b^n-1 | a^n-1 \Leftrightarrow a^n \equiv 1 \pmod {b^n-1}$. Сравнение $x^n \equiv 1 \pmod {b^n-1}$ имеет ровно $n$ решений вида $b^{m_n}, 0 \leq m_n<n$, значит $(\forall n) a^n \equiv 1 \pmod (b^n-1) \Leftrightarrow (\forall n)(\exists k_n) a \equiv b^{k_n} \pmod {b^n-1}$. $a= \text{const}$, а при $n \to + \infty$ будет $b^n-1 \to + \infty$, значит, начиная с некоторого $n>n_0$ будет верно $k_n=k= \text{const}$ и $a \equiv b^{k} \pmod {b^n-1}$. Наконец, если $A-B$ делится на сколь угодно большое натуральное число, то $A=B$, отсюда заключаем, что $a=b^k$.

Нет задача сложнее, чем вы думаете. Хотя и не самая сложная среди предлагавшихся здесь.
Ошибка в том, что при рассмотрении по модулю (не простому) появляются лишние корни. Например, при $n=2$ и $b=4$, $b^2-1=3*5$ произведение двух простых появляются 4 решения вместо 2. Чем больше простых множителей и степень n, тем больше лишних решений.
К тому же все $k_n$ являются решением. Соответственно выбор одного делается не из сравнения по модулю, а из величины а. Исходное а меньше некоторой степени b.

Все-таки задача не слишком сложна. Она в какой-то степени даже стандартна. В книге Григорьян А.А., Конягин С.В., Садовничий В.А. Задачи студенческих математических олимпиад. М.: Изд-во МГУ, 1987. таких задач две.

1. Пусть $a>b$ --- взаимно простые натуральные числа, для которых существует предел последовательности дробных частей $\alpha_n=\{(a/b)^n\}$. Тогда $b=1$.

2. Пусть $a \geqslant b>1$ --- такие натуральные числа, что $a^n-1$ делится на $b^n-1$ при любом натуральном $n$. Тогда $a=b^m$, где $m$ --- некоторое натуральное число.

При решении обеих задач можно использовать разностный оператор $\Delta$, ставящий в соответствие последовательности $y_n$ последовательность $by_n-ay_{n-1}$. Очевидно, последовательность $y_n=(a/b)^n$ является решением однородного разностного уравнения

$$ \Delta y_n=0. \eqno(*) $$

Для последовательности $y_n=(a^n-1)/(b^n-1) \sim (a/b)^n$ при любом $m$ справедлива оценка

$$ \Delta^m y_n \asymp (b/a^{m+1})^n, \quad n \to \infty, $$

которую можно доказать, например, индукцией по $m$.

Подставив $y_n=(a/b)^n=[(a/b)^n]+\alpha_n$ в уравнение $(*)$, получим, что

$$ \Delta \alpha_n=c \eqno (**) $$

для всех достаточно больших $n$, где $c$ --- некоторое целое число. Среди решений неоднородного разностного уравнения $(**)$ ограниченными являются только константы, поэтому $\alpha_n=r$ для всех достаточно больших $n$, где $r$ --- некоторое рациональное число. Для таких $n$ имеем

$$ (a/b)^n=[(a/b)^n]+r, $$

что возможно только при $b=1$. Переходя к решению второй задачи, заметим, что если $a^m<b<a^{m+1}$ при некотором $m$, то $\Delta^m y_n \to 0$ при $n \to \infty$. Но тогда, начиная с некоторого $n$, последовательность $\Delta^m y_n$ должна быть нулевой, что, однако, невозможно.

Таким образом, следует лишь подыскать подходящий разностный оператор. Разумеется, всё это приносит успех только тогда, когда некоторое свойство последовательности имеет место при ВСЕХ натуральных $n$.

[glorius_May]

Вот самая сложная: topic40551.html

[Simba]

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

Я считаю достаточно трудная задача. Может кто справится?

[glorius_May]

Найти все целые числа $n$, при каждом из которых все решения уравнения $3x^3 - 3x^2 + n = 0$ являются рациональными.

*не решил ни один из участников олимпиады