a puzzle related to artinian group
Edwin Clark
cards are dealt to them.
There is no asumption >on the number of cards a player receive. In each
round, all players with 2 or more cards pass >one card to the left and
one card to the right. Prove that eventually, all players but one have
>exactly one card.
I do not have the solution, so any hint would be highly appreciated.
Please >restrain from posting messages saying "this is obvious", and
the like, because what is required >here is a proof.Thanks a lot
!CheersYannick
For fixed n this is, of course, a cellular automaton. You can allow any
positive integer states for each of the n cells. The transition rule is
such that if a cell has state x >=2 then the state never exceeds x and if
it has state x < 2 then it either stays the same or increase by 1 or 2.
If N is the maximum value of a cell state, then the maximum value of the
states in the next generation can be at most N, unless N = 2 and then a
maximum of 3 is possible in the next generation. It follows that there are
there are only a finite number of possible "global" states, so eventually
it is periodic.
One question might be to figure out which of Wolfram's "four" classes this
cellular automaton lies in.
These remarks don't answer your question, but may be of some interest.
--Edwin
Edwin Clark
For what it is worth, I have just verified that the game always terminates
for n <=9 players no matter how the n-1 cards are dealt. I did it using
brute force with Maple.
--Edwin
Ilmari Karonen
> Yannick wrote:
>> There is no asumption on the number of cards a player receive. In each
>> round, all players with 2 or more cards pass one card to the left and
>> one card to the right. Prove that eventually, all players but one have
>> exactly one card.
>
> states in the next generation can be at most N, unless N = 2 and then a
> maximum of 3 is possible in the next generation. It follows that there are
> there are only a finite number of possible "global" states, so eventually
> it is periodic.
In fact, one can prove a stronger theorem: if there are n players and
less than 2n cards, each player will at some point hold 0 or 1 cards.
An obvious corollary to the above is that in the eventual static or
cyclic state no player can hold more than 3 cards at any time.
To prove the theorem above, one must first note that only players
holding 0 or 1 cards can gain more cards on the next turn. Therefore,
if a player ever loses a card, he can only regain the same number of
cards he originally had by going down to 0 or 1 cards and then back up.
We already know the game will eventually settle into a repeating cycle
(of 1 or more turns). If a player has N cards at some point in the
cycle, he must also have N cards one cycle later. This means that
either he must never lose cards during the cycle or the number of cards
he holds must at some point be 0 or 1.
Assume the player has more than one card and never loses any cards.
This means the players on either side of him must also always hold more
than one card. By induction, we can show that _all_ players must always
hold more than one card.
But this is impossible if there are less than 2n cards. Therefore the
assumption must be false, and each player must hold less than two cards
at some point in the cycle.
--
Ilmari Karonen
If replying by e-mail, substitute .net for .invalid in address.
Ilmari Karonen
> For what it is worth, I have just verified that the game always terminates
> for n <=9 players no matter how the n-1 cards are dealt. I did it using
> brute force with Maple.
Brute force, Perl and the theorem I posted a while ago got me to n=15.
I could probably do n=16, but n=17 would almost certainly take too much
memory. A rewrite in C might get me up to n=18 or so.
Of course, all that feels pretty pointless, given that a general proof
_shouldn't_ be that hard. Oh well, it was a fun programming exercise...