6
$\begingroup$

In a soccer stadium restroom there are 100 stalls (cubicles), arranged in a straight line. Stalls are numbered 1, 2, 3,..., 100, with 1 being closest to the main exit of the restroom. Unfortunately, 100 people from audience rush towards the restroom during half-time. One by one, each person selects a stall as follows.

The first person picks from the 100 spots uniformly randomly. Then:

  • Each following person picks the choice which maximizes the minimal distance from an already occupied stall.
  • If two or more stalls have same such minimal distance, then their second minimal distances are compared, and the stall which maximizes the second minimal distance is chosen.
  • If again there is a tie, their third minimal distances are compared, and so on.
  • If there is a tie in set of all possible distances, then the stall farther from the main exit (i.e. with greater stall number) is chosen.

Which stall has the highest probability to be picked by the last person?

Tiny Spoiler:

The last person will never end up in the 100th stall.

$\endgroup$
1

3 Answers 3

9
$\begingroup$

Computer-based solution: cubicle number 35, code at the bottom.

First, note that due to the tie-breaker rules, the cubicle selected by each person is uniquely determined by the choice of cubicle of the 1st person. So the question is now equivalent to:

Aggregating over all the possible 100 choices of the first person, which cubicle is selected the most by the 100th person?

I wrote a brute-force search (O(n^3) complexity) code in Python, and the list of counts are (1-indexed, sorted by cubicle number, zeroes not shown):

 30:   2
 31:   2
 32:   2
 33:   2
 34:   2
 35:   6
 36:   2
 38:   2
 39:   1
 40:   4
 41:   4
 42:   4
 43:   2
 44:   1
 45:   2
 46:   4
 47:   2
 48:   4
 49:   2
 50:   2
 51:   3
 52:   5
 53:   4
 54:   3
 55:   4
 56:   3
 59:   2
 60:   4
 61:   4
 62:   2
 63:   1
 65:   1
 66:   4
 67:   1
 68:   2
 69:   2
 70:   1
 71:   1
 72:   1
Highest prob: 35

So the cubicle with the highest probability to be selected by the 100th person is cubicle number 35, selected 6 times out of 100, while the rest are selected at most 5 times by the 100th person.

# -*- coding: utf-8 -*-
"""
From: https://puzzling.stackexchange.com/questions/120379/the-halftime-hustle
"""
from __future__ import print_function, division

# Import statements
import sys
from argparse import ArgumentParser
from collections import Counter

def print_conf(cubicles):
    print(' '.join(str(c) for c in cubicles))

def get_last(n, start, debug=False):
    cubicles = [0]*n
    cubicles[start] = 1
    def dist_arr(idx):
        vals = []
        for i in range(max(idx+1, n-idx)):
            if idx-i>=0 and cubicles[idx-i]:
                vals.append(i)
            if idx+i<n and cubicles[idx+i]:
                vals.append(i)
        return vals
    if debug:
        print(f'Start: {start}')
        print_conf(cubicles)
    for person in range(1, n):
        selected = max((dist_arr(idx), idx) for idx in range(n) if not cubicles[idx])[1]
        cubicles[selected] = 1
        if debug:
            print_conf(cubicles)
    return selected

def main(args=None):
    parser = ArgumentParser(description='')
    parser.add_argument('n', type=int,
                        help='The number of people')
    parser.add_argument('--debug', action='store_true',
                        help='To enable debug mode')
    args = parser.parse_args(args)
    n = args.n
    debug = args.debug

    counts = Counter()
    for first in range(n):
        last = get_last(n, first, debug)
        counts[last] += 1
    for idx, count in sorted(counts.items()):
        print(f'{idx+1:3d}: {count:3d}')
    highest_count = max(counts.items(), key=lambda x: x[1])[0]
    print(f'Highest prob: {highest_count+1}')

if __name__ == '__main__':
    main()

Example cubicle selection for N=10 people, when the first person selected cubicle #9:

0 0 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 1 0
1 0 0 0 1 0 0 0 1 0
1 0 0 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 0
1 0 1 0 1 0 1 0 1 1
1 1 1 0 1 0 1 0 1 1
1 1 1 0 1 1 1 0 1 1
1 1 1 0 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

And here are the results for lower values of N:

N=6, best last: 3
N=7, best last: 3
N=8, best last: 4
N=9, best last: 4
N=10, best last: 5
N=11, best last: 5
N=12, best last: 6
N=13, best last: 6
N=14, best last: 7
N=15, best last: 7
N=16, best last: 8
N=17, best last: 8
N=18, best last: 9
N=19, best last: 9
N=20, best last: 10
N=21, best last: 9
N=22, best last: 12
N=23, best last: 11
N=24, best last: 12
N=25, best last: 12
N=30, best last: 15
N=40, best last: 20
N=50, best last: 22
N=60, best last: 27
N=70, best last: 42
N=80, best last: 40
N=90, best last: 40

I don't see any pattern yet so far, and I can't see an elegant way to get to the result for 100 by hand, given the complex rules for tie-breaker.

