gilbu.dev //

Groupings and interviews

Simon Gilbu

first published: October 2024

last edited: October 2024

The mathematics behind a well-known interview question

# The interview

there is a interview question for which i might be completely wrong. but i do believe i remeber it as follows:

Suppose that you have 9 balls in front of you, each are similar in shape and color, but one is slightly heavier. you have access to a balance scale and can compare the balls to each-other, but you are only allowd to make two measurements, how do you find the heavier ball?

the question is admidedtly frustrating to begin with. beacuse how would you even aproach this? well i hate to spoil the fun, but the question itself is not the interesting part. instead the interesting part is what follows.

## The answer

you have exactly 9 balls, and although we think of a balance-scale as binary, it does actually give us three results. so here is a decent aproach in my opinion. split the balls into three groups, A, B and C, each group has exactly three balls in them. now compare group A and B, if A is heavier. then that is where the heaviest ball is. if B is heavier, that is where the ball is. If they are of equal weight. then the heaviest ball is in group C.

Do this again for each ball in the selected group and we have our winner, its either the heaviest one we measure, or the one we didnt measure if the two measured balls are equal.

## The fun part

What if you had 10 balls?, okay, split it into groups of 3, but let one group have 4 balls in it. if a group with three balls has the heaviset one among them we're back to doing a second measurement. but if it is in the group with 4 balls, we have to either measure twice, with two balls on each scale, and then comperatively between 1 and 1 ball. so 10 balls will in the worst case be three measurements... how many measurements are "required" to find the heaviest of... 100 balls? what about 1000! balls? or maybe $1000!^{1000!}$ balls?

## Premise

i am going to postulate a statement here that might be intuitiv, but might not be. if you had somewhere between $3^1$ and $3^2$ balls to calculate, you would need 2 attempts. more formally, and as a general expression:

let $m$ be the number of tries you need, and let $k$ be the number of balls you have. if $3^a < k \leq 3^{a+1}$, then $m = a+1$. there are a couple of ways to think about this. but also a few assumptions to be made. first of all k must be at least 2. there is no way of doing a comperative measure of less then 2 balls, secondly we need to prove a few base-cases for this, look at some instances of different configurations, and then finally use induction to prove this statement.

## Base cases

I thought perhaps we could start by looking at the two most obvious base-cases, $k = 2$ and $k = 3$, both of these are less then or equal to $3^{1}$, and therefore should be solvable in a single measurement.

| balls | comparisons |
| ----- | ----------- |
| 2     | 1           |
| 3     | 1           |

The reason should be self-evident, but still lets clarify. if you have two balls you just measure them and pick the heaviest one. if you have three balls you compare two of them, and either pick the heaviest, or the unmeasured ball if the measurement is equal.

but i thought it might also be worht looking at all values for $k$ in the range $3^1 < k \leq 3^2$, so we can see a small pattern emerging. if we have 4 balls, we make either a grouping like (1,1,2), or a grouping like (2,2), that is either 3 groups of 1, 1 and 2 balls, or 2 groups of 2 balls. this takes us back to k=2 which is solvable in 1 step. for k = 5 we can make a grouping like (2,2,1), for k = 6 we can do (3,3) or (2,2,2), for k = 7 we can do (3,2,2), for k = 8 we can do (3,3,2) and for k = 9 we can do (3,3,3).

for each k we can in other words get to a new value, or the "step below" in a single measurement. and this would hold up no matter what k is. that is to say we can find have some function f such that if $3^a < k \leq 3^{a+1}$ then $3^{a-1} < f(k) \leq 3^{a}$

## Modulo and division

lets just get this one thing straight out of the way, any number $\frac{3^{a}}{3} = 3^{a-1}$, i'll leave the formal proof as a task to the reader. this means that simply dividing any k into three groups should allow us to proove by induction that our postulated statement is correct. however we do have some fun work ahead. see we need to show each possible way to split our balls into three seperate groups. since we are working with groups of three, we can look at the modulo operand %.

if $k \equiv 0 (\mod{3}) $ then we can simply create three even groups of $\frac{k}{3}$ members each. if $k \equiv 1 (\mod{3})$ then we would have to make the groups as follows: $(\frac{k-1}{3}, \frac{k-1}{3}, \frac{k-1}{3} +1, )$, we see that the largest group here is the $\frac{k-1}{3} +1$ group. we can show that this group can be solved in 1 less step then just $k$ if we can show that when $3^a < k \leq 3^{a+1}$ then $3^{a-1} < \frac{k-1}{3}+1 \leq 3^{a}$ we know already that in this specific $k$ must be less then $3^{a+1}$ by at least a value of 2. since these are conditions implied by $k \equiv 1 (\mod{3})$

$$k = 3^{a+1}-2$$
$$\frac{k-1}{3}+1 \leq 3^a$$
$$\frac{3^{a+1}-2-1}{3}+1 \leq 3^a$$
$$3(\frac{3^{a+1}-2-1}{3}+1) \leq 3(3^a)$$
$$3^{a+1}-2-1+3 \leq 3^{a+1}$$
$$3^{a+1} \leq 3^{a+1}$$
$$\frac{3^{a+1}}{3} \leq \frac{3^{a+1}}{3}$$
$$3^{a} \leq 3^{a}$$

we see that our inequality holds up and that in the worst case therefore, $\frac{3^{a+1}-2-1}{3}+1 = 3^a$. yet there is one more case to consider. which is for $k \equiv 2 (\mod{3})$, here we find a new grouping as well, which should look similar to our previous case.$(\frac{k-2}{3} +1, \frac{k-2}{3} +1, \frac{k-2}{3})$, we see that now our largest group is equivalent to $\frac{k-2}{3} +1$, and we also know that K could be as large as $3^{a+1}-1$, so lets quickly just go through the same inequality for our new values:

$$k = 3^{a+1}-1$$
$$\frac{k-2}{3}+1 \leq 3^a$$
$$\frac{3^{a+1}-1-2}{3}+1 \leq 3^a$$
$$\frac{3^{a+1}-2-1}{3}+1 \leq 3^a$$
$$3(\frac{3^{a+1}-2-1}{3}+1) \leq 3(3^a)$$
$$3^{a+1}-2-1+3 \leq 3^{a+1}$$
$$3^{a+1} \leq 3^{a+1}$$
$$\frac{3^{a+1}}{3} \leq \frac{3^{a+1}}{3}$$
$$3^{a} \leq 3^{a}$$

## conclusion

we now know that for each case, we can make one measurement and get from a number of balls $k \leq 3^{a+1}$ to $k \leq 3^{a}$, thereby we know that it is $a$, or the next power of three after K, that dermeines how many comparisions we need to make in order to find the heaviest ball.