shoelaces and aglets

[Neil Fernandez]

Hi Gerald and many thanks for this.

I think this is right, with the complication that for k>2 one cannot
test using increasing values of k starting with 1, because for low
values 2*(n-k) > n and C(n,2*(n-k)) is undefined - but of course one can
decrement starting with k=n.

A generalisation would be to use n shoelaces each with p aglets, and
pick up k r-tuplets of aglets each time. Here p=2 and r=2.

The sequence begins:

1,2,2,3,3,4,5,6,6,7,8,9,10,11,11,12,13,14,15

which is not in the OEIS (although A086861 with an initial 1 inserted is
the same for the first 18 terms).

I get a(100)=89, a(200)=184, a(1000)=964. I wonder what a(n)/n converges
to?

I have submitted the sequence as:

%I A000001
%S A000001 1,2,2,3,3,4,5,6,6,7,8,9,10,11,11,12,13,14,15
%N A000001 Aglet pairs to be picked up, given n shoelaces, so that
probably none remain
%C A000001 Assistance in extending sequence given by Gerald McGarvey
<Gerald.McGarvey at comcast.net>
%e A000001 a(2)=2 because given 2 shoelaces, p=1/3 that the first two
aglets picked up will be on a single shoelace, requiring another pick-
up, and p=2/3 that they won't, so the mean no. of pick-ups is (1/3)*2 +
(2/3)*1 = 4/3, for which the ceiling is 2.
%O A000001 1
%K A000001 ,nonn,
%A A000001 N Fernandez (primeness at borve.demon.co.uk), May 16 2005

Neil

In message <6.1.1.1.0.20050516001145.02650970 at mail.comcast.net>, Gerald
McGarvey <Gerald.McGarvey at comcast.net> writes

>Here's my take on this...
>
>Suppose you pick up 2*k aglets out of 2*n aglets, there are
>C(2n,2k) ways of doing this.
>
>That leaves 2*(n-k) aglets not-picked, we want none of the not-picked
>aglets to be on the same shoelace.
>
>How many ways are there of not-picking 2*(n-k) aglets such that no two
>are on the same shoelace?
>They must be on 2*(n-k) different shoelaces, which are chosen
>from n shoelaces; there are C(n,2*(n-k)) ways of doing this choosing.
>But each not-picked aglet can be on either end of its shoelace,
>so multiply each of those ways by 2^(2*(n-k)) for a total of
>2^(2*(n-k)) * C(n,2*(n-k)).
>
>So we want 2^(2*(n-k)) * C(n,2*(n-k)) to be more than 1/2 of C(2n,2k).
>
>Is that correct?
>
>Gerald
>
>At 08:49 PM 5/15/2005, Neil Fernandez wrote:
>>You've got n shoelaces in a box. Each shoelace has two aglets.
>>
>>You pick up a pair of aglets at random, that may or may not be on the
>>ends of the same shoelace.
>>
>>a(n) is the number of times you must do this, without replacement, to
>>have a better than evens chance of removing all the shoelaces if you tug
>>on all of the aglets you've got in your hand.
>>
>>I get the mean number of necessary times as 1, 4/3, 33/15, 102/35,...
>>giving a sequence a(n):
>>
>>1, 2, 3, 3, ...
>>
>>Help would be appreciated in extending this sequence.

-- 
Neil Fernandez