Maths Olympiad Prep

Library / /3 of 3

Combinatorics Difficulty 6.8 National olympiad Find the answer

In Vila Par, all the truth coins weigh an even quantity of grams and the false coins weigh an odd quantity of grams. The eletronic device only gives the parity of the weight of a set of coins. If there are 20202020 truth coins and 22 false coins, determine the least kk, such that, there exists a strategy that allows to identify the two false coins using the eletronic device, at most, kk times.

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

Solution

In the given problem, we have 2020 true coins, each weighing an even number of grams, and 2 false coins, each weighing an odd number of grams. The electronic device available can detect the parity (even or odd) of the total weight of a set of coins. We need to determine the minimum number of measurements, k k , required to identify the two false coins using this parity information.

The key insight is that each measurement provides a single bit of information (even or odd), and we use these bits to gradually identify the false coins among the total 2022 coins (2020 true + 2 false).

### Strategy to Identify the False Coins:

1. Understanding Parity Checks:
- The even number of grams for the true coins will give an even total parity when weighed in any even numbers.
- Any odd number of grams, when added to the even total, will result in an odd parity.

2. Binary Cutting Technique:
- Similar to a binary search, we can narrow down the possible false coins by half with each parity check.
- The primary goal is to ensure that the number of possible combinations after each measurement is reduced significantly, ideally halved.

3. Calculation of Minimum Measurements:
- With n=2022 n = 2022 coins, our task is to identify 2 specific false coins.
- Given that each measurement provides one bit of information, and knowing the initial uncertainty involves differentiating the 2 out of 2022, this is equivalent to differentiating among (20222)2,041,231 \binom{2022}{2} \approx 2,041,231 possible pairs of coins.
- Thus, the number of measurements required to determine these false coins is given by the smallest k k such that:
2k(20222) 2^k \geq \binom{2022}{2}

4. **Calculate the Smallest k k :**
- We approximate:
- log2((20222))log2(2,041,231)21.0 \log_2(\binom{2022}{2}) \approx \log_2(2,041,231) \approx 21.0 .
- Hence, the smallest integer k k satisfying this inequality is k=21 k = 21 .

Therefore, the minimum number of measurements required to definitively identify the two false coins using the electronic device is:
21 \boxed{21}

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