Задача о 100 медвежатах

[Xenia1996]

Есть одна довольно известная задача:

На поляне 100 медвежат. У каждого в лапках - кадочка с натуральным числом граммов мёда. Массы всех кадочек попарно различны. Возможна ли ситуация, при которой масса всего мёда делится на массу мёда в каждой из кадочек, уменьшенную на 1 грамм?

-- Пн фев 14, 2011 19:11:24 --

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

[Руст]

Обозначим через $S=\sum_i x_i$ общее количество меда и через $k_i=\frac{S}{x_i-1}$ соответствующие разные числа (разные, так как $x_i$ разные). Тогда на $S$ и $k_i$ получаем уравнение:

$$S(1-\sum_i \frac{1}{k_i})=100.$$

Как получать более менее общие решения таких соотношений тут недавно обсуждалось. Поэтому не буду повторяться. Простейший способ взять $k_1=2$ и рекурентно $k_n=1+\prod_{i<n}k_i$. Взяв $S=100*\prod_i k_i$ получаем одно из решений.

[Xenia1996]

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

Обозначим через $S=\sum_i x_i$ общее количество меда и через $k_i=\frac{S}{x_i-1}$ соответствующие разные числа (разные, так как $x_i$ разные). Тогда на $S$ и $k_i$ получаем уравнение:

$$S(1-\sum_i \frac{1}{k_i})=100.$$

Как получать более менее общие решения таких соотношений тут недавно обсуждалось. Поэтому не буду повторяться. Простейший способ взять $k_1=2$ и рекурентно $k_n=1+\prod_{i<n}k_i$. Взяв $S=100*\prod_i k_i$ получаем одно из решений.

Общего решения, как у Вас, я, конечно, не нашла, но решила вот так.

[age]

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

Простейший способ взять $k_1=2$ и рекурентно $k_n=1+\prod_{i<n}k_i$. Взяв $S=100*\prod_i k_i$ получаем одно из решений.

А я вот что-то не совсем понял здесь. Берём $k_1=2$, тогда $k_2=1+2=3$, $k_3=1+2\cdot3=7$, $k_4=1+2\cdot3\cdot7$ Так что ли?

-- Пн фев 14, 2011 22:12:15 --

Xenia1996 в сообщении #413015 писал(а):

Общего решения, как у Вас, я, конечно, не нашла, но решила вот так.

Сам я не решил, но Ваше решение подсмотрел , и у меня возник вопрос, а есть ли другие решения?

(Оффтоп)

(вообще задачка интересная, хоть бинарная арифметика там прямо и проклёвывается, но недосмотрел, несмотря на то что вряд ли можно себе представить кадочку с $\dfrac{2^nn}{2}$ граммами мёда)

В частности для случая $n=3$ у вас получилось $24=13+7+4$, хотя есть меньшее решение $12=5+4+3$

[Xenia1996]

age в сообщении #413045 писал(а):

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

Простейший способ взять $k_1=2$ и рекурентно $k_n=1+\prod_{i<n}k_i$. Взяв $S=100*\prod_i k_i$ получаем одно из решений.

А я вот что-то не совсем понял здесь. Берём $k_1=2$, тогда $k_2=1+2=3$, $k_3=1+2\cdot3=7$, $k_4=1+2\cdot3\cdot7$ Так что ли?

-- Пн фев 14, 2011 22:12:15 --

Xenia1996 в сообщении #413015 писал(а):

Общего решения, как у Вас, я, конечно, не нашла, но решила вот так.

Сам я не решил, но Ваше решение подсмотрел , и у меня возник вопрос, а есть ли другие решения?

(Оффтоп)

(вообще задачка интересная, хоть бинарная арифметика там прямо и проклёвывается, но недосмотрел, несмотря на то что вряд ли можно себе представить кадочку с $\dfrac{2^nn}{2}$ граммами мёда)

-- Пн фев 14, 2011 22:24:15 --

В частности для случая $n=3$ у вас получилось $24=13+7+4$, хотя есть меньшее решение $12=5+4+3$

В принципе, слова "уменьшенное на единичку" можно заменить на "уменьшенное на фиксированное целое неотрицательное число", тогда интересней получится, но ответ всё равно будет "да".

-- Пн фев 14, 2011 21:38:15 --

В самом общем виде задача формулируется так:

Доказать, что для любых натуральных n и m существуют n попарно различных натуральных чисел таких, что их сумма делится на каждое из них, уменьшенное на m.

Пример для $n=5; m=3$:

$32\cdot15=480=243+123+63+33+18$

[age]

Не, ну это тривиально. Формула-то та же. А я имел в виду, существуют ли другие решения. Не по этой формуле.

[Руст]

age в сообщении #413080 писал(а):

Не, ну это тривиально. Формула-то та же. А я имел в виду, существуют ли другие решения. Не по этой формуле.

Решений много. Здесь я приводил как можно продолжать многими способами. Во первых надо привести к виду:

$$\sum_{i=1}^m \frac{1}{k_i}+\frac{100}{S}=1.$$

Фактический мы рассматривали только случай $S=100\prod_i k_i$. Это существенно ограничивает.
Наряду с ним рассмотрим уравнение

$$\sum_{i=1}^l\frac{1}{y_i}=1$$

и удлиним длину предыдущего решения взяв $k_i=k_i,i<m, k_{m+i}=k_m*y_{i+1},i=0,1,..l-1$.
Можно вместо $k_m$ менять сумму $S$ таким же образом $k_{m+i}=100y_iS,i=1,...,l-1, S'=y_lS$.
Можно попарно умножать и т.д. Такие операции здесь уже ранее обсуждали.

[age]

Руст
А для 10 на числах найти сможете? И скажем так: наибольший интерес представляет минимальная из таких последовательностей, т.е. там где будут наиболее удобные горшочки для мёда.

[Руст]

age в сообщении #413389 писал(а):

Руст
А для 10 на числах найти сможете? И скажем так: наибольший интерес представляет минимальная из таких последовательностей, т.е. там где будут наиболее удобные горшочки для мёда.

Может не самое малое решение:
$k_i=(3,4,6,10,12,24,30,40,60,80),S=480, x_i=\frac{S}{k_i}+1.$

[age]

Если я правильно понял, искомые числа у Вас находятся как $x_i=\dfrac{480}{k_i}+1$. Тогда для предложенных $k_i$ у меня получилось $x_i=\{7,9,13,17,21,41,49,81,121,161\}$. Но в данном случае $S=\sum{x_i}=520\neq480$

[Руст]

age в сообщении #413449 писал(а):

Если я правильно понял, искомые числа у Вас находятся как $x_i=\dfrac{480}{k_i}+1$. Тогда для предложенных $k_i$ у меня получилось $x_i=\{7,9,13,17,21,41,49,81,121,161\}$. Но в данном случае $S=\sum{x_i}=520\neq480$

Возможно я ошибся вычислял в ручную.