[seqfan] Re: New sequence from XKCD - Urinal protocol
jfb at brennen.net
Wed Sep 2 19:56:23 CEST 2009
I think this sequence is recursively defined as:
u(1) = u(2) = 1
u(3) = 2
For n>3, let m=(n+1)/2, then u(n)=u(floor(m))+u(ceil(m))-1.
Should be easy to check any closed formula, possibly prove by induction.
David Radcliffe wrote:
> An interesting new(?) sequence was described in Randall Munroe's XKCD blog.
> Suppose that there is a row of n urinals. The first guy chooses a
> urinal at one of the ends, and each subsequent guy chooses a urinal
> that is as far as possible from the other guys. No guy will choose a
> urinal that is adjacent to an occupied urinal. Let f(n) be the
> maximum number of urinals that can be occupied using this protocol.
> Munroe claims that f(n) = 1+2^floor(log(n-2)-1)+max(0,
> n-(3/2)*2^floor(log(n-2))-1) for n>2, but I have not verified this.
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan