Maths Olympiad Prep

Library / /9 of 520

Combinatorics Difficulty 6.1 National olympiad Find the answer

A balance has a left pan, a right pan, and a pointer that moves along a graduated ruler. Like many other grocer balances, this one works as follows: An object of weight L L is placed in the left pan and another of weight R R in the right pan, the pointer stops at the number R\minusL R \minus{} L on the graduated ruler. There are n,(n≥2) n, (n \geq 2) bags of coins, each containing n(n\minus1)2\plus1 \frac{n(n\minus{}1)}{2} \plus{} 1 coins. All coins look the same (shape, color, and so on). n\minus1 n\minus{}1 bags contain real coins, all with the same weight. The other bag (we don’t know which one it is) contains false coins. All false coins have the same weight, and this weight is different from the weight of the real coins. A legal weighing consists of placing a certain number of coins in one of the pans, putting a certain number of coins in the other pan, and reading the number given by the pointer in the graduated ruler. With just two legal weighings it is possible to identify the bag containing false coins. Find a way to do this and explain it.

A number or a short expression. Spacing and $ signs are ignored.

Solution

1. Initial Setup and Notation:
- Let the weight of a real coin be x x .
- Let the weight of a false coin be x+d x + d , where d≠0 d \neq 0 .
- There are n n bags, each containing n(n−1)2+1 \frac{n(n-1)}{2} + 1 coins.
- n−1 n-1 bags contain real coins, and 1 bag contains false coins.
- We need to identify the bag with false coins using two weighings.

2. **Weighing Strategy for n≥3 n \geq 3 :**
- Order the bags as B1,B2,…,Bn B_1, B_2, \ldots, B_n .
- Take 1+2+⋯+(n−1)=n(n−1)2 1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2} coins from bag B1 B_1 and place them on the left pan.
- Take 1,2,3,…,(n−1) 1, 2, 3, \ldots, (n-1) coins from bags B2,B3,…,Bn B_2, B_3, \ldots, B_n respectively and place them on the right pan.
- Let the reading be R1−L1 R_1 - L_1 .

3. First Weighing:
- L1=n(n−1)2x L_1 = \frac{n(n-1)}{2} x (total weight of coins from B1 B_1 ).
- R1=1x+2x+⋯+(n−1)x=(n−1)n2x R_1 = 1x + 2x + \cdots + (n-1)x = \frac{(n-1)n}{2} x (total weight of coins from B2,B3,…,Bn B_2, B_3, \ldots, B_n ).
- If B1 B_1 contains false coins, L1=n(n−1)2(x+d) L_1 = \frac{n(n-1)}{2} (x + d) .
- If Bi B_i (for i≥2 i \geq 2 ) contains false coins, R1=(n−1)n2x+(i−1)d R_1 = \frac{(n-1)n}{2} x + (i-1)d .

4. Second Weighing:
- Empty the right pan.
- Take (n−1),(n−2),(n−3),…,1 (n-1), (n-2), (n-3), \ldots, 1 coins from bags B2,B3,…,Bn B_2, B_3, \ldots, B_n respectively and place them on the right pan.
- Let the reading be R2−L2 R_2 - L_2 .

5. Second Weighing Calculation:
- L2=n(n−1)2x L_2 = \frac{n(n-1)}{2} x (same as L1 L_1 ).
- R2=(n−1)x+(n−2)x+⋯+1x=(n−1)n2x R_2 = (n-1)x + (n-2)x + \cdots + 1x = \frac{(n-1)n}{2} x .
- If B1 B_1 contains false coins, L2=n(n−1)2(x+d) L_2 = \frac{n(n-1)}{2} (x + d) .
- If Bi B_i (for i≥2 i \geq 2 ) contains false coins, R2=(n−1)n2x+(n−i+1)d R_2 = \frac{(n-1)n}{2} x + (n-i+1)d .

6. Conclusion:
- If R1−L1=R2−L2 R_1 - L_1 = R_2 - L_2 , then B1 B_1 contains false coins.
- If R1−L1≠R2−L2 R_1 - L_1 \neq R_2 - L_2 , then some Bi B_i (for i≥2 i \geq 2 ) contains false coins.
- If R1−L1=(i−1)d R_1 - L_1 = (i-1)d and R2−L2=(n−i+1)d R_2 - L_2 = (n-i+1)d , then i=n(R1−L1)(R2−L2)+(R1−L1)+1 i = \frac{n(R_1 - L_1)}{(R_2 - L_2) + (R_1 - L_1)} + 1 .

7. Determining the Weight Difference:
- If R1−L1>0 R_1 - L_1 > 0 , the false coins are heavier.
- If R1−L1<0 R_1 - L_1 < 0 , the false coins are lighter.

The final answer is i=n(R1−L1)(R2−L2)+(R1−L1)+1 \boxed{ i = \frac{n(R_1 - L_1)}{(R_2 - L_2) + (R_1 - L_1)} + 1 } .

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.