[seqfan] Re: New sequence from XKCD - Urinal protocol

[Jack Brennen]

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/
> 
>