A few days ago this question was asked on puzzling.SE:
There are 10 balls which come in two possible weights. Using a balance scale at most 3 times, determine whether all the balls are the same weight or not.
The solution is not terribly satisfying, because there's no obvious way to generalize it. Can it be generalized?
Given N balls, how many weighings are required to determine if all balls are the same weight? Equivalently, for a given number of weighings, what's the maximum number of balls we can weigh?
$N=30$ for 4 weighings:
Let's divide all 30 balls into several groups. Namely, let in groups there will be 2, 5, 6, 8 and 9 balls. If we use four equalities to prove that the weights of the groups are also related as $2:5:6:8:9$, then we will solve the problem.
The required equalities are:
2+6 = 8
2+9 = 5+6
5+9 = 6+8
2+5+8 = 6+9
Let $w_2$, $w_5$, $w_6$, $w_8$ and $w_9$ be weights of our groups. Then $w_2+w_6=w_8$, $w_2+w_9=w_5+w_6$, $w_5+w_9$=$w_6+w_8$ and $w_2+w_5+w_8=w_6+w_9$. So, we solve and conclude that $w_6=3w_2$, $w_8=4w_2$, $w_5=2.5w_2$ and $w_9=4.5w_2$. If both balls in 2-group are the same (with weight $m$) then $m=w_2/2 = w_5/5 = w_6/6 = w_8/8 = w_9/9$, so all balls are equal. If balls from 2-group are not the same, then $w_2=M+m$ and $w_5=2.5(M+m)$, i.e. $2m+3M < w_5 < 3m +2M$, that's impossible.
So, the proof is over.