Brooklyn 99 Captain Holt's Islander Puzzle

by Orhan G. Hafif

The Riddle

In the 18th episode of the season 2, Capt. Holt presents this riddle:

There's an island with 12 men, one of them is slightly lighter or heavier. You have to determine who has the different weight, using a seesaw. The exciting catch? You can only use it to measure three times.

Anonymous


Here's a 12 balls version and multiple answers I've found: Twelve balls and a scale question on puzzling.stackexchange.com.
There are top 2 answers, the most upvoted one is creatively brute-forcing it. Numbering the balls and weighing them via following order: 
Weighing 1:  1 4 8 12 / 5 7 10 11
Weighing 2:  2 6 9 11 / 4 7 10 12
Weighing 3:  5 8 9 10 / 3 6 11 12
And then, there are 24 different outcomes, which forces you to map all possible solutions if you wanted to prove it with a computer code:
==L : 3L    L== :  1H    R== :  1L
==R : 3H    L=L :  8H    R=L :  5H
=L= : 2H    L=R :  5L    R=R :  8L
=LL : 9H    LL= :  7L    RL= :  4L
=LR : 6H    LLR : 10L    RLL : 12L
=R= : 2L    LR= :  4H    RLR : 11H
=RL : 6L    LRL : 11L    RR= :  7H
=RR : 9L    LRR : 12H    RRL : 10H
   
 = : scale balanced
 L : scale tipped to the left
 R : scale tipped to the right
nL : ball n is light
nH : ball n is heavy

The other top answer, which was accepted as the solution, although upvoted less, is more efficient. But I assume, to simplify, it doesn't tell you randomly selected balls and it doesn't explain why it does the certain selections in the round  \(2\) . It also follows a bulleted list to show the solution.

My Solution

