1
$\begingroup$

We have $20$ coins, every step we can give $10$ coins to a person and he will tell us the order of their weights. Find the minimum number of steps that we can arrange coins according to their weight.

My attempt:I found a method using $5$ steps.

1.Divide the coins to two equal halfs and give one of the halfs to that person.

2.Give the second half to that person.

3.Give $5$ heavy coins from the first step and $5$ heavy coins from the second step to that person.

4.Do the same as third step but this time use the $5$ light coins of step $1$,$2$

5.Give $5$ light coins from the third step and $5$ heavy coins from the forth step to that person.

This is a copy of this one.

According to the answer of @Aryabhata the above algorithm works. Now I need a proof for showing $5$ steps is the minimum desired. Any way I copy @Aryabhata's answer here:

For a proof that your procedure works:

Let the result of steps 1 and 2 be

$$A_1 \ge A_2 \ge \dots \ge A_{10}$$

and

$$B_1 \ge B_2 \ge \dots \ge B_{10}$$

The result of step 3 will be some permutation of

$$A_1, A_2, \dots, A_5, B_1, B_2, \dots, B_5$$

The result of step 4 will be some permutation of

$$A_6, A_7, \dots, A_{10}, B_6, B_7, \dots, B_{10}$$

If $B_j$ was the lightest of the heaviest 5 coins from step $3$, then it is easy to see that $j \le 5$: The 5 heaviest are $A_1, A_2, \dots, > A_{5-j}, B_1, B_2, B_j$

Similarly if $B_k$ was the heaviest of the lightest 5 from step 4, then $k \ge 6$.

Thus you have a partition by weight

Heaviest in step $3$ $\ge$ Lightest $5$ in step $3$, Heaviest $5$ in step $4$ $\ge$ Lightest 5 in step 4

You step 5 now sorts the middle portion and brings everything in order.

Math SE copy is here and AOPS copy is here.

Source:Second round Iranian olympiad of informatics.

Improve this question
$\endgroup$
12
  • $\begingroup$ two steps... give him 10 coins, arrange them based on what he tells us... give him 10 more and arrange accordingly? $\endgroup$
    – Jason V
    Commented Aug 4, 2017 at 12:53
  • 1
    $\begingroup$ @Jason, try it with 4: if coin 1 is heavier than coin 2 and coin 3 is heavier than coin 4, what is the final order? There is no information about how the first set relates to the second. $\endgroup$
    – Forklift
    Commented Aug 4, 2017 at 13:16
  • 1
    $\begingroup$ @Jason He gives the order of only the 10 coins that on that turn; he does not combine the next 10 with the previous 10. In your scenario, which weighs more: the heaviest coin in the first set or the heaviest coin in the second set. If you can answer that, how did you determine the answer? $\endgroup$
    – Apep
    Commented Aug 4, 2017 at 13:17
  • 1
    $\begingroup$ Here's an incorrect argument for why at least 4 is needed. In a set of 20 coins, there are $20*21/2=210$ pairs that need to be compared. In a comparison of 10 coins, $10*11/2=55$ pairs are compared. Therefore we need at least $ \lceil{210/55}\rceil = 4$ comparisons. Unfortunately this is bogus, since not every pair needs to be compared. If $a<b$ and $b<c$, we can deduce $a<c$ without actually checking. $\endgroup$
    – Jaap Scherphuis
    Commented Aug 4, 2017 at 13:28
  • 1
    $\begingroup$ Post the answer with the question seems odd to me. $\endgroup$
    – paparazzo
    Commented Aug 4, 2017 at 15:45

1 Answer 1

Reset to default
3
+100
$\begingroup$

Your question was also asked in a Russian math olympiad (with 100 coins instead of 20). I found a solution here: https://artofproblemsolving.com/community/c6h530369p3026656. I think the solution left out some details, so I've reworded it and filled them in. This proof also generalizes to the case of trying to sort $2n$ coins, provided $n$ is of the form $4k+2$. I think it can be adapted to work when $n$ is odd, but I haven't thought about what happens when $n$ is a multiple of four.

To prove that four tests are insufficient, suppose that the true order of the coins is $c_1\le c_2\le \dots\le c_{20}$. In order to succeed, for each consecutive pair of coins $\{c_i,c_{i+1}\}$, there must be some test where both coins in the pair handed to your friend. Otherwise, you could not distinguish the true order from $c_1\le \dots\le c_{i-1}\le c_{i+1}\le c_i\le c_{i+2}\le \dots\le c_{20}$.

