Задача: Трое друзей делят 1 литр.

[bayah]

Задача такая:

Цитата:

Трое друзей $A,B,C$ хотят разделить между собой $1$ литр некоторого напитка. Проблема в том, что они умеют делить только пополам. Поэтому поступают следующим образом. Сначала весь напиток находится в кружке у $A$, а кружки у $B$ и $C$ пустые. Затем половина содержимого кружки $A$ поровну добавляется в кружки $B$ и $C$ . После этого половина содержимого кружки $B$ поровну добавляется в кружки $A$ и $C$. На следующем шаге половина содержимого кружки $C$ поровну добавляется в кружки $A$ и $B$. И так далее, много раз: половина содержимого очередной кружки (по циклу: $A,B,C,A,B,C,\ldots$) поровну добавляется в остальные кружки.

Нужно понять к значениям стремятся объемы в каждой куржке.
Можно выразить содержимое каждой кружки после полного цикла ($A,B,C$) через содержимое кружек на прошлом шаге:

$A_1 = A_0 - \dfrac{A_0}{2} + \left(\dfrac{B_0 + \frac{A_0}{4}}4 \right) + \left(\dfrac{C_0 + \dfrac{B_0 + \frac{A_0}{4}}4}{4}\right)$
$B_1 = B_0 + \dfrac{A_0}{4} - \left(\dfrac{B_0 + \frac{A_0}{4}}2 \right) + \left(\dfrac{C_0 + \dfrac{B_0 + \frac{A_0}{4}}4}{4}\right)$
$C_1 = C_0 + \dfrac{A_0}{4} + \left(\dfrac{B_0 + \frac{A_0}{4}}4 \right) - \left(\dfrac{C_0 + \dfrac{B_0 + \frac{A_0}{4}}4}{2}\right)$

откуда упрощая получим

$A_1 = \dfrac{16 + 25A_0 + 4B_0}{64}$; $B_1 = \dfrac{13 + 23B_0 + 3C_0}{64}$; $C_1 = \dfrac{4 + 28C_0 + A_0}{32}$

Далее, я полагаю нужно как-то получить эти рекурсивные формулы в замкнутой форме (то есть без рекурсии). Но как это сдеать не знаю.
Или же можно как-то иначе понять к чему стремятся эти объемы?
Написал скрипт из которого собственно ясно что объемы стремятся к $\dfrac 4 9$, $\dfrac 1 3$, $\dfrac 2 9$ соответсвенно, но понимания это не дало.

Подскажите, где тут можно что-то сделать?

[ИСН]

Как числа Фибоначчи получают в замкнутой форме без рекурсии, знаете? Тут примерно так же.

[iifat]

Коли уж гипотеза у вас есть, проще всего, имхо, подставить значения в формулы. Если это и правда пределы, должно получиться (возможно, за некоторое небольше количество шагов) то ж самое.

[bayah]

ИСН в сообщении #1336795 писал(а):

Как числа Фибоначчи получают в замкнутой форме без рекурсии, знаете? Тут примерно так же.

Как? Знаю что насчет числ Фибонначи можно с помощью производязих функций, но я не очень знаком с ними.

iifat в сообщении #1336797 писал(а):

Коли уж гипотеза у вас есть, проще всего, имхо, подставить значения в формулы. Если это и правда пределы, должно получиться (возможно, за некоторое небольше количество шагов) то ж самое.

Ну да, можно, но так-то вроде я уже и знаю что это верный ответ. По сути скрипт довольно явно к этим числам сходился. По сути та же процедура что и подставить. Но я просто считаю это не совсем честное решение.

[DeBill]

bayah
В здоровенных формулах - опечатка (в третьем слагаемом пропущено в числителе $\frac{A_0}{4}$)
Странно Вы как то упрощаете: часть слагаемых с нулями заменили их значениями, а часть - нет....Ясно, что есть ошибка: суммарное кол-во жидкости уменьшилось (а за такое в реале могут и морду начистить...)
Ответ Ваш (численнонайденный ) не удовлетворяет системе.
Не надо упрощать, подставляя: в здоровенных формулах, чисто формально приведите подобные. И будет у Вас хорошая рек. формула. Запишите ее в матричном виде. Убедитесь, что оператор из правой части - сжимающий (ну, эт - для математиков; физику/прикладнику - не обязательно: он и численно видит сходимость). Перейдите к пределу - и получите матричное уравнение для предельных значений. Решив его, получите ответ...

[Slav-27]

bayah
У нас есть 3 числа: количество напитка в 1-й, во 2-й и в 3-й кружке. Давайте рассматривать эти 3 числа как вектор 3-мерного пространства. Тогда $A,B$ и $C$ -- линейные операторы на этом пространстве. Для линейных операторов есть хорошая теория, и можно ею воспользоваться.

Обозначим линейный оператор $CBA$ через $K$: вы хотите узнать, что будет с начальным вектором, если применять $K$ достаточно долго. Для начала надо посмотреть, какие у $K$ собственные значения...

1) Если $|\lambda|<1$, то соответствующее подпространство уходит в ноль;
2) $|\lambda|>1$ быть не может, потому что степени оператора $K$, очевидно, равномерно ограничены;
3) если $\lambda$ не единица, но на единичной окружности, то будет двумерное подпространство, которое вертится; если проекция начального вектора на это подпространство ненулевая, то его будет болтать, и он никуда сходиться не будет;
4) если $\lambda=1$, то соответствующее подпространство неподвижно, и надо думать, как начальный вектор расположен относительно него.

