wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Pile Transition
        
(Message started by: jetplan on Jun 21^st, 2006, 1:09pm)

Title: Pile Transition
Post by jetplan on Jun 21^st, 2006, 1:09pm

You have 55 matches arranged in some number of piles of different sizes. You now do the following operation: pick one match from each pile, and form a new pile. You repeat this ad infinitum. What is the steady state? Is it unique?

Generalize the problem to N matches

source: thomer.com

Title: Re: Pile Transition
Post by Sjoerd Job Postmus on Jun 21^st, 2006, 1:53pm

I believe:
If we have M piles, every pile containing one more than the previous, the total number of matches would be:
1 + 2 + 3 + ... + M

I *believe* everything will decay to that... but I can't prove it.

We really have simple mechanism...
1. M = {m1, m2, m3, m4, m5, mn}
2. M' = {m1-1, m2-1, m3-1, mn-1, n}
3. Cancel out every 0-term.
4. If M' = M, stable situation. Break and report
5. Go to 1.

Title: Re: Pile Transition
Post by towr on Jun 21^st, 2006, 2:55pm

I'd hazard to guess for general N, if it is not a triangular number, that there is no steady state. And for triangular N, it's as Sjoerd said.
Proving it of course is a different matter. (Certainly it is clear it is a steady state, but it remains to be proven it's th eonly one. That is, if it wasnt' proved in the othe rthread on this problem. If it was already proven there, it no longer remains to be proven)

Title: Re: Pile Transition
Post by rmsgrey on Jun 22^nd, 2006, 8:26am

on 06/21/06 at 14:55:42, towr wrote:

It's not that hard to prove that it's the unique single-state steady state:

1) [hide]For a steady state with a maximum of M piles, the largest a pile could be is M matches - no pile can be created with more than M matches, and after N moves of the steady state, all surviving piles are ones which have been created since reaching the steady state.[/hide]

2) [hide]For a single state steady state with M piles, there must be exactly one pile of size M - the one that gets created every move (the only other potential source would be the decay of larger piles, which can't exist)[/hide]

3) [hide]The decay of the single pile of size M gives you exactly one pile of each smaller size, so that is the unique single state steady state.[/hide]

For the general case (possibly cyclic steady states and non-triangular totals) I found it helpful to work with the following game, which is equivalent to the match game:

Take an arbitrarily large chess board, with the SW corner in reach and an arbitrary number of counters. Place the counters on the board according to the following rules:

A) Each cell can contain at most one counter.
B) If a cell contains a counter, so must each cell below it in the same column.

Then "normalise" the position by moving each counter in turn to the unoccupied cell furthest West in the same row. This has the effect of sorting the columns to run in decreasing order.

Each normalised position is equivalent to a position in the match game, with the columns representing the piles of matches.

A move consists of moving each counter in turn one cell directly SE. Then take all the counters that fell off the S edge of the board and place them in the (now empty) Westmost column, with each counter due North of every counter it was previously due East of. Finally, normalise if necessary.

This is obviously equivalent to a move in the match game - the effect being to remove one counter from each column and place them in a new column, meaning the two games are equivalent, and any results about the column sizes in the counter game will also apply to pile sizes in the match game.

The rest is hidden so people can have a go themselves if they want.

[hideb]The counter game has added structure. The effect of repeated moves on an individual counter (ignoring normalisation for the moment) is to move it SE along a diagonal, reappearing at the top of the same diagonal when it falls off the bottom. The effect (if any) of normalisation is always to move the counter W onto a shorter diagonal, filling a hole in that shorter diagonal.

If you have a hole on a diagonal, and there's a counter on the next diagonal out, then, because that counter takes one move longer to cycle than the hole does, each time they both cycle, the hole "catches up" to the counter by one place and, eventually, the counter will be normalised into the hole.

Therefore, in a (cyclic) steady state, at most one diagonal can be partially full, with a solid triangle inside, and nothing outside that diagonal. If there are a triangular number of counters (or matches), then the only steady state is the solid triangle; with a non-triangular number of counters, there is the solid triangle corresponding to the nearest lower triangular number, and then the spare counters cycle in the next diagonal out, so, depending on the number, there may be more than one possible cycle (8 is the first number with two stable cycles, and 17 the first with 3).[/hideb]

Title: Re: Pile Transition
Post by Icarus on Jun 22^nd, 2006, 6:30pm

Nice. More generally, let m, k be such that m(m+1) <= 2N < (m+1)(m+2), and k = N - m(m+1)/2.
[hide]Instead of filling just the SW corner with counters, consider the entire board to be filled with counters of two colors, red and white, with the white counters in the SW corner following rmsgreys rules. Note that the "move" process can now be applied to all counters of both colors, but the white counters will behave exactly as before. In the steady state (for non-triangular N), we can divide the board into three parts: the solid, unchanging white triangle in the SW corner, the large unchanging red region filling the NE, and the single red/white diagonal that separates them. With each move, this diagonal shifts one square SW, with the SW-most counter cycling back to the NE end.

As a result, there is a one-to-one correspondence between repeating cycles and arrangements of k white counters and m+1-k red counters in a circle.[/hide]