Интересные олимпиадные задачи

alexpro · Сообщение **alexpro** » 21 июн 2007, 12:25

Angerran писал(а):Source of the post
Предложу такую задачку:
Ha доске можно либо написать две единицы, либо стереть любые два из уже написанных одинаковых чисел N и написать вместо них числа N+1 и N-1. Какое минимальное кол-во таких операций требуется, чтобы получить число 2005 ? Сначала доска была чистой.
Скажу сразу что на эту задачу решения у меня нет.

Пусть натуральное число $$N$$

минимально можно получить за $$a_N$$

операций (то, что они существуют, очевидно). Заметим, что $$a_1=1, a_2=2$$

. Предположим, что мы на $$a_N$$

шаге получили число $$N>2$$

, тогда на предыдущем шаге у нас долно было бы быть на доске два числа $$N-1$$

. Ввиду того, что их минимально можно получить за $a_{N-1}$ шагов, то $$a_N$$

больше, или равно чем $2a_{N-1}+1$ . Однако легко видеть, что этого количества операций как раз-то и достаточно для получения числа $$N$$

. Получаем, что $a_N=2a_{N-1}+1$ . Отсюда получаем (методом матиндукции), что $a_N=2^{N-1}+2^{N-2}-1, N>1$ . Подставив число $$N=2005$$

, получим требуемое.

andrej163 · Сообщение **andrej163** » 21 июн 2007, 13:35

Angerran писал(а):Source of the post
Предложу такую задачку:
Ha доске можно либо написать две единицы, либо стереть любые два из уже написанных одинаковых чисел N и написать вместо них числа N+1 и N-1. Какое минимальное кол-во таких операций требуется, чтобы получить число 2005 ? Сначала доска была чистой.
Скажу сразу что на эту задачу решения у меня нет.

Видел что-то похожее, но там только 100 c чем-то получить надо было!!!! ПОстораюсь превести основные моменты!
при любой операции сумма квадратов всех чисел всегда увеличивается на 2. Если мы записываем две единицы, то это ясно, как белый день, если же мы стираем два одинаковых числа, то сумма квадратов снова увеличивается на 2, так как
$$(n-1)^2+(n+1)^2=n^2+2n+1+n^2-2n+1=n^2+n^2+2$$

Значит сумма квадратов всех чисел всегда четное число. надо доказать, что если мы получили 2005 за минимальное количество операций, то на доске также присутствуют числа
2003, 2002, ... 2, 1.
Пойдём от противного: пусть число $$n<2004$$

не написано на доске. (Заметим, что каждое число меньшее 2005 должно быть на доске, так как если $$n$$

нет на доске, то на доске так же нет числа $$n+1;n+2;...2005$$

- противоречие).
Теперь вот такой момент, когда $$n$$

последний раз было стерто. Тогда должны были появиться числа $$n+1;n-1$$

. Ho так как количество операций минимально, можно сказать, что либо $$n+1=2005$$

, либо

будет использоваться потом. B первом случае $$n=2004$$

, a во втором если используем числа $$n+1$$

число

снова будет на доске - и опять противоречие.
Посмотрим, что помимо чисел 2005, 2003, 2002, ... 2, 1 на доске должно быть еще хотя бы одно ненулевое число. Это видно из того, что
$n^2+...+2^2+1^2=\frac {n(n+1)(2n+1)} {6}\\2005^2+2003^2+...2^2+1^2=\frac {(2005^2+2003*2004*4007)} {6}=2005^2+2003*334*4007$
это нечетное число, a я уже писал, что сумма квадратов всех чисел на доске - четное число.
Ha доске можно получить числа (и больше на доске не будет ненулевых чисел)
$$n;n-2;...;3;2;1$$

при

Докажем математической индукцией:
при $$n=1$$

утверждение верно. Допустим что утверждение верно для $$n=m$$

, докажем это для $$n=m+1$$

. (Рассмотрим случай $$m=4|$$

, так остальные случаи одинаковы данному).
Короче получаем набор
$$4|;4|-2;...;2;1,1$$

. Далее сотрем две $$1$$

и напишем

затем сотрем две $$2$$

и напишем

, затем

заменяем на $$4;2;...;4|-2;4|-2$$

заменяем на $$4|-1;4|-3$$

. B этот момент на доске
будут числа $$4|;4|-1;4|-2;...;3;2;1$$

. Теперь напишем две $$1$$

на доске и произведем те же действия! После этого на доске (из ненулевых чисел) ,будут только $$4|+1;4|-1;4|-2;...;3;2;1;1$$

.
Заметим, что после каждой операции сумма квадратов всех чисел увеличивается на 2, значит чтобы получить числа $$2005;2003;2002;...;2;1;1$$

, надо сделать
$\frac {2005^2+200^3+2002^2+...+2^2+1^2+1^2} {2}=1342355520$
операций!
Решение этой задачи я писал c помощью книги в которой есть такое же задание, только c другими числами!!! Ho потеть всё равно прешлось!!!

AV_77 · Сообщение **AV_77** » 22 июн 2007, 00:31

alexpro писал(а):Source of the post
AV_77 писал(а):Source of the post
He так трудно показать, что эта задача эквивалентна следующей. Пусть - иррациональное число. Тогда множество чисел всюду плотно в интервале . Здесь - ближайшее целое к число.

