![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
utnapishtiНедавно я наткнулся в жж на математическую задачку, которая мне очень понравилась. Потом расскажу, почему именно, а пока пересказываю её своими словами.
Дана квадратная решётка n×n. (Пояснение: Она состоит из n2 клеток. Например, шахматная доска - это квадратная решётка 8×8).
В некоторые клетки мы ставим фишку. Таким образом, мы имеем "начальную конфигурацию".
Клетки, в которых стоит фишка, называем "занятыми"; а те, в которых фишки нет - "свободными".
После этого начинается "эволюционный процесс": если есть свободная клетка, с которой граничат как минимум две занятые клетки, то в эту свободную клетку мы тоже ставим фишку (таким образом, эта клетка становится "занятой").
(ПОЯСНЕНИЕ: клетки считаются граничащими, если у них есть общая сторона. Если только общий угол - не считаются.)
Этот процесс продолжается, пока есть куда ставить новые фишки согласно правилу.
Поставленные фишки никогда не снимаются (т.е. однажды занятая клетка больше никогда не становится свободной).
Легко проверить, что, если в качестве начальной конфигурации мы поставим n фишек в клетки, образующие диагональ решётки, то в ходе описанного процесса заполнится вся решётка - т.е. все клетки окажутся занятыми.
Есть и другие возможности поставить в качестве начальной конфигурации n фишек так, чтобы в ходе процесса заполнилась вся решётка.
Доказать: Если в качестве начальной конфигурации мы поставим меньше чем n фишек, то - как бы мы это ни сделали - в ходе процесса вся решётка не заполнится.
Дана квадратная решётка n×n. (Пояснение: Она состоит из n2 клеток. Например, шахматная доска - это квадратная решётка 8×8).
В некоторые клетки мы ставим фишку. Таким образом, мы имеем "начальную конфигурацию".
Клетки, в которых стоит фишка, называем "занятыми"; а те, в которых фишки нет - "свободными".
После этого начинается "эволюционный процесс": если есть свободная клетка, с которой граничат как минимум две занятые клетки, то в эту свободную клетку мы тоже ставим фишку (таким образом, эта клетка становится "занятой").
(ПОЯСНЕНИЕ: клетки считаются граничащими, если у них есть общая сторона. Если только общий угол - не считаются.)
Этот процесс продолжается, пока есть куда ставить новые фишки согласно правилу.
Поставленные фишки никогда не снимаются (т.е. однажды занятая клетка больше никогда не становится свободной).
Легко проверить, что, если в качестве начальной конфигурации мы поставим n фишек в клетки, образующие диагональ решётки, то в ходе описанного процесса заполнится вся решётка - т.е. все клетки окажутся занятыми.
Есть и другие возможности поставить в качестве начальной конфигурации n фишек так, чтобы в ходе процесса заполнилась вся решётка.
Доказать: Если в качестве начальной конфигурации мы поставим меньше чем n фишек, то - как бы мы это ни сделали - в ходе процесса вся решётка не заполнится.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2015-02-20 09:30 pm (UTC)Самое маленькое число фишек, вокруг которых построится прямоугольник n*n - n фишек по диагонали.
no subject
Date: 2015-02-20 09:43 pm (UTC)Верно и то, что окончательная конфигурация - один прямоугольник или объединение нескольких прямоугольников.
Но всё равно непонятно, почему 9 фишек не может хватить для того, чтобы заполнить доску 10х10. Мы ведь их не обязательно вдоль диагонали ставим, можем поставить как-то запутанно. Как ты сам саметил, "маленькие прямоугольники" могут начать срастаться. Почему же нет шанса, что они как-нибудь так удачно срастутся, что захватят всю доску?
no subject
Date: 2015-02-20 09:57 pm (UTC)Update: нет, неправильно.в пустом столбце могут появиться фишки из-за окружающих соседних столбцов.
no subject
Date: 2015-02-20 10:13 pm (UTC)Да. Более того, если ты сначала ставишь n фишек вдоль двух соседних сторон "через одну" - т.е. так, что свободые клетки чередуются с занятыми, - то в конце концов вся доска заполнится - при том, что в начальной конфигурации почти половина строчек и почти половина столбцов были пустыми.
no subject
Date: 2015-02-20 10:25 pm (UTC)no subject
Date: 2015-02-21 03:26 pm (UTC)no subject
Date: 2015-02-21 01:08 am (UTC)no subject
Date: 2015-02-21 03:25 pm (UTC)no subject
Date: 2015-02-21 02:44 am (UTC)no subject
Date: 2015-02-21 10:53 am (UTC)no subject
Date: 2015-02-21 02:08 pm (UTC)На несколько другую тему. Если фишки на этой решётке могут не только "размножаться" (размножение можно взять попроще, от одного родителя), но и диффундировать, это называется lattice gases. В такой системе можно, например, изучать продвижение фронта: посадили все фишки в левую часть длинной горизонтальной полосы, они диффундируют и размножаются направо; со временем получится фронт типа Фишера-Колмогорова в пределе, когда вероятность диффузии много больше вероятности размножения. Это примерно то, что происходит с некими клетками (глиома), если их высадить на тарелку.
no subject
Date: 2015-02-21 03:24 pm (UTC)> Мне кажется, что все начальные условия с минимальным количеством фишек устроены следующим образом.
Т.е. мы пытаемся описать все минимальные (с точки зрения количества фишек) начльные конфигурации, ведущие к заполнению всей доски. Верно?
> Квадрат n на n может быть разбит на базисные квадратные блоки.
ОК, дальше должно быть определение.
> Базисные блоки это квадраты размером 1 на 1, 2 на 2 и 3 на 3.
ОК.
> Базисные блоки расположены так, что каждый из них касается уголком хотя бы одного из других блоков, и каждая строка (и каждый столбец) пересекает (ют) только один базисный блок.
Это продолжение определения, или же предыдущее предложение - это всё определение, а это - уже свойство базисных блоков, следующеии из определения?
Базисные блоки определяются начальной конфигурацией?
Возьмём шахматную доску, n=8.
Если мы поставили фишки вдоль диагонали (A1, B2, ..., H8) - каковы базисные блоки?
А если вдоль сторон, через одну (A1, A3, A5, A7, B8, D8, F8, H8)?
no subject
Date: 2015-02-21 03:59 pm (UTC)no subject
Date: 2015-03-12 05:25 pm (UTC)no subject
Date: 2015-03-12 05:31 pm (UTC)Может быть, ещё сегодня.
Я сейчас разбираю свой берлинский оффис.
Через четыре часа у меня автобус в Вену.
Если разберу быстро, напишу про решение задачки, а если очень быстро - то ещё и про музей группы "die Brücke", куда я сегодня сходил напоследок :)
no subject
Date: 2015-03-12 05:45 pm (UTC)no subject
Date: 2015-03-12 05:46 pm (UTC)no subject
Date: 2015-03-12 05:51 pm (UTC)no subject
Date: 2015-03-12 05:53 pm (UTC)no subject
Date: 2015-02-22 08:35 am (UTC)no subject
Date: 2015-02-22 11:22 am (UTC)Т.е. пытаемся рассуждать так:
Если изначально фишек меньше, чем n, то в начальной конфигурации есть пустая строчка и пустой столбик.
Посмотрим на клетку X, являющуюся их пересечением. (По-видимому, именно её ты называешь центром пустой крестовины.)
Попытаемся доказать, что она никогда не заполнится...
После нескольких попыток обнаруживаем, что это неверно: если у нас в какой-то момент оказались занятыми все четыре клетки, граничащие с Х *углом*, то через два шага и Х окажется занятой. Для этого даже достаточно, чтобы были занятыми не все четыре соседа-через-угол, а только три из них.
Но - думаем мы - пытаясь "спасти" решение, это значит, что у нас уже (за два хода до заполнения Х) возникла "очень неэффективная" ситуация, при которой много фишек стоят в одном и том же столбце/строчке, и поэтому скорее всего проблема возникнет где-нибудь в другом месте из-за того, что там фишек не хватит.
Но - понимаем мы, ещё немного подумав - мы же не знаем, как именно эти соседи-через-угол оказались заняты.
И дальше всё усложняется.
Короче говоря, решения нет.
Более того, если в качестве начальной конфигурации ставить фишки "через одну" вдоль двух соседних сторон доски начиная с угла (я в одном из комментариев написал поля в шахматных терминах), то пустых крестовин там полным полно, а доска всё-таки заполняется.
no subject
Date: 2015-02-22 04:16 pm (UTC)ты ж написал, что есть идея решения и обоснование идеи решения.
no subject
Date: 2015-02-22 06:13 pm (UTC)no subject
Date: 2015-02-22 06:18 pm (UTC)