Задачи для детей от 5 до 15 лет.

[ravnovesie]

Здравия Вам желаю. Надеюсь, верно выбрал раздел для темы.

В сборнике "задачи для детей от 5 до 15 лет" Владимира Игоревича Арнольда имеется такая задача :
№15
Сколькими способами можно разбить число 64 на 10 натуральных слагаемых (целых >1), наибольшее из которых равно 12? [Разбиения, отличающиеся только порядком слагаемых, не считаются при подсчете числа разбиений разными.]

Верно ли понял условие, считая, что хотя бы одно слагаемое уже равно 12, то есть одно слагаемое зафиксировано. Или же все слагаемые могут быть и меньше 12?

[gris]

Натуральное — это целое $\geqslant 1$, вообще-то. Тут интрига в другом: могут ли в сумме быть несколько $12$. Слово "наибольший" можно и не строго толковать. А одно слагаемое, конечно, равно $12$.

$12+11+11+11+11+4+1+1+1+1=64$ или можно $12+12+11+11+11+3+1+1+1+1=64$

До сих пор нет единого мнения на этот счёт.

[ravnovesie]

gris в сообщении #1178700 писал(а):

А одно слагаемое, конечно, равно $12$.

Здравия Вам желаю, Gris. Спасибо! Тогда задачу можно свести к нахождению количества различных разбиении

$a_{1}+a_{2}+a_{3}+a_{4}+a_{5}+a_{6}+a_{7}+a_{8}+a_{9}=52$

при условии

$1\leqslant a_{1} \leqslant a_{2} \leqslant...\leqslant a_{8} \leqslant a_{9} \leqslant 12$

[ravnovesie]

Здравия Вам желаю.
Общая формула для приближенного расчета для условии
$0\leqslant a_1\leqslant a_2\leqslant ...\leqslant a_{n-1}\leqslant a_{n}\leqslant m$
$a_1+a_2+a_3+...+a_{n-1}+a_n=x$

$$N\approx\frac{\Sigma}{\sigma \sqrt{2\pi}} \exp \left\lbrace-\frac{(mn/2-x)^2}{2\sigma^2}\right\rbrace$$

где $\Sigma=\frac{(n+m)!}{n!m!} и $$\sigma^2=\frac{nm(n+m+1)}{12}$

С ростом $|mn/2-x|$ точность ухудшается.

[ravnovesie]

Эту задачу кто-нибудь решил? Стоит ли ею дальше заниматься мне?

[gris]

Подобные задачи на форуме обсуждались и в общем виде даже. Самый общий вид такой задачи это найти количество представлений числа $N$ в виде суммы натуральных слагаемых. А далее идут условия одинаковости представлений (например, по отличию только в порядке слагаемых) и ограничения, которых возможно до безобразия много (например, что все слагаемые должны быть разными, или лежать в одном интервале, или быть простыми, или их должно быть ровно столько-то, или вообще даже диву даёшься, что могут придумать Числовых Дел Мастера). С целью написания статей они изобретают рекуррентные формулы, производящие функции, адаптивные многочлены, эффективные алгоритмы и прочую умноту. Можете погрузиться в это, но нет гарантии возвращения в прекрасный непрерывный мир.
Я думаю, что решать именно эту конкретную задачу очень нудно. Хотя может быть и существует простой и красивый путь.

[grizzly]

ravnovesie в сообщении #1236392 писал(а):

Эту задачу кто-нибудь решил?

Просто и красиво? я нигде не видел. Это точно было бы интересно. В противном случае трудно будет кого-нибудь заинтересовать своими результатами, но решать в своё удовольствие тоже может быть интересно.

[grizzly]

ravnovesie в сообщении #1235243 писал(а):

$$N\approx\frac{\Sigma}{\sigma \sqrt{2\pi}} \exp \left\lbrace-\frac{(mn/2-x)^2}{2\sigma^2}\right\rbrace$$

где $\Sigma=\frac{(n+m)!}{n!m!}$ и $\sigma^2=\frac{nm(n+m+1)}{12}$

Что-то не так с этой формулой, мне кажется (я пытаюсь проверить её на правдоподобие при небольших $m,n,x$). Может, в последнем выражении просто $\sigma$, без квадрата? Где Вы нашли или как получили её?

[ravnovesie]

Здравия Вам желаю.

gris в сообщении #1236468 писал(а):

Хотя может быть и существует простой и красивый путь.

Тогда буду дальше над ней думать. Лучший способ саморазвития-- решать задачи, а если в результате решения найти что-то новое, то это двойная польза.

grizzly в сообщении #1236507 писал(а):

Что-то не так с этой формулой, мне кажется (я пытаюсь проверить её на правдоподобие при небольших $m,n,x$). Может, в последнем выражении просто $\sigma$, без квадрата? Где Вы нашли или как получили её?

