There are $6$ pieces of cheese of different weights. For any two pieces we can identify the heavier piece. Given that it is possible to divide them into two groups of equal weights with three pieces in each. Give the explicit way to find these groups by performing two weightings on a regular balance.
Problem
Source: Tournament of Towns,Spring 2002, Senior O Level, P3
Tags: combinatorics proposed, combinatorics
the_boss
14.05.2014 14:16
do you mean that for any 2 pieces, we can identify the heavier one, only by hand, without weighing them?
joybangla
14.05.2014 14:38
Yes. That's correct.
chaotic_iak
15.05.2014 03:47
Call a decreasing sequence $a,b,c$ to majorize another decreasing $d,e,f$ if $a > d, b > e, c > f$. Clearly this means $a+b+c > d+e+f$, and so their sums are not equal. Suppose the pieces are 6,5,4,3,2,1 from the heaviest to the lightest. Take the group containing the 6. There are 10 possible cases: - 6,5,4 majorizes 3,2,1, so this is impossible. - 6,5,3 majorizes 4,2,1. - 6,5,2 majorizes 4,3,1. - 6,5,1 doesn't majorize 4,3,2. Indeed, by setting for example 6 = 100kg, 5 = 99kg, 4 = 98kg, 3 = 97kg, 2 = 85kg, 1 = 81kg, we obtain two groups that sum to 200kg each. - 6,4,3 majorizes 5,2,1. - 6,4,2 majorizes 5,3,1. - 6,4,1 doesn't majorize 5,3,2. Set 6 = 100kg, 5 = 99kg, 4 = 98kg, 3 = 97kg, 2 = 83kg, 1 = 81kg. - 6,3,2 doesn't majorize 5,4,1. Set 6 = 100kg, 5 = 99kg, 4 = 98kg, 3 = 96kg, 2 = 82kg, 1 = 81kg. - 6,3,1 doesn't majorize 5,4,2. Set 6 = 100kg, 5 = 98kg, 4 = 97kg, 3 = 96kg, 2 = 82kg, 1 = 81kg. - 6,2,1 doesn't majorize 5,4,3. Set 6 = 100kg, 5 = 96kg, 4 = 84kg, 3 = 83kg, 2 = 82kg, 1 = 81kg. So we need to find the correct grouping among these five: - 651 vs 432 - 641 vs 532 - 631 vs 542 - 621 vs 543 - 632 vs 541 Weigh 641 vs 532, and 631 vs 542. If either is the same, we're done. Otherwise, there are four cases: - 641 is heavier, 631 is heavier. Thus we need to move something heavy from the 631 side to the 542 side (and get replaced by something lighter). If we move the 6, we get 531 vs 642, which when swapped around gives 642 vs 531, something that majorizes over another. This no good. So we need to move the 3 to get the 2. In other words, if 641, 631 are heavier, we can deduce that the correct grouping is 621 vs 543. - 641 is lighter, 631 is lighter. This is similar as above: we must have 651 vs 432. - 641 is lighter, 631 is heavier. This is impossible, as moving the 4 from the lighter side with the 3 shouldn't make the lighter side suddenly heavier. - 641 is heavier, 631 is lighter. Clearly we cannot replace the 4 from 641 with the 5, as we will get another heavier left side. Similar with replacing the 3 from 631 with the 2. Thus there is only one possibility left: 632 vs 541 is the correct grouping.