Author |
Topic: Taking eggs from a carton (Read 673 times) |
|
fiziwig
Junior Member
Posts: 78
|
 |
Taking eggs from a carton
« on: Jun 13th, 2007, 2:34pm » |
 Quote  Modify
|
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.)
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Taking eggs from a carton
« Reply #1 on: Jun 13th, 2007, 2:37pm » |
Quote Modify
|
on Jun 13th, 2007, 2:34pm, 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?
|
| « Last Edit: Jun 13th, 2007, 2:38pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
fiziwig
Junior Member
Posts: 78
|
|
Re: Taking eggs from a carton
« Reply #2 on: Jun 13th, 2007, 2:44pm » |
Quote Modify
|
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.)
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Taking eggs from a carton
« Reply #3 on: Jun 13th, 2007, 3:12pm » |
Quote Modify
|
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)*2i behind 2k*2i each step i (starting at 0).
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
fiziwig
Junior Member
Posts: 78
|
|
Re: Taking eggs from a carton
« Reply #4 on: Jun 13th, 2007, 3:56pm » |
Quote Modify
|
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.
|
| « Last Edit: Jun 13th, 2007, 3:58pm by fiziwig » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Taking eggs from a carton
« Reply #5 on: Jun 20th, 2007, 10:45pm » |
Quote Modify
|
With 2n holes, the probability of going from k to k-r eggs in one step is
C(n, r)*2k-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}.As.{0,0,0,0,0,1}, which can be found in closed form:
1 + [ 45240 210s + 37345 168s + 18915 112s + 6111 56s + 1029 16s] / [ 21728 231s ] ~ 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 +  k=2n ck [C(n,k)2k/C(2n,k)]s,
which is approximately 1 + c*[(2n-2)/(2n-1)]s for large s.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print