Деление с остатком

[dnoskov]

Докажите, что среди 35 натуральных чисел найдётся хотя бы два, разность которых делится на 34.

Я дошёл вот до чего (т.е. по-сути ни до чего):

Заметим, что 34 - наибольший остаток при делении на 35. Тогда имеем 35 чисел вида: $35k+r$, где $k\in \mathbb{N}\cup\{0\}, \: r\in \{0, 1, 2, 3, \ldots, 32, 33, 34\}, k=0\Rightarrow r\ne 0$.
Дальше думаю, что могу ошибаться, но тем не менее:
Пусть $35k_1+r_1 > 35k_2+r_2$, тогда: $35k_1+r_1-35k_2-r_2=35(k_1-k_2)+(r_1-r_2)=34(k_1-k_2)+(k_1-k_2)+(r_1-r_2)$
Дальше, наверное, нужно как-то доказать, что среди этих 35 чисел обязательно есть такие два, что $(k_1-k_2)+(r_1-r_2)$ делится на 34, т.е. задача даже не упростилась.

Как здесь быть-то? Подскажите, пожалуйста.

ЗЫ. Или *может быть* есть опять какое-то молчаливое разумение по поводу, например, того, что эти числа последовательные.
ЗЗЫ. Это я себя успокаиваю. На самом деле я пробовал для 5 чисел и деления на 4. Для 3 и 2 это получается автоматически.

[Jnrty]

Рассмотрите остатки од деления заданных чисел на 34.
Можно ли посадить 35 кроликов в 34 клетки так, чтобы в каждой было по одному?

[dnoskov]

Jnrty
Нет. Но я не понимаю, как те два кролика, которые окажутся в клетке вдвоём будут друг из друга вычитаться.


Мне не ясно, как мне их рассматривать. Т.е. если вдруг окажется, что остаток от деления на 34 у всех этих чисел одинаковый, пусть даже 3, тогда делимость разности любых двух из них на 34 зависит от $k_1$ и $k_2$.

[ИСН]

Очень просто: минус между ними поставят, они и будут.
Понятно ли, какой воспоследует результат, вернее, какой у него остаток?

[Алексей К.]

dnoskov в сообщении #379238 писал(а):

Тогда имеем 35 чисел вида: $35k+r$, где ...

Мне кажется, что лучше поиметь 35 чисел вида: $34k+r$. И тогда с кроликами наступит ясность.

-- 22 ноя 2010, 22:31 --

Ну, собственно, это Jnrty и предложил выше...

[dnoskov]

Алексей К.
$34k + r$?

Прошу прощения. Я отталкивался от указания, данного в задачнике, а именно: "Указание. Представьте каждое из 35 чисел в виде $35k+r$ и заметьте, что $r$ может принимать 35 различных значений: $0; 1; \ldots; 34$."

Это неверное указание? (здесь я вовсе не ссылаюсь на авторитет задачника, просто в этом задачнике ошибка на ошибке (уже не пишу "опечатка"))

[ИСН]

Сами-то как думаете? Какой вид нам обещает более приятный исход?

[dnoskov]

ИСН
Ну... наверное $34k + r$, раз мы собрались на 34 делить.

А раз $34k+r$, тогда поджжите секундочку...

[Алексей К.]

dnoskov в сообщении #379257 писал(а):

Указание. Представьте каждое из 35 чисел в виде $35k+r$ и заметьте, что $r$ может принимать 35 различных значений: $0; 1; \ldots; 34$."

Это неверное указание?

Я опять залез не в свою епархию; и уж о верности-неверности указания судить не буду.
Просто мне показалось, что если представить каждое из 35 чисел в виде $34k+r$ и заметить, что 35 $r$-ов могут принимать только 34 различных значения, то два кролика непременно попадут в одну клетку (а то и более)... Их мы и возьмём за уши для дальнейшего исследования.

[dnoskov]

