[seqfan] Re: puzzle suitable to make a sequence ?

Andrew Weimholt andrew.weimholt at gmail.com
Tue May 11 13:05:45 CEST 2010

If I'm not mistaken, the case for 3 balls, is n appears 1+t(n-1) times
where t(n) = A000217(n).

Perhaps more interesting than minimizing the worst case number of
throws would be to minimize
the worst case number of times you have to climb a flight of stairs.
(Let's say going down stairs is easy, so we don't count it, but going
upstairs is tiring
so we seek to minimize it).

For the two ball case, if we start at floor i, and the ball breaks, we
must throw the ball from
floors 1 through i-1 in ascending order, but we also must retrieve the
ball between each throw.
As it takes k-1 climbs to get to the kth floor, it takes A000217(i-2)
climbs for the worst case
test of floors 1 through i-1 with only 1 ball, plus we already climbed
i-1 flights to perform the
first throw. If the ball doesn't break, then instead of retrieving the
first ball right away,
we can ascend to floor j (a climb of j-i), and throw the second ball
(retrieving two balls at a time until one breaks).


for given n, what is the minimum worst case number of climbs?
for given n, what is the worst case number of throws when minimizing
climbs instead of throws?
for given n, what is the lowest starting floor which will allow us to
minimize the worst case number of climbs?

what is the answer to the above question for the 3 ball case?

As it's (way) past my bedtime, I won't be pondering these anymore
tonight, but perhaps
someone in another time zone will take up the challenge and have
answers before I awake :-)


More information about the SeqFan mailing list