wu :: forums - Print Page


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

        riddles >> medium >> Taking eggs from a carton
        
(Message started by: fiziwig on Jun 13^th, 2007, 2:34pm)

Title: Taking eggs from a carton
Post by fiziwig on Jun 13^th, 2007, 2:34pm

I'm not sure if this one is easy or medium, so here goes:

Begin with a full carton of 12 eggs arranged in two rows of six.

For each egg in the front row, remove the corresponding egg in the back row.
This removes six of the eggs, emptying the back row.
Next, take the remaining six eggs and distribute them randomly among the twelve cups in the carton.
Now repeat that procedure, removing an egg from the back row if and only if the matching cup in the front row also has an egg. Then once more randomly distribute all remaining eggs among the twelve cups in the carton.

On average, how many times must these two steps be repeated until there is only one egg remaining in the carton?

What is the average number of remaining eggs after S steps?

What if the egg carton holds 18 eggs in two rows of 9?
What if the carton holds 2X eggs in two rows of X?

Bonus question: Given a very large egg carton, with an unknowable number of cups in each of the two rows, is there a fixed procedure for non-randomly distributing the remaining eggs on each step that will minimize the numbers of steps to reach one egg remaining? (If such a procedure exists then it can form the basis of a fast way of factorizing a large composite N where the unknown-size carton has 2 rows of (p-1)/2 cups where p is a factor of N. Bonus points for explaining why that is true.)

Title: Re: Taking eggs from a carton
Post by towr on Jun 13^th, 2007, 2:37pm

on 06/13/07 at 14:34:09, fiziwig wrote:

Bonus question: Given a very large egg carton, with an unknowable number of cups in each of the two rows, is there a fixed procedure for non-randomly distributing the remaining eggs on each step that will minimize the numbers of steps to reach one egg remaining?

Always move them to one side of the carton, lets say right.
Or did you have something else in mind?

Title: Re: Taking eggs from a carton
Post by fiziwig on Jun 13^th, 2007, 2:44pm

Hmmm. I'm going to have to slightly re-think how to state the problem regarding the fixed procedure to make it correspond to the problem of factorization. The difficulty in using it for factorization is that you don't know how big the carton is so you don't know how to locate the right side. In other words, you have a substantially larger carton with N-1 cups which is, out of sight to you, mapped into the smaller, but unknown size carton with p-1 cups. (I'm not explaining that part very well. Let me mull it over. But the first parts of the problem are still valid as stated.)

Title: Re: Taking eggs from a carton
Post by towr on Jun 13^th, 2007, 3:12pm

It is a bit odd to consider a carton you can't find the beginning of. You could never empty it if that were the case.
But if you prefer, you could choose an arbitrary point 0, somewhere along the carton. And either move eggs toward that; or for all integer k move eggs at (2k-1)*2ⁱ behind 2k*2ⁱ each step i (starting at 0).

Title: Re: Taking eggs from a carton
Post by fiziwig on Jun 13^th, 2007, 3:56pm

I probably should have left that whole part of the problem out since I didn't think it through well enough.

The problem is that the cups represent residues mod P (a factor of N) , but we really only know the residues mod N, so we aren't really sure "where" the "cups" are in the hidden "egg carton".

If, for example, I start with all 40 residues mod 41 (using residues > 0) and square them (mod 41) I'm left with 20 unique residues (i.e., I've removed half the eggs and shuffled the remaining 20 eggs among the 40 cups). Now if I square the residues again I end up with 10 unique residues. Then, instead of squaring I can do x <- x^2+1 on each step, or some other randomly chosen process.

The point is, starting with two random numbers q and r < N, and applying some such operation (mod N rather than mod P) over and over, the probability that f(q) mod P == f(r) mod P gets higher and higher, meaning that gcd(N,f(q)-f(r)) = P will reveal the factor p of N.

The number of steps it takes to get down to one egg in a carton of P-1 cups is the number of steps it takes to find P a factor of N. But a shuffling procedure that needs to know how big P is, is forbidden because P is not known beforehand.

Title: Re: Taking eggs from a carton
Post by Eigenray on Jun 20^th, 2007, 10:45pm

With 2n holes, the probability of going from k to k-r eggs in one step is

C(n, r)*2^k-2rC(n-r, k-2r) / C(2n, k).

Putting these transition probabilities into a matrix A, we can find the expected number of steps required by solving the vector equation e = (0,1,1,1,1,1) + e.A. For n=6, the expected number of steps, starting from 12 eggs, is 1040062/54825 ~ 18.97. For n=9, it is 10766875055207/352237767777 ~ 30.57. For large n, it seems to be well approximated by E ~ 4n - log n - 4.

After s+1 steps, the expected number of eggs remaining is given {1,2,3,4,5,6}.A^s.{0,0,0,0,0,1}, which can be found in closed form:

1 + [ 45240 210^s + 37345 168^s + 18915 112^s + 6111 56^s + 1029 16^s] / [ 21728 231^s ] ~ 1 + 2.08*(10/11)^s.

For s=0,1,2,..., this works out to be
{6, 4.64, 3.85, 3.33, 2.95, 2.67, 2.44, 2.26, 2.11, 1.98, ...}.

For n=9, we have
{9, 6.88, 5.67, 4.87, 4.29, 3.86, 3.51, 3.23, 3.00, 2.80, ...}.

In general, the expected number of eggs after s steps will have the form

1 + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=2ⁿ c_k [C(n,k)2^k/C(2n,k)]^s,

which is approximately 1 + c*[(2n-2)/(2n-1)]^s for large s.