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 $2020$ truth coins and $2$ false coins, detemine the least $k$, such that, there exists a strategy that allows to identify the two false coins using the eletronic device, at most, $k$ times.
Problem
Source: Rioplatense L-1 2022 #6
Tags: combinatorics
AngleWatchers
13.12.2022 19:12
I think the answer is $1349$. Solution: WLOG, let the coins be named $a_1,a_2,a_3,$ and so on. Define $W_n$ as a weighing process of a set of coins from coin $a_n$ to $a_{n+673}$. We will prove that no matter the placement of the fake coins, there are always $W_i$ and $W_j$ where $i\neq j$ and both have different parities. Assume otherwise. Then, for $1\leq n\leq674$, $a_n,a_{n+674},$ and $a_{n+1348}$ must have the same parities because $W_n,W_{n+1},W_{n+674},$ and $W_{n+675}$ have the same parities. But this also means that there needs to be $3k$ false coins, where $k\in\mathbb{N}$, which contradicts. Now, notice that for $1\leq n\leq674$, we can always identify the parities of $a_n,a_{n+674},$ and $a_{n+1348}$ by taking a look at the parities of $W_n,W_{n+1},W_{n+674},$ and $W_{n+675}$. - Case 1: If both pairs $W_n,W_{n+1}$ and $W_{n+674},W_{n+675}$ have the same parities ($W_{n+1}$ and $W_{n+674}$ do not have to be the same parity), then $a_n,a_{n+674},$ and $a_{n+1348}$ have the same parities. Thus, all $3$ coins are truth coins. - Case 2: If both pairs $W_n,W_{n+1}$ and $W_{n+674},W_{n+675}$ have different parities, then $a_n$ and $a_{n+1348}$ have the same parities, but different from $a_{n+674}$. - Case 3: If $W_n,W_{n+1}$ have the same parity but $W_{n+674},W_{n+675}$ have different parity, then $a_n$ and $a_{n+674}$ have the same parities, but different from $a_{n+1348}$. - Case 4: If $W_n,W_{n+1}$ have different parity but $W_{n+674},W_{n+675}$ have the same parity, then $a_{n+674}$ and $a_{n+1348}$ have the same parities, but different from $a_n$. From here, we can search where the fake coins are by investigating how many the combined cases of 2,3, and 4 are. If the combined cases amount is $1$: - If it is case 2, then $a_n$ and $a_{n+1348}$ are the fake coins. - If it is case 3, then $a_n$ and $a_{n+674}$ are the fake coins. - If it is case 4, then $a_{n+674}$ and $a_{n+1348}$ are the fake coins. If the combined cases amount are $2$: - If one of the cases is case 2, then $a_{n+674}$ is one of the fake coins. - If one of the cases is case 3, then $a_{n+1348}$ is one of the fake coins. - If one of the cases is case 4, then $a_n$ is one of the fake coins. Also notice that the combined cases are not more than two because there are only $2$ fake coins. Thus, the minimum value of $k$ is $1349$.
PennyLane_31
22.11.2023 05:01
Actually, we can do with less! $21$ is sufficient!! And now you said omg, right? lol Well, first, this solution is not mine, but I think I should write here because other people may not be able to think these crazy things... Okay, now let's starrrt!! With $21$, we can give a number for each coin, from $0$ to $2021$, for example. Then, we rewrite these numbers in a binary system. Now, we divide the numbers into $11$ groups like this: (notice that as $2^{11}>2022$, we are good, which means that there are no numbers left, also, if we have a coin with less than $11$ digits, we add enough zeros in the left to complete) This is the first idea, can you finish from here? How divide the groups?
Group 1: all the numbers such that the first digit is $1$.
Group 2: all the numbers such that the second digit is $1$
$\vdots$
Group 11: all the numbers such that the $11-th$ digit is $1$.
We will use the electronic device 11 times to see which groups give us even and which ones are odd.
Now, we see that if one of the groups is even then, we have two possibilities: the two fake coins are in this same group or they are both out of this group, in both cases, we will have the same $i-th$ digit (supposing that the group i is even). So, if all the groups are even, then, for each $i-th$ digit in one of the coins, we have the same digit in the same position for the other coin $\implies$ the two fake coins would have the same representation in a binary system, impossible! So, we must have at least one of these groups being odd.
Well, if one of them is odd then one of the fake coins is in it. Also, this group has, at most, $2^{10}$ coins in it, so we just do some kind of binary search and discover we use at the most, $10$ times the electronic device. With that, we found one of the fake coins, now notice that the other is defined because we can do similarly as we did (compare the representation of the fake coins based on the parity of the 11 groups).
(if you don't know how to do the binary search, the motivation is: founded the odd group, just keep dividing into two groups, because always one will be odd and the other one is even, and keep doing this division in the odd group until you found the fake coin; it will show, eventually, and we can count this by doing $log_2 (n)= log_2 (2^{10})= 10$).
So, after all this, we discovered we used the electronic device 21 times.
But now you wonder... why can't we do with 20?
Try it out before!Basically, if we use just 20 times the device, we will have $2^{20}$ results (odd or even for each weighing). But, notice that $2^{20}< {{2022}\choose {2}}$. Can you see why this implies a contradiction?
Here's whyWhy does this imply contradiction? Well, for each weighing, we have two situations:
First one: we put $k$ coins into the device and it appears even.
So, the fake coins are both in this group or both of them are in the other group (2022-k) coins, so we would have: ${k\choose 2}+{2022-k\choose 2}$ possibilities of pairs of fake coins.
Second situation: we put $k$ coins into the device and it appears odd.
So, one of the fake coins is in the k group and the other one is in the (2022-k) group, which gives us $k(2022-k)$ possibilities. But if we sum the two cases, it gives us ${2022\choose 2}$ which means the cases are "complementary", so we can affirm that one of them is at least $\lfloor{\frac{{2022\choose 2}}{2}}\rfloor$ in each operation, so as we would have, initially $2022\choose 2$ pairs of possible fake coins, we reduce to the half, at least, in each operation, so, after 20 operations, the number of possible pairs of fake coins would be at least $\frac{{2022\choose 2}}{2^{20}}>1$, so it would be more than one pair of fake coins to analyze.
Therefore, we can't conclude, with 20 operations, which are fake coins! And now we finish congrats to the one who made until here lol