$\endgroup$
3
  • 3
    $\begingroup$ My program found the same answer. $\endgroup$ Commented Apr 5, 2023 at 18:04
  • 1
    $\begingroup$ @justhalf Congratulations! 35 is the right answer :) I appreciate you recognized this was solvable through code, and were the first one to solve it. If you observe carefully, the tie-breaking rules are essentially creating nearly-equal sized partitions, which I was trying to exploit further. But yes, the question is too noisy for a clean solution. $\endgroup$
    – thisIs4d
    Commented Apr 5, 2023 at 19:31
  • $\begingroup$ Yeah, I recon this might not have a clean solution, unlike this other similar question, where you can have a closed form solution (which was my answer; I've answered questions similar to this, so I was intrigued to answer this too) $\endgroup$
    – justhalf
    Commented Apr 6, 2023 at 2:19
3
$\begingroup$

Adding onto @justhalf's answer, I too have computed

stall number 35

Please feel free to go over my code in this gist.

By utilising a weighting scheme, I may have improved it to $O(n^2)$. The idea being: at each turn, we look for the stall with the minimum weight, choose it, and update/increment the weights of all the stalls.

The procedure

Suppose there are $N$ stalls. We maintain an array w of size $N$ for the weights of each stall and initialise it to zero. Say we index by 1. When we choose stall $m$, we add onto w elementwise: $$ \left[4^{N - m},\ldots, 4^{N-2}, 4^{N-1}, 4^{N-2}, \ldots, 4^{m - 1}\right] $$ By finding the stall with minimum weight, we can choose a stall and update the weights again.

The idea behind it

Consider when $N=5$. Suppose we have a strategy of adding weights to stalls incrementally like described above. Naturally, we might explore adding: $N$ minus the distance from the chosen stall. Our scheme becomes:

choose        add to w
  1       [ 5, 4, 3, 2, 1 ]
  2       [ 4, 5, 4, 3, 2 ]
  3       [ 3, 4, 5, 4, 3 ]
  4       [ 2, 3, 4, 5, 4 ]
  5       [ 1, 2, 3, 4, 5 ]

Each column shows the possible weights that can be added to each stall. While not true in this example, if stalls $p$ and $q$ have weights: 2+5+3=10 and 5+4+1=10, we run into a problem. As $4>3$, we must choose stall $q$. Adding them as is is not sufficient to disambiguate the weights.

To capture the ordering of these addends, we may assign them to bits in, say, binary. Now, we can simply compare the numbers: $10110_2$ and $11001_2$ to choose a stall. However, notice that each number appears in the column at most twice. If instead we had 4 + 4, this would result in a bit being carried over. To resolve this, we can opt for a larger base (e.g. three) which guarantees this doesn't happen. We use base four here as bit-shifting operations are relatively fast.

Python allows for arbitrarily large integers, so this wasn't so bad. However, this is pretty much like maintaining a sorted list of distances from each stall and using it to decide beween stalls.

Some graphs

Probability distribution of last stall for N=100 Heatmap of stalls chosen for N=100 Trend of last stall taken as stalls are increased

$\endgroup$
2
  • 1
    $\begingroup$ Great work! I wonder if you can get the bounds on the graphs you have got...i.e. a linear (or not) upper or lower bound $\endgroup$
    – thisIs4d
    Commented Apr 6, 2023 at 19:24
  • 1
    $\begingroup$ Appropriate color scheme for a table titled "Where to pee" XD $\endgroup$
    – justhalf
    Commented Apr 7, 2023 at 13:51
1
$\begingroup$

The second person will always pick 100 or 1, depending on what gets picked first

The next person will either chose the remaining 100 or 1, or the middle point between the first choice or the second choice. (depending on which has the biggest gap)

if either 1 or 100 are still not picked, repeat step 2 with the remaining choice, as well as the gap between the two biggest other seats

We will reach a point where 1, and 100, and a few fairly spaced others stalls have been picked.

We keep filling the stall by picking the middle stall of the biggest gap. If two gap are tied for the biggest gap, we chose the gap formed by the biggest number. If the gap is odd, we round up the middle stall.

Some visualisation using 10 stalls. O are open and X are taken.

O O X O O O O O O O
O O X O O O O O O X
O O X O O O X O O X
O O X O X O X O O X
X O X O X O X O O X <= the last gap is bigger but
X O X O X O X O X X...... still only has opening right next
X O X O X O X X X X...... to other stalls, making it
X O X O X X X X X X...... basically the same
X O X X X X X X X X
X X X X X X X X X X

Using the pattern in 5. We can see that 2 will always be picked last unless it is picked first, therefore the answer is the 2nd stall

$\endgroup$
2
  • 1
    $\begingroup$ Good observation. But consider this case: O O X O O O -> O O X O O X -> X O X O O X -> X O X O X X -> X X X O X X -> X X X X X X $\endgroup$
    – thisIs4d
    Commented Apr 5, 2023 at 11:22
  • 1
    $\begingroup$ somehow I missed the rule "If two or more stalls have same such minimal distance, then their second minimal distances are compared, and the stall which maximizes the second minimal distance is chosen.". Sorry $\endgroup$ Commented Apr 5, 2023 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.