[bonanova]

In partition theory, a counting number n is expressed as the sum of positive integers, without regard to order.

If n is a triangular number it has a special partition, namely 1+2+3+4+ ...

Examples of triangular numbers are 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, and so on.

If we select a triangular number of cards from a deck of 52, the largest number we'd have is 49 45.

Let's go with 49 45cards [any 49 45cards, it doesn't matter] and play a little game.

Deal the cards into some number of piles, each pile having some number of cards.

Doesn't matter how many piles - could be a single pile, could be 49 45 piles. Your choice.

What you've done is create a partition of the number 49 45.

Play proceeds as follows:

.

1. Remove 1 card from each pile.
2. Place these cards together and use them to form a new pile.

.

For example, if you began with 49 45 piles of one card each, after the first play you'd have a single pile of 49 45 cards. After two plays you'd have a pile of 48 cards and a pile of 1 card. And so on. Piles are created and sometimes piles are used up.

Continue repeating steps 1 and 2.

The puzzle is to find the answer to these questions:

1. Does the game ever get stuck in an endless loop?
   i.e. Does a partition ever revert to a previous partition?
   .
2. Does the game ever reach a stable state?
   i.e. Is a partition ever reached that is invariant to steps 1 and 2?
   .

In answering these questions remember that, in a partition, the order does not matter.

So in a game of 3 cards, piles of 1 1 and 1 card and a single pile of 3 cards are different partitions.

But piles of 1 and 2 cards and piles of 2 and 1 cards are the same partition.

Shuffle up, deal and play the game, or just think about it.

Either way, enjoy!

Edited October 29, 2010 by bonanova
change 49 to 45

[Guest]

If we select a triangular number of cards from a deck of 52, the largest number we'd have is 49.

I lost you at that part, 49 isn't a triangular number...

[Guest]

1-Does the game ever get stuck in an endless loop?

i.e. Does a partition ever revert to a previous partition?

2-Does the game ever reach a stable state?

i.e. Is a partition ever reached that is invariant to steps 1 and 2?

1-Yes. The number of combinations of 49 cards in piles is finite. After a combination is always the same combinatión. So, there are loops.

2-Only if the number of cards is triangular.

[Guest]

1-if the chosen cards of piles say the max< possiblity deals with 49 then infinite steps can evoke

2-

[araver]

1. Always.

2. Not for 49 cards.

1. Always in a game of M cards. The number of possible pile configurations at any time during the game is the number of partitions of M, denoted P(M).

Dirichet's principle guarantees that in P(M)+1 consecutive rounds there are two identical configurations and since the game is deterministic, these configurations lead to an endless loop.

2. Assume there is a stable state in a game of M cards.

Let n>0 be the number of piles in such a stable state reached in round N.

Then one round later, in round N+1 we must have exactly n piles.

Reorder the piles as increasing in size: 0 <a(1) <= ... <= a(n) piles in round N.

Denote A={a(1),..., a(n)}.

Then a(1)-1,a(2)-1 .... a(n)-1 and n are piles in round N+1. Since it's a stable state it must have only n piles in round N+1 as well, so exactly one pile out of {a(1)-1,a(2)-1, .... ,a(n)-1,n} must be empty. Since n>0 and the others are still sorted 0<=a(1)-1 <= ... <= a(n)-1, then a(1)=1.

So the piles in round N are exactly: B={a(2)-1, .... ,a(n)-1,n} and a(1)=1.

Also if n>=2, a(2)>1. If a(2)=1, then it would become empty in round N+1 and that means less piles than in round N.

One of the piles in B must be 1 since it's the same as the previous state 1=a(1) <= ... <= a(n).

So either n=1 (which means M=1) or a(2)=2.

For n>=2 we have:

A={1,2,a(3),...,a(n)}

B={1,a(3)-1, ..., a(n)-1, n}

With the same argument, either n=2 (which means M=3) or a(3)-1=2. Latter case implies:

A={1,2,3,...,a(n)}

B={1,2,a(4)-1,...,a(n-1),n}.

and so on ... (n=3 AND M=6) OR (a(4)=4).

If the number of cards is known (e.g. M=49) then after a finite number of steps, the induction process stops as we run out of cards.

If M is a triangular number then the process is successful A={1,2,...,n-1,n} and M=n*(n+1)/2.

