Jump to content
BrainDen.com - Brain Teasers
  • 0

Analyze this: A simple card game


bonanova
 Share

Question

You must start with a deck that contains a triangular number of cards. From a standard deck, the largest such deck would contain 45 cards. You keep the cards face down throughout, so it does not matter which cards are selected.

The game begins by dealing the cards arbitrarily into a number of piles: anything from one pile of 45 [say] to 45 piles of a single card each. Play continues as a series of moves. A move consists of gathering one card from each pile to form a new pile. The piles are not in any particular order, but one card must be harvested from each pile during a move. Piles with only one card are destroyed, but each move creates a new pile.

The question concerns the end configuration, if one exists, after which any further moves do not change the number of piles nor change the number of cards in the collection of individual piles, without regard for which pile has what number of cards. i.e. four piles with 3 4 7 5 cards or 4 5 7 3 cards are considered the same configuration.

First, does the configuration eventually become stable? OK, there wouldn't be a second question if the answer were No; so as a mental exercise imagine, before trying, what the stable configuration would be. Then play a game to confirm it.

Second, using a deck of 45 cards, what is the maximum number of steps required to reach the stable configuration, and what initial configuration of piles produces it? It may be easier to work this out on paper using state trees than to deal the cards.

Extra credit: provide the second answer for all the triangular numbers possible with a standard deck.

Enjoy. ;)

Link to comment
Share on other sites

13 answers to this question

Recommended Posts

  • 0

37 moves

Start with 45 piles of 1.

1: 45

2: 44 1

3: 43 2

4: 42 1 2

5: 41 1 3

6: 40 2 3

7: 39 1 2 3

8: 38 1 2 4

9: 37 1 3 4

10: 36 2 3 4

11: 35 1 2 3 4

12: 34 1 2 3 5

13: 33 1 2 4 5

14: 32 1 3 4 5

15: 31 2 3 4 5

16: 30 1 2 3 4 5

17: 29 1 2 3 4 6

18: 28 1 2 3 5 6

19: 27 1 2 4 5 6

20: 26 1 3 4 5 6

21: 25 2 3 4 5 6

22: 24 1 2 3 4 5 6

23: 23 1 2 3 4 5 7

24: 22 1 2 3 4 6 7

25: 21 1 2 3 5 6 7

26: 20 1 2 4 5 6 7

27: 19 1 3 4 5 6 7

28: 18 2 3 4 5 6 7

29: 17 1 2 3 4 5 6 7

30: 16 1 2 3 4 5 6 8

31: 15 1 2 3 4 5 7 8

32: 14 1 2 3 4 6 7 8

33: 13 1 2 3 5 6 7 8

34: 12 1 2 4 5 6 7 8

35: 11 1 3 4 5 6 7 8

36: 10 2 3 4 5 6 7 8

37: 9 1 2 3 4 5 6 7 8

Edited by curr3nt
Link to comment
Share on other sites

  • 0

My longest triangle paths before the fixed point so far are:

T2=2, 2 steps, starting at 1-1-1

T3=6, 6 steps, starting at 2-2-1-1

T4=10, 12 steps, starting at 3-2-2-1-1-1 (among others)

T5=15, 20 steps, starting at 4-3-3-2-2-1 (However, I have not exhausted the cases)

I note, without comprehension, that each max = N*(N-1).

Of course, if my T5 answer is wrong, we can forget that...

If true, however, T9=45 would have a max path of 9*8 = 72.

Link to comment
Share on other sites

  • 0

Jim, you harvest one from each of the piles, destroying them. However, your harvest becomes another pile, so you wind up with one pile with 45 cards. Then curr3nt has analyzed what happens there.

And I assume (without proof or even reason to back it up) that we can do 72.

9-6-5-5-4-4-3-3-2-2-1-1

12-8-5-4-4-3-3-2-2-1-1

11-11-7-4-3-3-2-2-1-1

10-10-10-6-3-2-2-1-1

9-9-9-9-5-2-1-1

8-8-8-8-8-4-1

7-7-7-7-7-7-3

7-6-6-6-6-6-6-2

8-6-5-5-5-5-5-5-1

9-7-5-4-4-4-4-4-4

9-8-6-4-3-3-3-3-3-3

10-8-7-5-3-2-2-2-2-2-2

11-9-7-6-4-2-1-1-1-1-1-1

12-10-8-6-5-3-1

11-9-7-7-5-4-2

10-8-7-6-6-4-3-1

9-8-7-6-5-5-3-2

8-8-7-6-5-4-4-2-1

9-7-7-6-5-4-3-3-1

9-8-6-6-5-4-3-2-2

9-8-7-5-5-4-3-2-1-1

10-8-7-6-4-4-3-2-1

9-9-7-6-5-3-3-2-1

9-8-8-6-5-4-2-2-1

9-8-7-7-5-4-3-1-1

9-8-7-6-6-4-3-2

8-8-7-6-5-5-3-2-1

9-7-7-6-5-4-4-2-1

9-8-6-6-5-4-3-3-1

9-8-7-5-5-4-3-2-2

9-8-7-6-4-4-3-2-1-1

10-8-7-6-5-3-3-2-1

9-9-7-6-5-4-2-2-1

9-8-8-6-5-4-3-1-1

9-8-7-7-5-4-3-2

8-8-7-6-6-4-3-2-1

9-7-7-6-5-5-3-2-1

9-8-6-6-5-4-4-2-1

9-8-7-5-5-4-3-3-1

9-8-7-6-4-4-3-2-2

9-8-7-6-5-3-3-2-1-1

10-8-7-6-5-4-2-2-1

9-9-7-6-5-4-3-1-1

9-8-8-6-5-4-3-2

