13 replies to this topic

[CaptainEd]

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

[bonanova]

Has anyone noticed that

Spoiler for there is a unique

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

Spoiler for you can get the most difficult starting position

by a simple change to the final position.

Spoiler for just

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

[kbrdsk]

Spoiler for might be helpful...

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, 17 August 2012 - 05:10 PM.

[Rob_Gandy]

Yay for over analyzing!

Spoiler for How to make the longest chain (maybe)

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