shoelaces and aglets

[Gerald McGarvey]

Generalizing to the case of picking up a single aglet at a time,
which I agree gives more information (and another sequence),
this is what I believe to be true:

There are C(2n,k) ways of picking up k aglets out of 2*n aglets.
all of them equally likely. Picking up k aglets leaves 2n - k aglets
not picked up. Each of these 2n - k aglets must be on a different
shoelace in order to get all the shoelaces. There are C(n,2n - k)
combinations of shoelaces with a not-picked aglet. Each
not-picked aglet can be on either end, so we multiply C(n,2n - k)
by 2^(2n - k) for a total of 2^(2n - k) * C(n,2n - k) ways to get all
the shoelaces. So we want
So 2^(2n - k) * C(n,2n - k) > (1/2) * C(2n,k).
The following PARI code can be used to calculate k,
it solves for 50% probability, pretending that the problem is continuous,
then takes the ceiling to get to the realistic k value required.

choose(n,k)=gamma(n+1)/(gamma(n-k+1)*gamma(k+1))
a(n)=ceil(solve(x=n,2*n,2^(2*n-x)*choose(n,2*n-x)-(1/2)*choose(2*n,x)))
for(n=3,50,print1(a(n),","))

I get:
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, 


For the picking up aglet pairs case, I submitted the following for A106744,
which I would have emailed for review before but I lost access to email for 
days.

%S A106744 1,2,2,3,3,4,5,6,6,7,8,9,10,11,11,12,13,14,15
%N A106744 Given n shoelaces, each with two aglets; sequence gives number 
of aglet
%C A106744 Replacement and extension of terms:
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,
%o A106744 (PARI) choose(n,k)=gamma(n+1)/(gamma(n-k+1)*gamma(k+1))
a(n)=ceil(solve(x=n/2,n,2^(2*(n-x))*choose(n,2*(n-x))-(1/2)*choose(2*n,2*x)))
for(n=3,50,print1(a(n),","))

I cross-checked these two sequences by rounding the first up to a
multiple of 2 and then dividing by 2.

For the other problem about the average number of picks to get all the 
shoelaces,
if the wording is 'number of picks required', then that suggests a rule 
that once all
the shoelaces can be picked up, we stop for that particular trial.
Another way to play the game is to wait until k aglets are picked, 
regardless of
whether some of the picks are unnecessary, then see if we've got all the 
shoelaces,
i.e. we allow unnecessary picks.
These seem like more difficult problems, at least to me.

Regarding the word aglet, here's the entry from www.dictionary.com:
http://dictionary.reference.com/search?q=aglet
1. A tag or sheath, as of plastic, on the end of a lace, cord, or ribbon to 
facilitate its passing through eyelet holes.
2. A similar device used for an ornament.
[Middle English, from Old French aguillette, diminutive of aguille, needle, 
from Vulgar Latin *acucula, from Late Latin acucula, diminutive of Latin 
acus, needle. See ak- in Indo-European Roots.]
The word acumen (Quickness, accuracy, and keenness of judgment or insight.) 
also comes from acus.

- Gerald

At 09:40 AM 5/16/2005, Brendan McKay wrote:
>* N. J. A. Sloane <njas at research.att.com> [050516 23:08]:
> > PS  I changed it again to read:
> >
> > %N A106744 Given n shoelaces, each with two aglets; sequence gives 
> number of ag\
> > let pairs that must be picked up to guarantee that the probability that 
> no shoe\
> > lace is left behind is > 1/2.
>
>I don't see the point of selecting pairs rather than single aglets.
>Since the choosing is done without replacement, the number of pairs
>required is just the number of singletons required rounded up to a
>multiple of 2 and then divided by 2. So counting singletons gives
>more information. Or did I miss something?
>
>Brendan.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20050521/93530ec3/attachment-0001.htm>