8-8-7-7-5-4-3-2-1

9-7-7-6-6-4-3-2-1

9-8-6-6-5-5-3-2-1

9-8-7-5-5-4-4-2-1

9-8-7-6-4-4-3-3-1

9-8-7-6-5-3-3-2-2

9-8-7-6-5-4-2-2-1-1

10-8-7-6-5-4-3-1-1

9-9-7-6-5-4-3-2

8-8-8-6-5-4-3-2-1

9-7-7-7-5-4-3-2-1

9-8-6-6-6-4-3-2-1

9-8-7-5-5-5-3-2-1

9-8-7-6-4-4-4-2-1

9-8-7-6-5-3-3-3-1

9-8-7-6-5-4-2-2-2

9-8-7-6-5-4-3-1-1-1

10-8-7-6-5-4-3-2

9-8-7-6-5-4-3-2-1

Link to comment
Share on other sites

  • 0

T2=3: 2 steps, starting 1-1-1

T3=6: 6 steps, starting 2-2-1-1

T4=10: 12 steps, starting 3-3-2-1-1

T5=15: 20 steps, starting 4-3-3-2-2-1

T6=21: 30 steps, starting 5-4-3-3-2-2-1-1

T7=28: 42 steps, starting 6-5-4-3-3-2-2-2-1

T8=36: 56 steps, starting 7-6-5-4-3-3-2-2-2-1-1

T9=45: 72 steps, starting 8-7-6-5-4-3-3-3-2-2-1-1

Beyond T4, I have not verified these are maxima, I just tried to emulate the gestalt, and when I got the count that matched my preconceived notion (N*(N-1)), I didn't look further.

Assuming these counts hold up, why is the max = N*(N-1)?

Link to comment
Share on other sites

  • 0

Superprismatic, that's a pretty and nicely organized template for a starting configuration! This whole problem and its solution are provocative.

It's provocative alright! The trouble is, I have no idea how to proceed from here. I hope you have a glimmer of an idea, Captain.

By the way, I've seen this before somewhere. I think it was called Bulgarian Solitaire.

Link to comment
Share on other sites

  • 0

I'm clueless. I was hoping to see some sort of kernel for an induction step--if I remove this card, I get the previously solved problem for N-1. That's one reason I like your observation about a most expensive starting point- it consists of (N-1) and (1) bracketing the fixed point from the previous round. I don't see how that helps, but it is at least a simple pattern such as you like to find in induction...

Link to comment
Share on other sites

  • 0

Has anyone noticed that

penultimate configuration.

That is, you get to the final 1 2 3 ... N configuration only one way.

by a simple change to the final position.

harvest a single card from the largest pile and add a unit pile.

3: 1 1 1 is farthest from 1 2

6: 1 1 2 2 is farthest from 1 2 3

10: 1 1 2 3 3 is farthest from 1 2 3 4

15: 1 1 2 3 4 4 is farthest from 1 2 3 4 5

21: 1 1 2 3 4 5 5 is farthest from 1 2 3 4 5 6

28: 1 1 2 3 4 5 6 6 is farthest from 1 2 3 4 5 6 7

36: 1 1 2 3 4 5 6 7 7 is farthest from 1 2 3 4 5 6 7 8

45: 1 1 2 3 4 5 6 7 8 8 is farthest from 1 2 3 4 5 6 7 8 9

Link to comment
Share on other sites

  • 0

Here's what I got (through exhaustion using what little I know of java) to be the number of starting positions from which you reach the end in the maximum number of steps for T1-8, and the total number of starting positions that will reach the end regardless of how many steps for T1-6:

T1: 1 1

T2: 1 1

T3: 1 1

T4: 3 7

T5: 16 42

T6: 65 239

T7: 293 ??

T8: 1267 ??

I considered a starting position to be one that couldn't be the result of another turn, for example [1, 1, 2, 2, 3] is a starting position but [1, 1, 2, 5] is not.

The starting positions that will get you to the end in the maximum number of steps also aren't all with the minimum amount of decks.

Edited by kbrdsk
Link to comment
Share on other sites

  • 0

Yay for over analyzing!

Start with where you want to end and work backwards. n, n-1, n-2,...,1.

Step 1: Set aside n-1 and add one to all the other numbers n+1,n-1,n-2,...,2. You now have n-1 piles.

Step 2: Set aside the first number you have and add one to all the other numbers. If you don't have enough piles to equal the number you set aside add ones until you do.

Step 3: Repeat step 2 until you can no longer create a new set of piles.

Step 4: Count your steps.

Example of the first few iterations with 45 cards:

9 8 7 6 5 4 3 2 1 (Final Config)

9 7 6 5 4 3 2 1 8->10 8 7 6 5 4 3 2 (Step 1) I have a set of eight piles.

10 8 7 6 5 4 3 2 (This is where I end after Step 1)

8 7 6 5 4 3 2 10->9 8 7 6 5 4 3 1 1 1 (Step 2 I added 3 ones so that I would have 10 total piles.

9 8 7 6 5 4 3 1 1 1 (This is where I end after Step 2)

8 7 6 5 4 3 1 1 1 9->9 8 7 6 5 4 2 2 2 (I don't need to add any ones because I have 9 piles already)

9 8 7 6 5 4 2 2 2 (End of last step.)

8 7 6 5 4 2 2 2 9->9 8 7 6 5 3 3 3 1 (Add 1 one to make 9 piles.)

After working backward 72 steps I get to 8 8 7 6 5 4 3 2 1 1 which is what Bonanova stated was the most dificult starting position. I actually worked the problem forwards and noticed that this was happening afterwards. Oh and I hope it makes sense. >.<

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...