Ошибок и опечаток при наборе этой формулы нет.
Исходил из того, что функция должна быть симметричной по перестановке $mn\to nm $ , количество комбинаций максимально примерно при $x=mn/2$, центральной теоремы, индукции и немного интуиции. Для малых чисел формула даст большие погрешности.
Думаю, с точностью до коэффициента, функция будет точнее такая
$N\sim[x(mn-x)]^s$
где $s$ функция от $m$ и $n$.

[Yadryara]

ravnovesie
Чегой-то расхождение существенное по Вашей формуле получается. Я, конечно, мог и напутать. Смотрите сами, для $x=m=n=10$ Альфа даёт ответ $\approx57.629$, тогда как правильное значение $42$. См. A000041

[grizzly]

Yadryara в сообщении #1236613 писал(а):

$x=m=n=10$ Альфа даёт ответ
$\approx57.629$, тогда как правильное значение $42$. См. A000041

Нет-нет, что-то не так. Если $x=m=n=10$, то у нас есть только одно решение: $1+1+\cdots +1=10$. В рассматриваемой задаче нулевые слагаемые недопустимы.

[Yadryara]

grizzly в сообщении #1236618 писал(а):

В рассматриваемой задаче нулевые слагаемые недопустимы.

То-то и оно, что, согласно ТС, допустимы. Обратите внимание на ноль слева.

ravnovesie в сообщении #1235243 писал(а):

Общая формула для приближенного расчета для условии
$0\leqslant a_1\leqslant a_2\leqslant ...\leqslant a_{n-1}\leqslant a_{n}\leqslant m$

[ravnovesie]

Yadryara в сообщении #1236613 писал(а):

ravnovesie
Чегой-то расхождение существенное по Вашей формуле получается. Я, конечно, мог и напутать. Смотрите сами, для $x=m=n=10$ Альфа даёт ответ $\approx57.629$, тогда как правильное значение $42$. См. A000041

Под самой формулой мной сказано, что погрешность растет тем больше, чем больше $mn/2-x$. В вашем случае 10*10/2-10=40. Кроме того в этом случае ограничения на члены суммы практически не действуют, задача сводится к приведенной в ссылке https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0. Задача Арнольда $a_1+a_2+...+a_{10}=64$ с условием $1\leqslant a_i \leqslant 12$ представлена мной в таком виде
$a_1+a_2+...+a_{10}=64-10=54$ с условием $0\leqslant a_i \leqslant 11$
Что интересно $mn/2=10 \cdot 11/2=55$

Рассмотрим Вашу задачу $m=n=10$ но $x=mn/2=50$. Составлю код для расчета и сравним с формулой.

-- 29.07.2017, 22:40 --

Код

#include<iostream>
#include<math.h> 
using namespace std;
main()
{

      int j1=0, g,k;
      cin>>g; //максимальное значение члена суммы
      cin>>k; //значение суммы
     
      for(int i1=0; i1<=g; i1++)
      { for(int i2=i1; i2<=g; i2++)
               {for(int i3=i2; i3<=g; i3++)
               {for(int i4=i3; i4<=g; i4++)
               {for(int i5=i4; i5<=g; i5++)
               {for(int i6=i5; i6<=g; i6++)
               {for(int i7=i6; i7<=g; i7++)
               {for(int i8=i7; i8<=g; i8++)        
               {for(int i9=i8; i9<=g; i9++)
               {for(int i10=i9; i10<=g; i10++)
               if(i1+i2+i3+i4+i5+i6+i7+i8+i9+i10==k) j1++;
               }
               }
               }
               }
               }
               }
               }
               }
               }
               cout<<"j1=="<<j1<<endl;              
               system("pause");
               return 0;
}

По программе при $k=50$ и $g=10$ имеем результат 5448. По формуле 5571.72. Погрешность 2,326%.

[svv]

А что выдаёт Ваша программа для исходной задачи? (для сверки)

[Yadryara]

ravnovesie в сообщении #1236680 писал(а):

Под самой формулой мной сказано, что погрешность растет тем больше, чем больше $mn/2-x$.

Да, и для значений $x=\lfloor {\frac{n^2}2} \rfloor$ при $m=n$ имеется A029895, а для чётных $n$ и A063074.

В этом случае относительная точность Вашей формулы действительно возрастает с ростом $n$. Если $n = 200$, то

$$\frac{3.5525 \cdot 10^{115}}{3.5485 \cdot 10^{115}}\approx 1.0011$$

Табличное значение в знаменателе. Результаты вычислений по Вашей формуле до этих значений $n$ постепенно приближаются к табличным сверху.

ravnovesie в сообщении #1236680 писал(а):

Кроме того в этом случае ограничения на члены суммы практически не действуют, задача сводится к приведенной в ссылке

Я в курсе, потому и давал ссылку на A000041. Ошибок в подсчёте с помощью Альфы не выявлено. Например, получено значение $\approx5571.72$ и оно совпадает с Вашим.