Закончится ли "игра"

[Urahag]

Задача следующая:

Имеется куб размером 100x100x100, каждая грань которого разбита на 10000 участков 1x1. На каждом участке живет человек. У некоторых из них есть карточки, 60000 штук на всех. Каждый день один из людей, имеющих не менее 4 карточек (если такие люди имеются), должен отдать своим соседям по стороне по одной карточке. Нужно доказать, что через какое-то ограниченное время не менее трети людей будут иметь хотя бы одну карточку.

В случае если "игра" конечна, всё очевидно, но конечна ли она - не могу понять(

[sergey zhukov]

Urahag
Похоже на пример с бюрократами из книжики Пера Бака "Как работает природа. Теория самоорганизованной критичности". Возможно, от размера куба ничего не зависит. Может быть, попробовать доказать это для куба с одним участком на каждой грани?

[vicvolf]

Urahag в сообщении #1631826 писал(а):

Задача следующая:

Имеется куб размером 100x100x100, каждая грань которого разбита на 10000 участков 1x1. На каждом участке живет человек. У некоторых из них есть карточки, 60000 штук на всех. Каждый день один из людей, имеющих не менее 4 карточек (если такие люди имеются), должен отдать своим соседям по стороне по одной карточке. Нужно доказать, что через какое-то ограниченное время не менее трети людей будут иметь хотя бы одну карточку.

В случае если "игра" конечна, всё очевидно, но конечна ли она - не могу понять(

Всего 1 млн. человек. Третья часть -333333 человека. Всего карточек 60 тыс. Как может по карточке быть у каждого из 333333 чел.?

[EUgeneUS]

vicvolf в сообщении #1631831 писал(а):

Всего 1 млн. человек.

всего $10000 \times 6 = 60000$ человек.

[vicvolf]

EUgeneUS в сообщении #1631832 писал(а):

$10000 \times 6 = 60000$ человек.

Значит имеем случайное блуждание на плоскости с вероятностью перескока равной тому, что одновременно 4 карточки у одного человека.

[Urahag]

sergey zhukov в сообщении #1631829 писал(а):

Urahag
Похоже на пример с бюрократами из книжики Пера Бака "Как работает природа. Теория самоорганизованной критичности". Возможно, от размера куба ничего не зависит. Может быть, попробовать доказать это для куба с одним участком на каждой грани?

Да, спасибо. Это как я понимаю всё про модель песчаной кучки. Но мне не помогло(

-- 05.03.2024, 20:42 --

vicvolf в сообщении #1631834 писал(а):

EUgeneUS в сообщении #1631832 писал(а):

$10000 \times 6 = 60000$ человек.

Значит имеем случайное блуждание на плоскости с вероятностью перескока равной тому, что одновременно 4 карточки у одного человека.

Помогает ли это как-то ответить на вопрос, закончится ли процесс?

[manul91]

Urahag в сообщении #1631926 писал(а):

Помогает ли это как-то ответить на вопрос, закончится ли процесс?

блуждание вовсе не случайное:)

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

Так как в системе конечное число состояний, то она либо должна остановится, либо зациклится переходя через прежних же состояний.
Такая монотонная величина будет противоречить возможности "зациклиться" (если допустить что попали в цикл, то в конце цикла величина должна быть измениться поскольку монотонна - но это ведь одно из прежних состояний - т.е. величина должна быть той же самой - противоречие).

Задачка хороша :)
Что-то между дискретного уравнения теплопроводности на сфере (расплывание тепла) в виде клеточного автомата типа игры жизнь.

Есть две интересные величины: количество "нулевиков", и количество "богатых" (те у которых карточек 4 или больше). Вся динамика на данном шаге происходит вокруг "богатых" т.е. только эти границы (и соответных "кластеров") можно и рассматривать.
Из богатых, в конкретном шаге только "четверточники" могут превратиться в "нулевиков", и никакие другие.

Мне удалось доказать например, что множество "нулевиков" на каждом шаге не может увеличиваться (либо уменьшается, либо остается постоянным). Это путем неких рассуждений про "стоков карточек через границ". Они несколько длинные (рассматриваются разные случаи) но не трудные, если интересно напишу.

К сожалению это проблему не решает, т.к. остается возможность цикла т.к. не исключает чтобы при шаге к-во нулевиков остается постоянным.
Впрочем это и так понятно (кластер из "супер богатых" отгороженным толстым пластом "одиночников" от "нулевиков" - нужно какое-то время чтобы "волна" распространилась до границ, за это время нулевики не будут меняться).

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

Некоторые "плохие соседства" возможно, в интегральном смысле потребуется исключить заведомо из-за того что карточек достаточно мало (аналогично тому как можно сразу доказать, что нулевиков обязано быть ненулевое количество). (Например типа "нельзя чтобы все соседи из которых один нулевик а другой "богач" - это нулевик и "четверточник"). Это нужно для отсутствия цикла и хорошо видно при аналогичной игре например, на круге; замкнутая топология тут существенна.

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

В общем пока без успеха.

[worm2]

Ещё интересны угловые кубики: каждая из трёх граней является соседней для двух других. Это наверняка придаёт какие-то ключевые свойства всей схеме. В частности, нельзя весь куб раскрасить в шахматном порядке. Если бы можно было (в 4-мерном пространстве???), был бы очевидный цикл: "богатые" в чёрных клетках, "нулевики" в белых, и на каждом шаге они меняются. Но здесь такая схема не проходит, возможно, угловые кубики дают шанс на какой-то полуинвариант.

[vicvolf]

Urahag в сообщении #1631926 писал(а):

vicvolf в сообщении #1631834 писал(а):

Значит имеем случайное блуждание на плоскости с вероятностью перескока равной тому, что одновременно 4 карточки у одного человека.

Помогает ли это как-то ответить на вопрос, закончится ли процесс?

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

[manul91]

worm2 в сообщении #1631961 писал(а):

В частности, нельзя весь куб раскрасить в шахматном порядке. Если бы можно было (в 4-мерном пространстве???), был бы очевидный цикл: "богатые" в чёрных клетках, "нулевики" в белых, и на каждом шаге они меняются.

Это точно. Но на "активно-шахматного" распределения итак не хватает карточек (максимальную площадь которую "богатые" могут занять 60k/4=15k, площадь куба - 60k). Факт про угловых кубиков да, в копилку.

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

Напрашивается следующая мысль.

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

Интуитивно, по мере "расплывания концентрации карточек" будет происходить следующее:
- те красные области в которых избыток карточек будет достаточно большим (у каждого внутри больше четырех карточек) будут увеличивать свою площадь, пока теряют карточек.
- те красные области в которых количество карточек "погранично" (с "четверокарточниками по внутренней границе") будут "рассыхаться" уменьшая свою площадь (из-за отбытия "четверокарточников") пока теряют карточек.

Итого интегрально, на шаг:
- Через красных областей "вытечет" ровно столько карточек, сколько суммарная длина их границ (и столько карточек прибавится к синих областей)
- Красные области потеряют столько клеток сколько "четверокарточников" есть у по внутренней стороне их границ (не более чем потерянных карточек), притом потеря не каждого из них, обязана привести к компенсирующем появлении "богача" в синей области (что сохранит к-во богачей).

Тоесть грубо говоря, интегральная величина "плотности карточек в красных областей" $\rho = \frac{K}{A}$ где $K$ - сумма карточек внутри всех красных областей, а $A$ - их суммарная площадь, на каждом шаге должна уменьшаться.
Поскольку числитель на шаг убывает на величину периметра красных областей, а знаменатель убывает на меньшую (в граничном случае ту же самую) величину, имеем переход
$\rho_{n} = \frac{K}{A} \to \rho_{n+1} = \frac{K - P}{A - Q}$ где $P \ge Q$. "Плохой" случай равенства, нужно как-то исключить.... :)

[mihaild]

manul91 в сообщении #1632003 писал(а):

Тоесть грубо говоря, интегральная величина "плотности карточек в красных областей" $\rho = \frac{K}{A}$ где $K$ - сумма карточек внутри всех красных областей, а $A$ - их суммарная площадь, на каждом шаге должна уменьшаться

Я бы назвал это "средним количеством карточек у богатых". И она может возрастать: если у одного 59996 карточек, у другого 4 (и они далеко друг от друга), у остальных 0, то сейчас среднее количество карточек у богатых 30000, а на следующем шаге 59992. И количество богатых тоже может как возрастать, так и убывать с течением времени.

Я пока что понял только что каждый человек в какой-то момент времени останется с не более чем 3 карточками, и соответственно со временем ни у кого не будет больше 7 карточек. Что хуже нужной оценки в два с небольшим раза:)

