Jump to content
BrainDen.com - Brain Teasers
  • 0


bonanova
 Share

Question

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! B))

Edited by bonanova
change 49 to 45
Link to comment
Share on other sites

11 answers to this question

Recommended Posts

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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 by wolfgang
Link to comment
Share on other sites

  • 0

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 by Placidus
Link to comment
Share on other sites

  • 0

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 by kevink
Link to comment
Share on other sites

  • 0

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!

Link to comment
Share on other sites

  • 0

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 n2n is an upper bound for the periodicity.

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

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...