[seqfan] Re: New sequence from XKCD - Urinal protocol
Jack Brennen
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[2](n-2)-1)+max(0,
> n-(3/2)*2^floor(log[2](n-2))-1) for n>2, but I have not verified this.
>
> http://blag.xkcd.com/2009/09/02/urinal-protocol-vulnerability/
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
>
More information about the SeqFan
mailing list