Еще выглядит стоящим анализ: 1) верно ли утверждение для произвольного связного 4-регулярного графа? если есть простой контрпример, то надо как-то содержательно использовать структуру куба; 2) могут ли вообще остаться богатые?

[manul91]

mihaild в сообщении #1632006 писал(а):

И она может возрастать: если у одного 59996 карточек, у другого 4 (и они далеко друг от друга), у остальных 0, то сейчас среднее количество карточек у богатых 30000, а на следующем шаге 59992.

Н-да, что-то я затупил насчет свойств обычных дробей :(
А как насчет просто величины разницы $K-A$, "сумма карточек внутри всех красных областей минус суммарная площадь всех красных областей"? Первая величина уменьшается быстрей чем вторая, т.е.
$K-A \to K_{next} - P_{next} = (K-P) - (A-Q)$, но $P\ge Q$ значит $K-A \ge K_{next} - P_{next}$, т.е. разница $K-A$ вроде бы всегда должна уменьшаться (если на данном шаге хотя бы что-то происходит).
$P$ - суммарная длина границы отделяющая областей "богатых" от "бедных" на данном шаге, $Q$ - количество четверточников (и в некотором случае углов и пр. пятикарточников) на границе из-за которых может уменьшаться площадь, и вроде всегда $P\ge Q$.
Простое увеличение площади богачей величину только уменьшает; уменьшение площади богачей не может "тягаться" с уменьшением количества карточек внутри той же площади...
В вашем случае это даст $6k - 2 = 59998$, после перехода будет $59992 - 1 = 59991$ все в порядке... :)
(любая монотонная величина должна "остановиться", просто потому что количество возможных состояний конечно)

