Prev: Gravity and black holes
Next: Is This really a Proof that Standard Math is Inconsistent?
From: Jim Ferry on 18 Jan 2010 01:41
Suppose a bathroom has n urinals in a row which are initially
unoccupied. Men approach one by one, balking at any urinal adjacent
to one in use. Assuming they select urinals uniformly at random from
the set of those neither in use nor adjacent to one in use (and, for
simplicity, that they never leave -- think Austin Powers), what is the
expected fraction of urinals in use when the row fills up, in the
limit n -> infinity? The answer clearly lies between 1/3 and 1/2 (the
densities of the least and most efficient packings), so you might
think "Cinch! 1/e", but no, the density is greater than 40%.

BTW, some of you may have seen the very row of urinals which inspired
this problem: it was in the bathroom near the Employment Center at
last week's Joint Math Meetings in San Francisco.
From: Henry on 18 Jan 2010 04:43
On 18 Jan, 06:41, Jim Ferry <corkleb...(a)hotmail.com> wrote:
> Suppose a bathroom has n urinals in a row which are initially
> unoccupied.  Men approach one by one, balking at any urinal adjacent
> to one in use.  Assuming they select urinals uniformly at random from
> the set of those neither in use nor adjacent to one in use (and, for
> simplicity, that they never leave -- think Austin Powers), what is the
> expected fraction of urinals in use when the row fills up, in the
> limit n -> infinity?  The answer clearly lies between 1/3 and 1/2 (the
> densities of the least and most efficient packings), so you might
> think "Cinch!  1/e", but no, the density is greater than 40%.
>
> BTW, some of you may have seen the very row of urinals which inspired
> this problem:  it was in the bathroom near the Employment Center at
> last week's Joint Math Meetings in San Francisco.

The expected density tends towards 1/2 - exp(-2)/2 = 0.432... from
above as n increases


From: Ilmari Karonen on 18 Jan 2010 10:32
On 2010-01-18, Jim Ferry <corklebath(a)hotmail.com> wrote:
> Suppose a bathroom has n urinals in a row which are initially
> unoccupied. Men approach one by one, balking at any urinal adjacent
> to one in use. Assuming they select urinals uniformly at random from
> the set of those neither in use nor adjacent to one in use (and, for
> simplicity, that they never leave -- think Austin Powers), what is the
> expected fraction of urinals in use when the row fills up, in the
> limit n -> infinity?

The assumption that nobody ever leaves makes a big difference. If,
instead, we assume that men do occasionally leave, but that there's a
queue from which any vacancies are immediately filled, then the number
of occupied urinals will almost surely converge to n/2 for even n or
(n+1)/2 for odd n.

(To see why, consider the gaps formed by two adjacent empty urinals,
or an empty urinal at either end of the row, and observe that, under
the immediate replacement rule, each such gap will move in a random
walk along the row until it collides with another gap and vanishes,
and that under immediate replacement no new gaps can be formed. For
odd n, this process will a.s. lead to all the gaps disappearing; for
even n, one residual gap will always remain, unable to meet another.)

> The answer clearly lies between 1/3 and 1/2 (the
> densities of the least and most efficient packings), so you might
> think "Cinch! 1/e", but no, the density is greater than 40%.

Now I'm trying to figure out where exactly Henry's 1/2 - exp(-2)/2
comes from.

--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
From: Ilan Mayer on 18 Jan 2010 18:36
On Jan 18, 4:43 am, Henry <s...(a)btinternet.com> wrote:
> On 18 Jan, 06:41, Jim Ferry <corkleb...(a)hotmail.com> wrote:
>
> > Suppose a bathroom has n urinals in a row which are initially
> > unoccupied.  Men approach one by one, balking at any urinal adjacent
> > to one in use.  Assuming they select urinals uniformly at random from
> > the set of those neither in use nor adjacent to one in use (and, for
> > simplicity, that they never leave -- think Austin Powers), what is the
> > expected fraction of urinals in use when the row fills up, in the
> > limit n -> infinity?  The answer clearly lies between 1/3 and 1/2 (the
> > densities of the least and most efficient packings), so you might
> > think "Cinch!  1/e", but no, the density is greater than 40%.
>
> > BTW, some of you may have seen the very row of urinals which inspired
> > this problem:  it was in the bathroom near the Employment Center at
> > last week's Joint Math Meetings in San Francisco.
>
> The expected density tends towards 1/2 - exp(-2)/2 = 0.432... from
> above as n increases

There is an analysis of an equivalent problem at
http://algo.inria.fr/libraries/autocomb/fatmen-html/fatmen1.html



Please reply to ilan dot mayer at hotmail dot com

__/\__
\ /
__/\\ //\__ Ilan Mayer
\ /
/__ __\ Toronto, Canada
/__ __\
||
From: ksoileau on 18 Jan 2010 19:08
On Jan 18, 5:36 pm, Ilan Mayer <ilan_no_s...(a)hotmail.com> wrote:
> On Jan 18, 4:43 am, Henry <s...(a)btinternet.com> wrote:
>
>
>
>
>
> > On 18 Jan, 06:41, Jim Ferry <corkleb...(a)hotmail.com> wrote:
>
> > > Suppose a bathroom has n urinals in a row which are initially
> > > unoccupied.  Men approach one by one, balking at any urinal adjacent
> > > to one in use.  Assuming they select urinals uniformly at random from
> > > the set of those neither in use nor adjacent to one in use (and, for
> > > simplicity, that they never leave -- think Austin Powers), what is the
> > > expected fraction of urinals in use when the row fills up, in the
> > > limit n -> infinity?  The answer clearly lies between 1/3 and 1/2 (the
> > > densities of the least and most efficient packings), so you might
> > > think "Cinch!  1/e", but no, the density is greater than 40%.
>
> > > BTW, some of you may have seen the very row of urinals which inspired
> > > this problem:  it was in the bathroom near the Employment Center at
> > > last week's Joint Math Meetings in San Francisco.
>
> > The expected density tends towards 1/2 - exp(-2)/2 = 0.432... from
> > above as n increases
>
> There is an analysis of an equivalent problem athttp://algo.inria.fr/libraries/autocomb/fatmen-html/fatmen1.html
>
> Please reply to ilan dot mayer at hotmail dot com
>
>    __/\__
>    \    /
> __/\\  //\__  Ilan Mayer
> \          /
> /__      __\  Toronto, Canada
>   /__  __\
>      ||

I think this problem for n urinals in a row is equivalent to the
problem of n+1 urinals arranged in a circle which starts with one
occupied urinal.
 |  Next  |  Last
Pages: 1 2 3 4
Prev: Gravity and black holes
Next: Is This really a Proof that Standard Math is Inconsistent?