Как найти собствнные значения? Это легко сделать следующим образом: рассмотрите оператор $Z$, который циклически переставляет кружки; тогда, очевидно, $K=(ZA)^3$ (если правильно выбрать направление цикла).

[bayah]

DeBill в сообщении #1336837 писал(а):

В здоровенных формулах - опечатка (в третьем слагаемом пропущено в числителе $\frac{A_0}{4}$)

Да, там действительно пропустил, спасибо, но итоговые формулы его учитывали, правда в формуле для $C$ все равно ошибка закралась.

DeBill в сообщении #1336837 писал(а):

Странно Вы как то упрощаете: часть слагаемых с нулями заменили их значениями, а часть - нет

Это я пропустил слагаемое, я не подставлял значение.

В общем должно быть так:

$A_1 = A_0 - \dfrac{A_0}{2} + \left(\dfrac{B_0 + \frac{A_0}{4}}4 \right) + \left(\dfrac{C_0 + \frac{A_0}{4} + \dfrac{B_0 + \frac{A_0}{4}}4}{4}\right)$
$B_1 = B_0 + \dfrac{A_0}{4} - \left(\dfrac{B_0 + \frac{A_0}{4}}2 \right) + \left(\dfrac{C_0 + \frac{A_0}{4} + \dfrac{B_0 + \frac{A_0}{4}}4}{4}\right)$
$C_1 = C_0 + \dfrac{A_0}{4} + \left(\dfrac{B_0 + \frac{A_0}{4}}4 \right) - \left(\dfrac{C_0 + \frac{A_0}{4} + \dfrac{B_0 + \frac{A_0}{4}}4}{2}\right)$

$A_1 = \dfrac{16 + 25A_0 + 4B_0}{64}$; $B_1 = \dfrac{13 + 23B_0 + 3C_0}{64}$; $C_1 = \dfrac{4 + 12C_0 + A_0}{32}$

Slav-27 в сообщении #1336839 писал(а):

Ответ Ваш (численнонайденный ) не удовлетворяет системе.

Теперь вроде бы удовлетворяет.

DeBill в сообщении #1336837 писал(а):

Запишите ее в матричном виде. Убедитесь, что оператор из правой части - сжимающий (ну, эт - для математиков; физику/прикладнику - не обязательно: он и численно видит сходимость). Перейдите к пределу - и получите матричное уравнение для предельных значений. Решив его, получите ответ...

Вот тут я уже поплыл:)

-- 06.09.2018, 02:08 --

Slav-27 в сообщении #1336839 писал(а):

У нас есть 3 числа: количество напитка в 1-й, во 2-й и в 3-й кружке. Давайте рассматривать эти 3 числа как вектор 3-мерного пространства. Тогда $A,B$ и $C$ -- линейные операторы на этом пространстве. Для линейных операторов есть хорошая теория, и можно ею воспользоваться.

Это очень интересно. Я обязательно попробую, как только усвою все это:)

[Slav-27]

Не надо пугаться, про теорию я скорее для красоты сказал. Там из всей теории надо только понимать, почему если у лиейнго оператора на $\mathbb C^n$ все собственные значения различны, то он диагонализируется в некотором базисе. Ну и уметь считать собственные значения по матрице оператора.

Хотя если вы линейную алгебру совсем не знаете, то это я зря. В общем-то вы примерно это и делали (только сложнее, чем можно сделать, если знать линейную алгебру).

[Geen]

bayah в сообщении #1336854 писал(а):

Вот тут я уже поплыл:)

Попробуйте так: распределение 1 литра по кружкам можно описать точкой в (равностороннем) треугольнике; во что перейдёт этот треугольник после одного цикла (прямо по Вашим формулам)

[TOTAL]

Школьное решение.

Произвольный треугольник (синий), стороны которого заданы прямыми $A, B, C$, уменьшим в несколько раз и повернем на $90$ градусов (черный $PQR$, подобен синему).

На плоскости выбираем произвольную точку $L_1$, затем отрезок $PL_1$ сжимаем к прямой $A$ с подходящим коэффициентом (т.е. так, что точка $P$ перейдет в точку $Q$). При этом точка $L_1$ перейдет в точку $L_2$.

Затем отрезок $QL_2$ сжимаем к прямой $B$ с подходящим коэффициентом (т.е. так, что точка $Q$ перейдет в точку $R$). При этом точка $L_2$ перейдет в точку $L_3$.

Затем сжимаем к $C$ и так далее. Очевидно $|PL_1| \ge |QL_2| \ge |RL_3| \ge |PL_4| \ge |QL_5| \ge \dots $ Так как стороны исходного треугольника попарно не параллельны, равенство в этой цепочке может встречаться не более одного раза подряд. Точка $L$ в пределе будет бегать по вершинам $PQR$.


В исходной задаче треугольник равностороний (каждый отдает соседям поровну), сжатие к каждой стороне - ровно в два раза (каждый себе оставляет половину), площадь всего треугольника - 1 литр, а площади треугольников, задаваемых точкой $L$ и сторонами $A, B, C$ соответственно, равны текущему содержанию жидкости в кружках.

[OlegCh]

(Оффтоп)

Батюшки!... Представил этот разговор между тремя персонажами у соседнего гастронома за углом