<html>
<body>
Generalizing to the case of picking up a single aglet at a time, <br>
which I agree gives more information (and another sequence), <br>
this is what I believe to be true: <br><br>
There are C(2n,k) ways of picking up k aglets out of 2*n aglets. <br>
all of them equally likely. Picking up k aglets leaves 2n - k aglets
<br>
not picked up. Each of these 2n - k aglets must be on a different <br>
shoelace in order to get all the shoelaces. There are C(n,2n - k) <br>
combinations of shoelaces with a not-picked aglet. Each <br>
not-picked aglet can be on either end, so we multiply C(n,2n - k) <br>
by 2^(2n - k) for a total of 2^(2n - k) * C(n,2n - k) ways to get all
<br>
the shoelaces. So we want <br>
So 2^(2n - k) * C(n,2n - k) > (1/2) * C(2n,k). <br>
The following PARI code can be used to calculate k, <br>
it solves for 50% probability, pretending that the problem is
continuous,<br>
then takes the ceiling to get to the realistic k value required.
<br><br>
choose(n,k)=gamma(n+1)/(gamma(n-k+1)*gamma(k+1)) <br>
a(n)=ceil(solve(x=n,2*n,2^(2*n-x)*choose(n,2*n-x)-(1/2)*choose(2*n,x)))
<br>
for(n=3,50,print1(a(n),",")) <br><br>
I get:<br>
1,2,4,5,7,9,10,12,14,15,17,19,21,22,24,26,28,30,31,33,35,37,39,41,42,44,46,48,50,52,53,55,57,59,61,63,65,66,68,70,72,74,76,78,80,81,83,85,87,89,
<br><br>
For the picking up aglet pairs case, I submitted the following for
A106744,<br>
which I would have emailed for review before but I lost access to email
for days.<br><br>
%S A106744 1,2,2,3,3,4,5,6,6,7,8,9,10,11,11,12,13,14,15<br>
%N A106744 Given n shoelaces, each with two aglets; sequence gives number
of aglet<br>
%C A106744 Replacement and extension of terms:<br>
1,1,2,3,4,5,5,6,7,8,9,10,11,11,12,13,14,15,16,17,18,19,20,21,21,22,23,24,25,26,27,28,29,30,31,32,33,33,34,35,36,37,38,39,40,41,42,43,44,45,<br>
%o A106744 (PARI) choose(n,k)=gamma(n+1)/(gamma(n-k+1)*gamma(k+1))<br>
a(n)=ceil(solve(x=n/2,n,2^(2*(n-x))*choose(n,2*(n-x))-(1/2)*choose(2*n,2*x)))<br>
for(n=3,50,print1(a(n),","))<br><br>
I cross-checked these two sequences by rounding the first up to a<br>
multiple of 2 and then dividing by 2.<br><br>
For the other problem about the average number of picks to get all the
shoelaces,<br>
if the wording is 'number of picks required', then that suggests a rule
that once all<br>
the shoelaces can be picked up, we stop for that particular trial.
<br>
Another way to play the game is to wait until k aglets are picked,
regardless of <br>
whether some of the picks are unnecessary, then see if we've got all the
shoelaces,<br>
i.e. we allow unnecessary picks.<br>
These seem like more difficult problems, at least to me.<br><br>
Regarding the word aglet, here's the entry from
<a href="http://www.dictionary.com/" eudora="autourl">www.dictionary.com</a>:<br>
<a href="http://dictionary.reference.com/search?q=aglet" eudora="autourl">http://dictionary.reference.com/search?q=aglet</a><br>
1. A tag or sheath, as of plastic, on the end of a lace, cord, or ribbon
to facilitate its passing through eyelet holes. <br>
2. A similar device used for an ornament.<br>
[Middle English, from Old French<tt> aguillette</tt>, diminutive of<tt>
aguille</tt>, <i>needle</i>, from Vulgar Latin *<tt>acucula</tt>, from
Late Latin<tt> acucula</tt>, diminutive of Latin<tt> acus</tt>,
<i>needle</i>. See<tt> ak- </tt>in Indo-European Roots.] <br>
The word acumen (Quickness, accuracy, and keenness of judgment or
insight.) also comes from <tt>acus.</tt> <br><br>
- Gerald<br><br>
At 09:40 AM 5/16/2005, Brendan McKay wrote:<br>
<blockquote type=cite class=cite cite="">* N. J. A. Sloane
<njas@research.att.com> [050516 23:08]:<br>
> PS I changed it again to read:<br>
> <br>
> %N A106744 Given n shoelaces, each with two aglets; sequence gives
number of ag\<br>
> let pairs that must be picked up to guarantee that the probability
that no shoe\<br>
> lace is left behind is > 1/2.<br><br>
I don't see the point of selecting pairs rather than single aglets.<br>
Since the choosing is done without replacement, the number of pairs<br>
required is just the number of singletons required rounded up to a<br>
multiple of 2 and then divided by 2. So counting singletons gives<br>
more information. Or did I miss something?<br><br>
Brendan. </blockquote></body>
</html>