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

[waxtep]

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

В задаче не сказано, как в этом случае выбирается сосед

Всем четырем соседям же! Соответственно, на пятом шаге у "главного буржуина" число карточек не изменится, четверки превратятся в единички и приобретут по три единичных соседа

-- 07.03.2024, 10:11 --

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

Каждый день один из людей, имеющих не менее 4 карточек (если такие люди имеются), должен отдать своим соседям по стороне по одной карточке

Тут, кстати, понял, что тоже невнимательно прочел условие. Только один из людей? Не все, у кого $4+$ карточек одновременно? Это разные задачи, "только один" выглядит проще

[worm2]

waxtep в сообщении #1632069 писал(а):

Только один из людей? Не все, у кого $4+$ карточек одновременно? Это разные задачи, "только один" выглядит проще

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

[waxtep]

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

Но "только один", наоборот, выглядит сложнее

Мне показалось проще, потому что в такой постановке задача совсем локальная, за один день количество карточек меняется ровно в пяти клетках. Дальше, правда, думать не пробовал

[vicvolf]

waxtep в сообщении #1632069 писал(а):

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

В задаче не сказано, как в этом случае выбирается сосед

Всем четырем соседям же! Соответственно, на пятом шаге у "главного буржуина" число карточек не изменится, четверки превратятся в единички и приобретут по три единичных соседа

Сначала богач 16 дней отдает по 4 карточки своим 4 соседям. На 17, 18,19, 20 дни эти соседи отдают по 1 карточке одному из трех оставшихся своих соседей. Непонятно какому из трех? У них остается по 3 карточки, а у новых соседей по одной карточке. На 21, 22,23,24 дни богач отдает по одной карточке своим соседям. У него остается 59980 карточек, а у соседей опять по 4 карточки. Эти соседи богача на 25,26,27,28 дни отдают по 1 карточке одному из трех своих соседей. Непонятно тому же или другому. У них остается опять по 3 карточки, а у новых соседей по одной или две карточки (неизвестно из условия). Так будет пока у богача не останется 3 карточки, по 3 карточки будет через 4 дня после этого и у его соседей, а потом у их соседей, и.т.д. Таким образом, процесс заканчивается.

[EUgeneUS]

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

Сначала богач 16 дней отдает по 4 карточки своим 4 соседям

Четыре дня по четыре карточки (в каждый день) четырем соседям.

[mihaild]

И я невнимательно прочитал, подумал что все раздают.

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

Но "только один", наоборот, выглядит сложнее. Потому что вариант "одновременно" является частным случаем варианта "только один"

Это если в нем невозможен цикл. Если в нем цикл возможен, то это доказать может быть проще.

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

[vicvolf]

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

Еще кстати в любом цикле обязательно участвуют все жители,

По-моему не обязательно в цикле участвуют все. Например, распределили карточки, что у одного соседа -4, а другого 3. Один другому и будет передавать. Ведь нет ограничений на возврат карточек. Как я говорил, что все зависит от начального распределения карточек.

[mihaild]

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

Это сути не меняет

Это отвечает на вопрос "кому отдают карточки".

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

Если в любом цикле участвуют все жители, то для этого у всех должно быть хотя бы 3 карточки

У каждого в какой-то момент. Но не обязательно у всех одновременно. Человек, у которого сейчас нет карточек, может получить 4 карточки от соседей и начать раздавать уже сам.

Пусть у нас есть цикл передачи карточек, в результате которого все остаются при своих. $i$-й житель раздает карточки $a_i$ раз. Пусть $m = \min a_i$. Если есть $a_j > m$, то есть и житель, раздавший $m$ раз, у которого есть сосед, раздавший карточки $n > m$ раз. Соответственно наш житель раздал $4m$ карточек, а получил минимум $3m + n > 4m$ карточек. И значит наш житель не остался при своих.

[EUgeneUS]

1. Покрасим в красный цвет все занятые клетки, а также клетки у которых все соседи тоже занятые.
2. Площадь получившейся фигуры $S$ не убывает на каждом ходе. Вот вам "интегральный показатель"
3. Более того, клетка единожды покрашенная в красный цвет, уже не может его изменить.

Как утверждает уважаемый mihaild

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

Еще кстати в любом цикле обязательно участвуют все жители,

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

Минимальное количество людей с карточками, чтобы закрасить всё поле - половина поля (раскладываем карточки в шахматном порядке). То есть для 30 000 тысяч доказано.

-- 07.03.2024, 16:43 --

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

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

Если карточки у менее чем половины, то картинка будет обязательно "расплываться", и повторно, в цикле такая раскладка недостижима.