I will do it as expanding  \(\color{#6ab825}{3}\)  outcomes to  \(\color{#6ab825}{9}\)  outcomes for representing it more algorithmically.

Better Naming

We are dividing the balls to  \(\color{#6ab825}{3}\)  groups, so instead of numbering them  \(\color{#6ab825}{1}\)  to  \(\color{#6ab825}{12}\) , we will name them like the solution mentioned above:
\( - \color{#67D4FF}{A_{1}}, \color{#67D4FF}{A_{2}}, \color{#67D4FF}{A_{3}}, \color{#67D4FF}{A_{4}}, \)
\( - \color{#FF8B8B}{B_{1}}, \color{#FF8B8B}{B_{2}}, \color{#FF8B8B}{B_{3}}, \color{#FF8B8B}{B_{4}}, \)
\( - C_{1}, C_{2}, C_{3}, C_{4} \)

The First Measurement

We will weigh the group \(\color{#67D4FF}{A}\) and \(\color{#FF8B8B}{B}\) first. We've selected them randomly since we've also named them randomly 🙃 \(\color{#67D4FF}{A}\) could be the \(\color{#FF8B8B}{B}\) and \(\color{#FF8B8B}{B}\) could be the \(C\) and the \(C\) could be the \(\color{#67D4FF}{A}\). It doesn't matter.

\( \underbrace{ \color{#67D4FF}{A_{1}} + \color{#67D4FF}{A_{2}} + \color{#67D4FF}{A_{3}} + \color{#67D4FF}{A_{4}} \rm\ ==\rm\ \color{#FF8B8B}{B_{1}} + \color{#FF8B8B}{B_{2}} + \color{#FF8B8B}{B_{3}} + \color{#FF8B8B}{B_{4}} }_{comparing\rm\ group\rm\ \color{#67D4FF}{A}\rm\ and\rm\ \color{#FF8B8B}{B}\rm\ on\rm\ the\rm\ scale } \)

We can determine that  \(\color{#6ab825}{2}\)  groups or at least  \(\color{#6ab825}{1}\)  group has all equal weighted normal members via this first measurement. Remember,  \(\color{#6ab825}{11}\)  balls are normal, have equal weights, and  \(\color{#6ab825}{1}\)  ball is either heavier or lighter than them. Or the two of the groups have all normal members, only one group has an odd member.

This measurement has  \(\color{#6ab825}{3}\)  possible outcomes. \( = \cases{ left\rm\ is\rm\ heavier & $\color{#67D4FF}{A}$ $\gt$ $\color{#FF8B8B}{B}$ \cr right\rm\ is\rm\ heavier & $\color{#67D4FF}{A}$ $\lt$ $\color{#FF8B8B}{B}$ \cr balanced & $\color{#67D4FF}{A}$ = $\color{#FF8B8B}{B}$ } \)

According to these outcomes, in the second round, we will weigh different groups against each other.

The second measurement

\( = \cases{ \color{#67D4FF}{A} \gt \color{#FF8B8B}{B} & $\color{#67D4FF}{A_{1}}$ + $\color{#FF8B8B}{B_{1}}$ + $\color{#FF8B8B}{B_{2}}$ == $\color{#FF8B8B}{B_{3}}$ + $\color{#FF8B8B}{B_{4}}$ + $C_{1}$ \cr \color{#67D4FF}{A} \lt \color{#FF8B8B}{B} & $\color{#FF8B8B}{B_{1}}$ + $\color{#67D4FF}{A_{1}}$ + $\color{#67D4FF}{A_{2}}$ == $\color{#67D4FF}{A_{3}}$ + $\color{#67D4FF}{A_{4}}$ + $C_{1}$ \cr \color{#67D4FF}{A} = \color{#FF8B8B}{B} & $\color{#67D4FF}{A_{1}}$ + $\color{#67D4FF}{A_{2}}$ + $\color{#67D4FF}{A_{3}}$ == $C_{1}$ + $C_{2}$ + $C_{3}$ } \)

Why?

Let's start with the easy one, the balanced, \(\color{#67D4FF}{A} = \color{#FF8B8B}{B}\). It means all members of the group \(\color{#67D4FF}{A}\) and \(\color{#FF8B8B}{B}\) are normal balls with equal weights. We selected the first  \(\color{#6ab825}{3}\)  balls from the group \(C\) and group \(\color{#67D4FF}{A}\). It is just for the simplicity's sake. On the left side we could select any  \(\color{#6ab825}{3}\)  the balls from a pool of group \(\color{#67D4FF}{A}\) and \(\color{#FF8B8B}{B}\). On the right side, we could select any  \(\color{#6ab825}{3}\)  balls from the group \(C\).

If you look closely, we distributed the lighter group to the separate sides for both \(\color{#67D4FF}{A} \gt \color{#FF8B8B}{B}\) and \(\color{#67D4FF}{A} \lt \color{#FF8B8B}{B}\). We could have used the heavier side too, but if we use the heavier group for one outcome, we would need to use the heavier one for the other outcome too, if we just want to switch \(\color{#67D4FF}{A}\)s and \(\color{#FF8B8B}{B}\)s for writing down the operations for the seventh, eighth and ninth possibility of the second measurement result.

Our aim here is, leaving out maximum of  \(\color{#6ab825}{3}\)  balls to the last measurement and determining if the different one is either heavier or lighter; with one exception which is the fifth possibility described in the third measurement below. When I was trying to solve this puzzle by myself, I unnecessarily eliminated this very solution because of this exception and after a while, looked up for the solution on the internet instead of killing more time 🙃

We know that \(\color{#67D4FF}{A} \gt \color{#FF8B8B}{B}\) and \(\color{#67D4FF}{A} \lt \color{#FF8B8B}{B}\) are the same thing if we just switch the group names. So let's pick \(\color{#67D4FF}{A} \gt \color{#FF8B8B}{B}\):

\( \underbrace{ \color{#67D4FF}{A_{1}} + \color{#FF8B8B}{B_{1}} + \color{#FF8B8B}{B_{2}} == \color{#FF8B8B}{B_{3}} + \color{#FF8B8B}{B_{4}} + C_{1}}_{second\rm\ measurement\rm\ after\rm\ the\rm\ first\rm\ is\rm\ resulted\rm\ with\rm\ \color{#67D4FF}{A}\rm\ \gt\rm\ \color{#FF8B8B}{B}\rm\ } \)

The group \(\color{#67D4FF}{A}\) is heavier than the group \(\color{#FF8B8B}{B}\), so:
  • If the scale balances, we can easily say that one of the three remaining \(\color{#67D4FF}{A}\) balls is heavier, it was responsible for the first measurement.
  • If the left side is heavier, there are 2 possibilities. First, the \(\color{#67D4FF}{A_{1}}\) is heavier, second, \(\color{#FF8B8B}{B_{3}}\) or \(\color{#FF8B8B}{B_{4}}\) is lighter. This is the exception where we don't know if the different one is lighter or heavier before the third measurement.
  • If the right side is heavier, we can see that the group \(\color{#67D4FF}{A}\) was heavier than the group \(\color{#FF8B8B}{B}\) because of one of these balls, \(\color{#FF8B8B}{B_{1}}\) or \(\color{#FF8B8B}{B_{2}}\) being lighter.

The Third Measurement

Here, we can map all the  \(\color{#6ab825}{9}\) possible scale placements of the balls according the the previous round's results. We can even leave out the  \(\color{#6ab825}{7}\) ,  \(\color{#6ab825}{8}\)  and  \(\color{#6ab825}{9}\)  since they can be written as \(\color{#67D4FF}{A}\)s and \(\color{#FF8B8B}{B}\)s switched for  \(\color{#6ab825}{4}\) ,  \(\color{#6ab825}{5}\)  and  \(\color{#6ab825}{6}\)  since the names of these groups can be switched in the beginning, the calculations would be same. Here are the all nine possibilities after the second measurement:
  1. \((\color{#67D4FF}{A} = \color{#FF8B8B}{B})\rm\ \&\rm\ (\color{#67D4FF}{A_{1}} + \color{#67D4FF}{A_{2}} + \color{#67D4FF}{A_{3}} = C_{1} + C_{2} + C_{3}) \)
    Both the first and the second weights are balanced. Which means, the left out one, \(C_{4}\) is the different one. We can weigh it agains anyone and tell if it is heavier or lighter.
  2. \((\color{#67D4FF}{A} = \color{#FF8B8B}{B})\rm\ \&\rm\ (\color{#67D4FF}{A_{1}} + \color{#67D4FF}{A_{2}} + \color{#67D4FF}{A_{3}} \gt C_{1} + C_{2} + C_{3}) \)
    We can see that the different and lighter one is on the right side of the second measurement scale, one of \(C_{1}\), \(C_{2}\) or \(C_{3}\). We can randomly select two of them, if the scale balances, the remaining one is the lighter one, if it doesn't, lighter side of the scale is already showing us the lighter one.
  3. \((\color{#67D4FF}{A} = \color{#FF8B8B}{B})\rm\ \&\rm\ (\color{#67D4FF}{A_{1}} + \color{#67D4FF}{A_{2}} + \color{#67D4FF}{A_{3}} \lt C_{1} + C_{2} + C_{3}) \)
    The different and heavier one is one of \(C_{1}\), \(C_{2}\) or \(C_{3}\). We can solve it just like the second possibility above.
  4. \((\color{#67D4FF}{A} \gt \color{#FF8B8B}{B})\rm\ \&\rm\ (\color{#67D4FF}{A_{1}} + \color{#FF8B8B}{B_{1}} + \color{#FF8B8B}{B_{2}} = \color{#FF8B8B}{B_{3}} + \color{#FF8B8B}{B_{4}} + C_{1}) \)
    All these six balls on the scale are equal to each other, also all \(C\) balls are equal since the rivalry was between \(\color{#67D4FF}{A}\) and \(\color{#FF8B8B}{B}\). Then one of the remaining three \(\color{#67D4FF}{A}\) balls is heavier. We can choose random two as the last measurement and move on.
  5. \((\color{#67D4FF}{A} \gt \color{#FF8B8B}{B})\rm\ \&\rm\ (\color{#67D4FF}{A_{1}} + \color{#FF8B8B}{B_{1}} + \color{#FF8B8B}{B_{2}} \gt \color{#FF8B8B}{B_{3}} + \color{#FF8B8B}{B_{4}} + C_{1}) \)
    In this exceptional case, we can still determine the different one by the third measurement even without knowing its weight comparison from the second measurement. Both on the first and the second measurements, the left side is heavier, the right side is lighter. We kept \(\color{#67D4FF}{A_{1}}\) on the left side for both, and we kept \(\color{#FF8B8B}{B_{3}}\) and \(\color{#FF8B8B}{B_{4}}\) on the right side. Moving \(\color{#FF8B8B}{B_{1}}\) and \(\color{#FF8B8B}{B_{2}}\) to the left, didn't change the result of left side being heavier so they are not the ones we are looking for. After weighing \(\color{#FF8B8B}{B_{3}}\) and \(\color{#FF8B8B}{B_{4}}\) as third measurement, if \(\color{#FF8B8B}{B_{3}} = \color{#FF8B8B}{B_{4}}\), then the \(\color{#67D4FF}{A_{1}}\) is heavier. If not, we have found the lighter one.
  6. \((\color{#67D4FF}{A} \gt \color{#FF8B8B}{B})\rm\ \&\rm\ (\color{#67D4FF}{A_{1}} + \color{#FF8B8B}{B_{1}} + \color{#FF8B8B}{B_{2}} \lt \color{#FF8B8B}{B_{3}} + \color{#FF8B8B}{B_{4}} + C_{1}) \)
    An interesting result. The group \(\color{#67D4FF}{A}\) was heavier than the group \(\color{#FF8B8B}{B}\) because of \(\color{#FF8B8B}{B_{1}}\) and \(\color{#FF8B8B}{B_{2}}\). One of these balls must be lighter, so we can put them on the scale for determining which.
  7. \((\color{#FF8B8B}{B} \gt \color{#67D4FF}{A})\rm\ \&\rm\ (\color{#FF8B8B}{B_{1}} + \color{#67D4FF}{A_{1}} + \color{#67D4FF}{A_{2}} = \color{#67D4FF}{A_{3}} + \color{#67D4FF}{A_{4}} + C_{1}) \)
    Same as fourth
  8. \((\color{#FF8B8B}{B} \gt \color{#67D4FF}{A})\rm\ \&\rm\ (\color{#FF8B8B}{B_{1}} + \color{#67D4FF}{A_{1}} + \color{#67D4FF}{A_{2}} \gt \color{#67D4FF}{A_{3}} + \color{#67D4FF}{A_{4}} + C_{1}) \)
    Same as fifth
  9. \((\color{#FF8B8B}{B} \gt \color{#67D4FF}{A})\rm\ \&\rm\ (\color{#FF8B8B}{B_{1}} + \color{#67D4FF}{A_{1}} + \color{#67D4FF}{A_{2}} \lt \color{#67D4FF}{A_{3}} + \color{#67D4FF}{A_{4}} + C_{1}) \)
    Same as sixth.

    10. Did you notice that for the  \(\color{#6ab825}{7}\)th ,  \(\color{#6ab825}{8}\)th  and  \(\color{#6ab825}{9}\)th  possibilities, we've put the group \(\color{#FF8B8B}{B}\) on the left side to get the same explanations 🙃

Why not prove it with a Python code?

When explaining to a friend, I realized that it is easier to prove it with a software than to try to explain the missing random selection parts of the answer in the puzzling stackexchange link above.

Here's a simple Python script that gives initial weights of 1.0 to everyone, randomly selects one of them or iterates all for testing, then increases or decreases it by 0.5. Then the solution above, finds the different one by only  \(\color{#6ab825}{3}\)  comparisons of lsum and rsum which are referred to the total weights of the left and the right sides of the scale. 

  1    
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
from random import randrange, choice, sample

balls = {'A':[1.0, 1.0, 1.0, 1.0], 'B':[1.0, 1.0, 1.0, 1.0], 'C':[1.0, 1.0, 1.0, 1.0]}
    
def getRandValExceptC3():
    g = choice(['A', 'B', 'C'])
    if (g == 'A') or (g == 'B'):
        m = randrange(4)
    else:
        m = randrange(3)
    return balls[g][m]

def getTotalOfRandom3FromAandB():
    arr = [balls['A'][0], balls['A'][1], balls['A'][2], balls['A'][3],
           balls['B'][0], balls['B'][1], balls['B'][2], balls['B'][3]]
    return sum(sample(arr, 3))
    
def getHeavyStry(heavier):
    return 'heavier' if heavier else 'lighter'

def printWhich(g0, g1, g2, m0, m1, m2, heavier):
    s = ''
    if balls[g0][m0] == balls[g1][m1]:
        s = s + g2 + str(m2+1) + ' is ' + getHeavyStry(heavier)
    else:
        if heavier:
            if balls[g0][m0] > balls[g1][m1]:
                s = s + g0 + str(m0+1) + ' is ' + getHeavyStry(heavier)
            else:
                s = s + g1 + str(m1+1) + ' is ' + getHeavyStry(heavier)
        else:
            if balls[g0][m0] < balls[g1][m1]:
                s = s + g0 + str(m0+1) + ' is ' + getHeavyStry(heavier)
            else:
                s = s + g1 + str(m1+1) + ' is ' + getHeavyStry(heavier)
    print(s)

# group = choice(['A', 'B', 'C'])
# member = randrange(4)
# balls[group][member] += [-0.5, 0.5][randrange(2)] # randomly increase or decrease a random member's weight
print(balls)
print("Everyone is equal")

for g in ['A', 'B', 'C']:
    for m in range(4):
        for i in range(2):
            change = -0.5 if i == 0 else 0.5
            balls[g][m] += change
            print(balls)
            
            lsum = sum(balls['A'])
            rsum = sum(balls['B'])
            # A > B
            if lsum > rsum:
                lsum = balls['A'][0] + balls['B'][0] + balls['B'][1]
                rsum = balls['B'][2] + balls['B'][3] + balls['C'][randrange(4)]
                if lsum > rsum:
                    if balls['B'][2] == balls['B'][3]:
                        print('A1 is heavier')
                    elif balls['B'][2] < balls['B'][3]:
                        print('B3 is lighter')
                    else:
                        print('B4 is lighter')
                elif lsum < rsum:
                    if balls['B'][0] < balls['B'][1]:
                        print('B1 is lighter')
                    else:
                        print('B2 is lighter')
                else:
                    printWhich('A', 'A', 'A', 1, 2, 3, heavier=True)
            # A < B
            elif lsum < rsum:
                lsum = balls['B'][0] + balls['A'][0] + balls['A'][1]
                rsum = balls['A'][2] + balls['A'][3] + balls['C'][randrange(4)]
                if lsum > rsum:
                    if balls['A'][2] == balls['A'][3]:
                        print('B1 is heavier')
                    elif balls['A'][2] < balls['A'][3]:
                        print('A3 is lighter')
                    else:
                        print('A4 is lighter')
                elif lsum < rsum:
                    if balls['A'][0] < balls['A'][1]:
                        print('A1 is lighter')
                    else:
                        print('A2 is lighter')
                else:
                    printWhich('B', 'B', 'B', 1, 2, 3, heavier=True)
            # A = B
            else:
                lsum = getTotalOfRandom3FromAandB()
                rsum = balls['C'][0] + balls['C'][1] + balls['C'][2]
                if lsum > rsum:
                    printWhich('C', 'C', 'C', 0, 1, 2, heavier=False)
                elif lsum < rsum:
                    printWhich('C', 'C', 'C', 0, 1, 2, heavier=True)
                else:
                    if balls['C'][3] < getRandValExceptC3(): # except C4
                        print ('C4 is lighter')
                    else:
                        print ('C4 is heavier')
            balls[g][m] -= change # revert

The code tests all  \(\color{#6ab825}{24}\)  different cases one by one 🙃
Location: İstanbul, Türkiye

Comments

Post a Comment