login
Given n shoelaces, each with two aglets; sequence gives number of aglets that must be picked up to guarantee that the probability that no shoelace is left behind is > 1/2.
1

%I #4 Mar 30 2012 17:28:32

%S 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,

%T 44,46,48,50,52,53,55,57,59,61,63,65,66,68,70,72,74,76,78,80,81,83,85,

%U 87,89

%N Given n shoelaces, each with two aglets; sequence gives number of aglets that must be picked up to guarantee that the probability that no shoelace is left behind is > 1/2.

%C An aglet is a tag or sheath on the end of a lace to facilitate its passing through eyelet holes.

%C There are C(2n,k) ways of picking up k aglets out of 2*n aglets. All of them are 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.

%C 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).

%C 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.

%C Fieggen's site has pictures of aglets (and hints on repairing them). - _N. J. A. Sloane_ May 16 2005

%H Ian Fieggen, <a href="http://www.fieggen.com/shoelace/agletrepair.htm">Aglet repair</a>

%o (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,x))) for(n=3,50,print1(a(n),","))

%Y See A106744 for another version.

%K nonn

%O 1,2

%A _Gerald McGarvey_, May 22 2005