[manul91]

P.S. Не годится. Например богач (100 карточек) окруженный трешниками, в пустоте, нарушает монотонность. Каждый "новоприбывших" красных может принести вплоть до 4-ех дополнительных карточек в копилку площади красных... Тьфу. Может, $\frac{K}{4}-A$?

[mihaild]

Тоже нет: четыре человека с 4 карточками вокруг одного с тремя, у всех остальных людей мало карточек и они далеко. $K = 16$, $A = 4$. На следующем шаге $K = 7$, $A = 1$.

А если рассмотреть более простую задачу, для цикла (и соответственно с лимитом на две карточки, и требованием чтобы карточки были у половины). Тут если цикл четной длины то очевидно возможно бесконечное переодическое хождение между черными и белыми, но при нем карточки все равно будут у половины. Но я с наскока даже для цикла не понимаю ответ:(

[vicvolf]

mihaild в сообщении #1632033 писал(а):

Тоже нет: четыре человека с 4 карточками вокруг одного с тремя, у всех остальных людей мало карточек и они далеко. $K = 16$, $A = 4$. На следующем шаге $K = 7$, $A = 1$.

В этой задаче все зависит от начального распределения карточек. Предлагается в качестве примера начального взять вариант: у одного человека все 60000 карточек, а остальных карточек нет. В этом случае этот богач первые 4 шага раздает по 4 карточки своим 4 соседям. После этого у него остается 59984 карточки, а у 4-х его соседей по 4 карточки. На 5 шаге богач больше карточки не раздает, а каждый из его соседей отдает по 1 карточке одному из своих соседей, притом богачу они карточку не дают, а дают одному соседу из оставшихся трех. В задаче не сказано, как в этом случае выбирается сосед. Можно предположить, что когда есть выбор, то он делается с равной вероятностью. Таким образом, в данном случае вероятность передачи карточки одному из трех соседей равна $p=1/3$ и.т.д. Может быть другое распределение вероятностей. Когда выбора нет, то вероятность передачи карточки соседу $p=1$. В любом случае у нас случайный процесс.