Suppose that the results of the first two tests are $a_1\le a_2\le\dots\le a_{10}$ and $b_1\le b_{2}\le \dots\le b_{10}$. These two lists of coins might overlap. No matter what coins are chosen for the second test, it will be possible for the overlaps to be distributed among the $a$ list with the same spacings as in the $b$ list, as shown below: $$ \begin{array}{} a_1\le \dots\le a_{{k_1}-1}\le&a_{k_1} \le& a_{k_1+1}\le \dots\le a_{{k_2}-1}\le & a_{k_2} \le a_{k_2+1}\cdots\\ &\updownarrow&&\updownarrow\\ b_1\le \dots\le b_{k_1-i}\le & a_{k_1} \le& b_{k_1+1}\le \dots\le b_{{k_2}-1}\le & a_{k_2}\le b_{k_2+1}\cdots \end{array} $$ Assume that this does happen. We will now build a particular total ordering of the coins, consistent with these two tests. We do this in blocks of four as follows. The $*$'s represent any coins which were not tested during the first two tests. $$ (c_{4i+1},c_{4i+2},c_{4i+3},c_{4i+4})=\begin{cases}(a_{2i+1},b_{2i+1},a_{2i+2},b_{2i+2})&\text{if }\hspace{.3cm}a_{2i+1}\neq b_{2i+1},a_{2i+2}\neq b_{2i+2} \\ (a_{2i+1},b_{2i+1},*,a_{2i+2})&\text{if }\hspace{.3cm}a_{2i+1}\neq b_{2i+1},a_{2i+2}= b_{2i+2} \\ (a_{2i+1},*,a_{2i+2},b_{2i+2})&\text{if }\hspace{.3cm}a_{2i+1}=b_{2i+1},a_{2i+2}\neq b_{2i+2} \\ (a_{2i+1},*,*,a_{2i+2})&\text{if }\hspace{.3cm}a_{2i+1}=b_{2i+1},a_{2i+2}=b_{2i+2} \end{cases} $$ The general idea is to try to interleave the $a$ and $b$ lists, and whenever overlaps occur, using the untested coins to fill the gaps.

Note that for all $1\le i \le 5$, the consecutive pairs $\{c_{4i+1},c_{4i+2}\},\{c_{4i+2},c_{4i+3}\},$ and $\{c_{4i+3},c_{4i+4}\}$ have not been tested together. These need to be taken care of during tests three and four.

Since all 20 coins are represented among the 15 untested pairs, each coin must be used in exactly one test. This means that all four coins in the block $(c_{4i+1},c_{4i+2},c_{4i+3},c_{4i+4})$ have to be submitted in the same test. But there are five such blocks of four coins, and you can only fit two of the blocks in a single test, so in this case it is impossible to succeed.

Improve this answer
$\endgroup$
11
  • $\begingroup$ I missed sth to write in my question:The coins have different weights so could you delete extra parts to make the proof easier for me to understand? $\endgroup$
    – Taha Akbari
    Commented Aug 8, 2017 at 18:18
  • $\begingroup$ This proof does assume all the coins have different weights. When I say overlaps, I mean a situation like this. For your first test, you test coins 1 through 10, and for your second, you test 6 through 15. In that case, five of the $a$ coins are equal to five of the $b$ coins. There is no way to get rid of the complicated parts, since we need to prove you cannot succeed no matter what you do on the first two tests. $\endgroup$
    – Mike Earnest
    Commented Aug 8, 2017 at 18:38
  • $\begingroup$ The way you've written the outcomes of the first two tests, it looks as if the common coins will always occur at matching positions. However the first common coin could be, say, lightest in the first test and third lightest in the second (i.e. $a_1=b_3$). A simpler way to think about these steps in the proof is to replace each shared coin in the $b_i$ sequence by an untested coin and then interweave the $a_i$ sequence and this edited $b_i$ sequence. $\endgroup$
    – Jaap Scherphuis
    Commented Aug 8, 2017 at 22:43
  • 1
    $\begingroup$ @JaapScherphuis (1) I'm not saying common coins always occur at matching positions, I'm just saying that no matter what weighing strategy you use it is possible for this to occur, and if it does occur then you are doomed. (2) Your modification to the proof makes it much more elegant, I will edit it in. $\endgroup$
    – Mike Earnest
    Commented Aug 8, 2017 at 23:04
  • $\begingroup$ You're right. If the common coins don't occur at the same locations in the outcomes of the first two tests, then you've been lucky and have gained extra information that may allow you to use fewer steps (e.g. in the extreme case $a_{10}=b_1$ means you have sorted all but one coin which you can finish in 2 more steps). The worst case is when the common coins do occur at the same locations, and in that case the proof shows that 5 steps is necessary. So assume the worst. Similarly we can assume the untested coins lie between $b_{i-1}$ and $b_{i+1}$ where $b_i$ is a common coin and swap them in. $\endgroup$
    – Jaap Scherphuis
    Commented Aug 8, 2017 at 23:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.