$34k_1+r_1-34k_2-r_2=34(k_1-k_2)+(r_1-r_2)$, где $-33 \leqslant r_1-r_2 \leqslant 33$

Тогда получается, что утверждение верно только при $r_1=r_2$? А если у нас нету чисел с $r_1=r_2$?

-- Вт ноя 23, 2010 01:13:23 --

Но Алексей К. всю мою боль разрешил.

[Алексей К.]

Но тогда у нас есть $r_9=r_{23}$ или $r_{17}=r_{30}$ или $r_5=r_6=r_{20}$, или... Ну те, что в одной клетке (клетки пронумерованы).

[dnoskov]

Алексей К.
Да, это ошибка в задачнике. В УКАЗАНИИ к решению. Я определённо напишу книгу "Ошибки Звавича, Мордковича и остальных там"

Благодарю Вам.

[dnoskov]

Вот... опять сомневаюсь

Докажите, что существуют такие различные натуральные числа $n$ и $k$, что разность $573^n-573^k$ делится на 2001.

Здесь, наверное, вот так надо:
Если $573^n-573^k$ делится на $2001$, то:
$573^n=2001\cdot q_1 + r_1$, $573^k=2001\cdot q_2+r_2$, где $r_1=r_2$, тогда имеем: $573^n-573^k=2001(q_1-q_2)$.

Но ведь это не доказывает существование пары $n, k$? Т.е. я здесь вообще-то исхожу, как мне кажется, из того, что мне нужно доказать, а не из ограничений, накладываемых на $n$ и $k$. Кроме того, получается, что вместо 2001 можно вообще тогда что угодно подставить.

Подскажите, пожалуйста, насколько я неправ?

-- Ср ноя 24, 2010 15:04:11 --

Или, вообще-то, я пришёл к тому, что мне нужно доказать существование равных остатков при делении на $2001$ для чисел $573^n$ и $573^k$? Но как это сделать?

[Sonic86]

Здесь надо взять $k=0$ (ну или вынести $573^k$ за скобку - один результат будет) и $n= \varphi (2001)$. Или Вам так нельзя еще?

dnoskov писал(а):

Здесь, наверное, вот так надо:
Если $573^n-573^k$ делится на $2001$, то:
$573^n=2001\cdot q_1 + r_1$, $573^k=2001\cdot q_2+r_2$, где $r_1=r_2$, тогда имеем: $573^n-573^k=2001(q_1-q_2)$.

Но ведь это не доказывает существование пары $n, k$?

не доказывает. Просто необходимое условие выписали

dnoskov писал(а):

Или, вообще-то, я пришёл к тому, что мне нужно доказать существование равных остатков при делении на $2001$ для чисел $573^n$ и $573^k$? Но как это сделать?

Да, правильно.
Сколько возможно разностей? А сколько остатков? Следовательно...

[dnoskov]

Sonic86

Цитата:

Или Вам так нельзя еще?

Та что ви. Не более элементарной математики 8 кл.

Цитата:

Сколько возможно разностей?

• Безконечно много. (да, я знаю, это беЗ... обращает на себя внимание, но оно имеет смысл, в отличие от беС..)
  
• Или Вы имеете в виду разностей остатков от деления каждого из них, т.е. $573^n$ и $573^k$ на $2001$?
  $-2000 \leqslant r_1-r_2 \leqslant 2000$, т.е. $4001$

Цитата:

А сколько остатков?

2000 разных остатков.

...Ой, т.е. 2001, включая 0.

Цитата:

Следовательно...

• Среди безконечного множества разностей обязательно найдётся такая, что $r_1-r_2=0$? Не факт же...
• Среди $4001$ возможных разностей остатков обязательно встретится $0$? Опять же, почему обязательно?

-- Ср ноя 24, 2010 16:24:54 --

т.е. среди $4001$ возможного варианта $0$, конечно же встретится, но почему он должен встретиться среди всех $573^n-573^k$?