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

[EUgeneUS]

manul91
1. Разберитесь с доказательством, что в случае прохождения через цикл, каждый житель раздавал карточки одинаковое количество раз. Вот тут:

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

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

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

2. Далее разберитесь с раскраской. Например тут:

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

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

и далее до конца этого сообщения (откуда цитата выше).

[vicvolf]

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

У некоторых из них есть карточки, 60000 штук на всех.

Этого условия недостаточно, чтобы ответить на Ваш вопрос:

Цитата:

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

Потому что в этом случае возможно зацикливание

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

Например, распределили карточки, что у одного соседа -4, а другого 3. Один другому и будет передавать.

[mihaild]

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

Что значит "все жители участвуют в цикле"?

Рассматриваем случай последовательных передач (если при любом наборе последовательных передач всегда, начиная с некоторого момента, карточки будут минимум у трети, то и при одновременной передаче начиная с некоторого момента карточеки будут минимум у трети).
Последовательность передач называется циклом, если в результате все остаются при своих (и соответственно можно эту же последовательность повторить еще раз).
Человек участвует в цикле $n$ раз, если он за эту последовательность отдает карточки $n$ раз.

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

А это про $n > m$ откуда следует

Из связности графа. Рассмотрите путь от жителя, раздававших карточки $m$ раз, до жителя, раздававшего карточки больше $m$ раз.

vicvolf, карточки отдаются комплектами по $4$. Если у Васи $4$ карточки, у соседа Пети $3$, то после хода у Васи будет $0$ карточек, у Пети $4$. После хода Пети у Васи будет $1$ карточка и он никому ничего отдать не сможет.

[manul91]

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

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

Что значит "все жители участвуют в цикле"?

Рассматриваем случай последовательных передач (если при любом наборе последовательных передач всегда, начиная с некоторого момента, карточки будут минимум у трети, то и при одновременной передаче начиная с некоторого момента карточеки будут минимум у трети).
Последовательность передач называется циклом, если в результате все остаются при своих (и соответственно можно эту же последовательность повторить еще раз).
Человек участвует в цикле $n$ раз, если он за эту последовательность отдает карточки $n$ раз.

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

А это про $n > m$ откуда следует

Из связности графа. Рассмотрите путь от жителя, раздававших карточки $m$ раз, до жителя, раздававшего карточки больше $m$ раз.

Спасибо, теперь хотя бы понятно о чем речь ; )
А в чем состоит задача в случае последовательных передач, из формулировки как бы не совсем ясно:
a) Доказать что всегда существует некая последовательность передач, которая приведет к статичном состоянии (конец игры)?
б) Доказать что любая последовательная передача, обязана рано или поздно привести к статичном состоянии (конец игры)?

Это ведь разные вещи (если доказать для параллельной передаче, значит доказано и для a). Если доказать б) следует и верность и в параллельном случае).

[vicvolf]

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

vicvolf, карточки отдаются комплектами по $4$.

Такого в условии нет.

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

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

Если у одного человека 4 карточки и он отдал одному соседу 1 карточку, то у него осталось только 3 карточки и по условию он соседям больше карточки не передает.

[mihaild]

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

А в чем состоит задача в случае последовательных передач, из формулировки как бы не совсем ясно

Формулировка

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

через какое-то ограниченное время не менее трети людей будут иметь хотя бы одну карточку

стандартно подразумевает, что при любой последовательности передач так получится. И в целом формулировка в первом посте четкая, я не понимаю, почему все, включая меня, решили, что передача одновременная.
Ну и в любом случае задача уже положительна решена для последовательной передачи, из этого следует решение для одновременной.

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

Если у одного человека 4 карточки и он отдал одному соседу 1 карточку

То он не отдал соседям по одной карточке.

[vicvolf]

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

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

Пожалуйста, поясните, что это означает. Я понял, что если человек имеет 4 карточки, то он отдает 1 карточку только одному соседу. Потому что после этого у него будет только 3 карточки и он по условию больше соседям карточки не дает. Я правильно понял?

[wrest]

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

Я правильно понял?

Нет, если у него не менее 4х карточек, то он отдаёт 4 сразу, за один ход, если менее -- то ничего не отдаёт.
Если у него >4 и у всех 4-х соседей >4, то он отдаёт им, а они отдают ему, и у него остается сколько было.

Это пошаговая, дискретнея история, а не непрерывная.