Sign in to follow this  
Followers 0

Analyze this: A simple card game

14 posts in this topic

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Posted · Report post

The first part is easy...

n such that sum of 1 to n is 45, so

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

0

Share this post


Link to post
Share on other sites

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

Question. If we start with 45 piles of one card each, do we immediately destroy all piles and finish with a configuation of no cards and no piles in no moves?

0

Share this post


Link to post
Share on other sites

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Posted · Report post

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)?

0

Share this post


Link to post
Share on other sites

Posted · Report post

I've exhaustively checked through T11 and it seems that TN=N*(N+1)/2 has maximum steps of N*(N-1) using

the smallest possible number (N+1) of starting piles: N-1,N-1,N-2,N-3,...,4,3,2,1,1.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites

Posted · Report post

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

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.