If M is not triangular (e.g. M=49) then the last step is not succesful and leads to a contradiction.

E.g. for 49: A={1,2,3,4,5,6,7,8,a(9),...,a(n)}. Since 1+2+..+8=36 there are only 13 cards remaining. Since a(9)>=9 and a(n)>=9 then n<=9 (otherwise we need at least 9*2=18 cards). Therefore n=9 and a(9)=13. Then B={1,2,3,4,5,6,7,12,9} and B=/=A.

So the only stable states are A={1,2,3,...,n-1,n} and only for triangular numbers M=n*(n+1)/2.

To see posible states that lead in one round to a stable state, assume that in round N>1 we reach state A={1,2,3,...,n-1,n}. Then there are at most n piles in round N-1 since no pile is bigger than n.

Also, since there are n piles in round N, there must have been at least n-1 piles in round N since the game at most creates 1 extra pile per round.

If the previous round had n piles, then exactly one pile from round N-1 has dissapeared so it had 1 card, the pile with n cards is the new one which means 2,3,..., n were the rest of the piles in the previous round. So the previous round was identical to this round.

If the previous round had n-1 piles, then the pile with n-1 piles is the new pile and no piles have been emptied in round N so the previous round is {2,3,4,...,n-1,n+1}. Which means there are other possible configuration leading to a stable state for a triangular number of cards.

[wolfgang]

Hi my friends.. Let me suppose 49 is a triangular No.(which is not)! then the piles of: 1 2 3 4 5 7 8 9 10 cards ( nine piles)will enter an endless loop!...like this:- 0 1 2 3 4 6 7 8 9 9 -- 0 1 2 3 5 6 7 8 8 9-- 0 1 2 4 5 6 7 7 8 9 -- 0 1 3 4 5 6 6 7 8 9 -- 0 2 3 4 5 5 6 7 8 9-- 1 2 3 4 4 5 6 7 8 9-- 0 1 2 3 3 4 5 6 7 8 10 -- 0 1 2 2 3 4 5 6 7 9 10-- 0 1 1 2 3 4 5 6 8 9 10 -- 0 0 1 2 3 4 5 7 8 9 10.......which is the start position ! and there will be no stable state.

Edited October 29, 2010 by wolfgang

[bonanova]

I lost you at that part, 49 isn't a triangular number...

My bad - of course I meant 45.

Thanks.

[Guest]

uh 48 is triangular, working under the assumption that it need only be divisible by three, and therefore work as the perimeter of an equilateral triangle

Edit: nevermind i just saw the definition of triangular numbers again, and this time it registered, disregard this post

Edited October 29, 2010 by Placidus

[Guest]

just by working it around in my head, ive come to the plausible conclusion that the answer to question 1 is yes, and that the answer to question 2 is no

[Guest]

Nice puzzle. I did notice one thing in my simulation and wanted to know if anyone can explain why.

If the # of cards is between 3 and 6 (2 triangular numbers), when an endless loop is found the period is 3 (every three moves results in the same set of piles).

between 6 and 10 cards (two more triangular #'s), the period is 4.

between 10 and 15, the period is 5

between 15 and 21, the period is 6

and so on..

every time you hit a triangular #, the period increases by 1.

Edited October 29, 2010 by kevink

[bonanova]

Nice puzzle. I did notice one thing in my simulation and wanted to know if anyone can explain why.

If the # of cards is between 3 and 6 (2 triangular numbers), when an endless loop is found the period is 3 (every three moves results in the same set of piles).

between 6 and 10 cards (two more triangular #'s), the period is 4.

between 10 and 15, the period is 5

between 15 and 21, the period is 6

and so on..

every time you hit a triangular #, the period increases by 1.

I would expect the period to increase with the size of the deck, but not in this interesting way.

This short article tells us a little more about it, but does not mention your result explicitly.

Nice result!

[bonanova]

The literature on Bulgarian Solitaire gives an upper bound for periodicity when N is not triangular and the number of plays to reach stable partition with N is triangluar.

If N = 1+2+. . .+n+k, with 0 <= k < n, then n² −n is an upper bound for the periodicity.

When N is the k^th triangular number, the stable partition k, k-1, ... 3, 2, 1 will be reached in no more than k² - k plays.