Maths Olympiad Prep

Library / /48 of 105

Combinatorics Difficulty 5.7 AIME, harder Prove it JBMO

Problem:
All possible pairs of nn apples are weighed and the results are given to us in an arbitrary order. Can we determine the weights of the apples if

a. n=4n=4

b. n=5n=5

c. n=6n=6?

Solution

Solution:

a. No. Four apples with weights 1,5,7,91, 5, 7, 9 and with weights 2,4,6,102, 4, 6, 10 both give the results 6,8,10,12,14,166, 8, 10, 12, 14, 16 when weighed in pairs.

b. Yes. Let abcdea \leq b \leq c \leq d \leq e be the weights of the apples. As each apple is weighed 4 times, by adding all 10 pairwise weights and dividing the sum by 4, we obtain a+b+c+d+ea + b + c + d + e. Subtracting the smallest and the largest pairwise weights a+ba + b and d+ed + e from this we obtain cc. Subtracting cc from the second largest pairwise weight c+ec + e we obtain ee. Subtracting ee from the largest pairwise weight d+ed + e we obtain dd. aa and bb are similarly determined.

c. Yes. Let abcdefa \leq b \leq c \leq d \leq e \leq f be the weights of the apples. As each apple is weighed 5 times, by adding all 15 pairwise weights and dividing the sum by 5, we obtain a+b+c+d+e+fa + b + c + d + e + f. Subtracting the smallest and the largest pairwise weights a+ba + b and e+fe + f from this we obtain c+dc + d.
Subtracting the smallest and the second largest pairwise weights a+ba + b and d+fd + f from a+b+c+d+e+fa + b + c + d + e + f we obtain c+ec + e. Similarly we obtain b+db + d. We use these to obtain a+fa + f and b+eb + e.
Now a+d,a+e,b+ca + d, a + e, b + c are the three smallest among the remaining six pairwise weights. If we add these up, subtract the known weights c+dc + d and b+eb + e from the sum and divide the difference by 2, we obtain aa. Then the rest follows.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.