-- 07.03.2024, 16:47 --

Так всё доказано.

1. Если пришли к статичной ситуации и ходов больше нет, то карточками заполнено от 60 000 до 20 000 клеток. А это и есть "не менее трети".
2. Если зациклились (оказались в ситуации, которая возможна в цикле), то карточками заполнено не менее половины. А это всё равно "не менее трети".

Других вариантов нет, насколько понимаю.

[mihaild]

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

Минимальное количество карточек, чтобы закрасить всё поле - половина поля (раскладываем карточки в шахматном порядке)

По замечанию worm2, на кубе шахматаного порядке нет, т.к. есть цикл длины 3. Так что видимо 30 тысяч карточек чтобы закрасить всё не хватит.
Но просто если все клетки закрашены, то в любом квадрате $2 \times 2$ не менее двух клеток с карточками, а куб четного размера разбивается на такие непересекающиеся квадраты.

Я бы предложил покрасить в 3 цвета, чтобы не путаться: в красный - клетки, в которых что-то есть, в зеленый - клетки, во всех соседях которого что-то есть, и в синий - остальные.
Ключевое соображение от EUgeneUS: никакая клетка не может быть перекрашена в синий из не-синего.
Соображение от меня: если обмен карточками зациклился, то каждая клетка будет в какой-то момент покрашена в красный.
Из этого следует, что весь куб станет красно-зеленым.
А в красно-зеленом квадрате $2 \times 2$ хотя бы половина клеток красные, так что хотя бы половина клеток всего красно-зеленого куба - красные.

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

[EUgeneUS]

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

Минимальное количество людей с карточками, чтобы закрасить всё поле - половина поля (раскладываем карточки в шахматном порядке). То есть для 30 000 тысяч доказано.

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

По замечанию worm2, на кубе шахматаного порядке нет, т.к. есть цикл длины 3. Так что видимо 30 тысяч карточек чтобы закрасить всё не хватит.

Да, про шахматную раскраску куба согласен.
Тут у меня не очень внятно - что именно доказано
Имелось в виду, что для 30 000 возможны только статичные исходы, но не циклы. А если их "не хватит" из особенностей куба, то тем более.

-- 07.03.2024, 17:43 --

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

Остался вопрос, возможны ли циклы в регулярных графах степени больше 2.

Если в исходной задаче роздана 180001 карточка, то зациклится обязательно, так как будет минимум одна клетка с количеством карточек более $3$.
Более того, если раздали 180000 карточек, но не всем поровну, то тоже обязательно возникнет цикл.

[mihaild]

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

Более того, если раздали 180000 карточек, но не всем поровну, то тоже обязательно возникнет цикл.

Не обязательно. Одному дали 7, соседям по 2, на следующем шаге окажется что у всех поровну.

[manul91]

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

1. Покрасим в красный цвет все занятые клетки, а также клетки у которых все соседи тоже занятые.
2. Площадь получившейся фигуры $S$ не убывает на каждом ходе. Вот вам "интегральный показатель"
3. Более того, клетка единожды покрашенная в красный цвет, уже не может его изменить.

"Не убывает" недостаточно.
Оно может не убывать т.е. быть постоянным, а активность идти.

[EUgeneUS]

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

Оно может не убывать т.е. быть постоянным, а активность идти.

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

[manul91]

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

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

Интуитивно это "понятно", но не понял откуда это строго следует...
И это

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

Если карточки у менее чем половины, то картинка будет обязательно "расплываться", и повторно, в цикле такая раскладка недостижима.

Это где-то строго доказано, в каком-то определенном смысле? (и "расплываться" это не то же самое как "не уменьшаться")

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

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

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

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

Пусть у нас есть цикл передачи карточек, в результате которого все остаются при своих. $i$-й житель раздает карточки $a_i$ раз. Пусть $m = \min a_i$. Если есть $a_j > m$, то есть и житель, раздавший $m$ раз, у которого есть сосед, раздавший карточки $n > m$ раз. Соответственно наш житель раздал $4m$ карточек, а получил минимум $3m + n > 4m$ карточек. И значит наш житель не остался при своих.

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

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

$i$-й житель раздает карточки $a_i$ раз. Пусть $m = \min a_i$. Если есть $a_j > m$, то есть и житель, раздавший $m$ раз, у которого есть сосед, раздавший карточки $n > m$ раз.

А это про $n > m$ откуда следует, $j$-тый житель мог получать карточки из разных соседей чтобы ему пришлось раздавать $a_j > m$ раз...