Уважаемый Валерий,
если я не ошибаюсь, вы интересовались задачей о "рекурсивном"
разрезании коробки (кажется, давным-давно вы упоминали эту задачу в вашей
статье в "КомпьютерПресс"): из квадрата вырезаются четыре квадратных
уголка, из получившегося креста склеивается коробка, затем та же процедура
повторяется с оставшимися уголками, и так до бесконечности. Требуется
максимизировать суммарный объем всех коробок.
В принципе, задача решается "в одно соображение" (и много технических
вычислений): на каждом шаге отношение стороны большого квадрата и углового
квадратика должно оставаться постоянным.
Прийти к этому заключению можно по-разному. Пусть сторона квадрата на шаге n
равна a[n]: вначале мы имеем квадрат со стороной a[0], вырезаем углы со
сторонами a[1] и так далее. Допустим, для квадрата со стороной, равной единице,
оптимальное (для первого шага) a[1] равно p. Для квадрата со стороной a[0] все
линейные размеры изменятся в a[0] раз, а значит, a[1] будет равно p*a[0].
Далее, на втором шаге для каждого квадрата со стороной a[1] мы снова получим
исходную задачу; следовательно, a[2]=p*a[1] и a[n+1]/a[n] равно p для всех n.
Другой способ: положим a[0]=1 и, записав объем коробок, получаемых на шаге n,
как
V[n]=(a[n-1]-2*a[n])^2*a[n]*4^(n-1),
будем искать максимум суммы V[1]+V[2]+... как функции от a[1],a[2],... Замечая,
что только слагаемые V[n] и V[n+1] зависят от a[n], получаем
D[V[1]+V[2]+...,a[n]]=D[V[n]+V[n+1],a[n]]=0,
где через D[y,x] обозначена производная y по x. Подставляя значение V[n], имеем
a[n-1]^2-8*a[n-1]*a[n]+12*a[n]^2+8*a[n]*a[n+1]-16*a[n+1]^2=0.
Это рекуррентное соотношение является однородным (все члены имеют степень 2), и
его решение можно искать в виде a[n]=p^n, что дает алгебраическое уравнение для
p. Отсюда немедленно получаем a[n+1]/a[n]=p.
Это же уравнение для p можно получить, если в выражение для V[n] подставить
a[n]=p^n, вычислить V[1]+V[2]+... (которое будет функцией от p) и далее искать
максимум по p.
Поскольку граничные значения p=0 и p=1/2 нам не подходят, окончательно
получаем, что p удовлетворяет уравнению
8*p^3-6*p+1=0
и S=V[1]+V[2]+... удовлетворяет уравнению
27*S^3+54*S^2+9*S-1=0.
Эти величины можно выразить через тригонометрические функции:
p=cos(4*pi/9), S=(2/3)*(sqrt(3)*sin(2*pi/9)-1).
Также можно убедиться, что значение S согласуется с численным решением задачи с
ограниченным числом шагов.
Соотвествующие выкладки в программе Mathematica я привожу ниже.
-----------------------------------------------------------------
In[1]:=
V[n_] = (a[n - 1] - 2*a[n])^2*a[n]*4^(n - 1);
In[2]:=
Simplify[D[V[n] + V[n + 1], a[n]] /. 4^(n + (a_.)) -> 4^a*2^(2*n)]
Out[2]=
4^(-1 + n)*(a[-1 + n]^2 - 8*a[-1 + n]*a[n] + 12*a[n]^2 + 8*a[n]*a[1 + n] -
16*a[1 + n]^2)
In[3]:=
Factor[% /. a[n_] -> p^n]
Out[3]=
(-4^(-1 + n))*p^(-2 + 2*n)*(-1 + 2*p)*(1 - 6*p + 8*p^3)
In[4]:=
FullSimplify[Sum[V[k] /. a[n_] -> Root[8*#1^3 - 6*#1 + 1 & , 2]^n, {k,
1, Infinity}]]
Out[4]=
Root[-1 + 9*#1 + 54*#1^2 + 27*#1^3 & , 3]
In[5]:=
Sum[V[k] /. a[n_] -> p^n, {k, 1, Infinity}]
Factor[D[%, p]]
Out[5]=
-((p - 4*p^2 + 4*p^3)/(-1 + 4*p^3))
Out[6]=
-(((-1 + 2*p)*(1 - 6*p + 8*p^3))/(-1 + 4*p^3)^2)
In[7]:=
Block[{a}, a[0] = 1; Table[Max[Sum[V[j], {j, 1, n}] /. NSolve[Table[D[Sum[V[j],
{j, 1, n}], a[i]] == 0, {i, n}],
Array[a, n]]], {n, 6}]]
Out[7]=
{0.07407407407407408, 0.07552944016343892, 0.07555988110956362,
0.07556051866298116, 0.07556053201623188,
0.07556053229590946}
In[8]:=
ListPlot[Log[(2/3)*(Sqrt[3]*Sin[(2*Pi)/9] - 1) - %], PlotJoined -> True]
#
###
-7.5 #
####
#
###
###########################################################################
#
###
-10 #
####
3
4
5 6
#
####
#
###
#
####
-12.5#
###
#
####
#
####
-15
#
###
#
####
#
###
#
####
-17.5#
###
#
####
#
####
-20
#
###
#
####
Out[8]=
Graphics[]
In[9]:=
FullSimplify[ComplexExpand[ToRadicals[Root[8*#1^3 - 6*#1 + 1 & , 2]]] -
Cos[(4*Pi)/9]]
FullSimplify[ComplexExpand[ToRadicals[Root[27*#1^3 + 54*#1^2 + 9*#1 - 1 & ,
3]]] -
(2/3)*(Sqrt[3]*Sin[(2*Pi)/9] - 1)]
Out[9]=
0
Out[10]=
0
-----------------------------------------------------------------
С уважением,
Максим Рытин m.r@inbox.ru
Декабрь 2002 г.