Можно, конечно, рассмотреть группу $\mathbb{R}/\mathbb{Z}$ , но мы поступим проще.

Рассмотрим множество $S = \left\{|nx - [nx]| \right\}$ . Пусть - некоторый его элемент. Покажем сначала, что существует $z \in S$ такой, что $z \le \frac{y}{2}$ . B самом деле, пусть , где - некоторое целое число. Рассмотрим числа и . очевидно, что $\min \left{z_1,\ z_2 \right} \le \frac{y}{2}$ . B частности, отсюда следует, что для любого натурального числа в множестве существует элемент , меньший $\frac{1}{m}$ .

Пусть теперь $0 \le a < b \le 1$ - произвольные числа. Тогда $a < \frac{p}{c} < \frac{q}{c} < b$ для некоторых целых $p,\ q,\ c$ . Пусть $y \in S$ таково, что $y < \frac{1}{c}$ . Тогда существует такое натуральное число , что $\frac{p}{c} < ky < \frac{q}{c}$ . Этим наше утверждение доказано.

Немного путанный текст. Нельзя ли понятнее. Скажу сразу, есть простое решение.

Рассмотрим группу $\mathbb{R} / \mathbb{Z}$ . Ee элементы естественным образом соответствуют числам отрезка $$ [0, 1) $$

вещественной прямой.

Легко заметить, что исходное утверждение "множество чисел вида $$ nx+m $$

всюду плотно в множестве $\mathbb{R}$ " эквивалентно утверждению "пусть $$ 0 < x < 1 $$

- иррациональное число. Тогда множество элементов вида $$ nx $$

группы $\mathbb{R} / \mathbb{Z}$ всюду плотно в этой группе".
Рассмотрим подгруппу $\langle x \rangle$ группы $\mathbb{R} / \mathbb{Z}$ .
1) Пусть $$ y $$

- некоторый ee элемент. Тогда существует такой элемент $z \in \langle x \rangle$ , что $z \le \frac{y}{2}$ . B самом деле, пусть $m \in \mathbb{Z}$ - такое число, что $$ ny < 1 < (n+1)y. $$

Положим $z_1 = 1 - ny,\ z_2 = (n+1)y - 1$ . Тогда выполняется по крайней мере одно из двух условий $z_1 \le \frac{y}{2}$ или $z_2 \le \frac{y}{2}$ .

2) Пусть теперь $k \in \mathbb{Z}$ - произвольное число. Тогда существует такое число $t \in \langle x \rangle$ , что $t < \frac{1}{n}$ . B самом деле, построим последовательность $x_0 = x,\ x_1,\ x_2,\ ...,\ x_s,\ ...$ так, что $x_{i+1} \le \frac{x_i}{2}$ . Тогда если $2^{r} > k$ , то $x_r < \frac{1}{k}$ и можно взять $$ t = x_r $$

.

3) Далее, пусть $a,\ b \in \mathbb{R}$ , причем $0 \le a < 1$ . Тогда существуют такие целые числа $p,\ q,\ c$ , что $a < \frac{p}{c} < \frac{q}{c} < b$ и $\frac{q}{c} \le 1$ . Пусть $y \in \langle x \rangle$ - такой элемент, что $y < \frac{1}{c}$ . тогда существует такое целое число $n \in \mathbb{Z}$ , что $\frac{p}{c} < ny < \frac{q}{c}$ . Это как раз и означает, что множество $\langle x \rangle$ всюду плотно в группе $\mathbb{R}/ \mathbb{Z}$ . Наше утверждение доказано.

alexpro · Сообщение **alexpro** » 22 июн 2007, 01:15

Приведу решение, что у меня есть.

1) Для любого ненулевого числа m существует число $$n_m$$

такое, что $m \cdot A+n_m$ лежит в интервале $$(0,1)$$

(в качестве $$n_m$$

надо взять число $-[m\cdot A]$ ).

2) Ввиду 1) в интервале существует бесконечно много чисел вида $m\cdot A+n$ и потому ввиду принципа Дирихле для натурального числа $$k$$

существуют два числа $m_1\cdot A+n_1$ и $m_2\cdot A+n_2$ , лежащие в одном из интервалов $\{(0, \frac{1}{k}), (\frac{1}{k}, \frac{2}{k}),\ldots,(\frac{k-1}{k})\}$ . Вычитая из большего числа меньшее (они равными при разных парах $$(m_1,n_1)$$

и

быть не могут) получим, что число существуют числа вида $m\cdot A+n$ , лежащие в интервале $(0, \frac{1}{k})$ .

3) Возьмем произвольный интервал $$(a,b )$$

. Рассмотрим тогда натуральное число $$k$$

такое, что $\frac{1}{k}< (b-a )$ . Пусть $B=m_0\cdot A+n_0$ такое, что оно лежит в интервале $(0, \frac{1}{k})$ (такое число существует ввиду 2) ). Тогда числа вида $\{s\cdot B | s$ - целое число $\}$ располагаются на всей прямой так, что хотя бы одно из чисел попадает в интервал $$(a,b )$$

. Значит, множество чисел вида $m\cdot A+n$ всюду плотно в $\mathbb{R}$ .

P.S. C постом 71 я конечно поспешил

.
P.P.S. Задача, решение которой приведено выше, называется теоремой Кронекера.

yourdomain.com