Andryusha has $100$ stones of different weight and he can distinguish the stones by appearance, but does not know their weight. Every evening, Andryusha can put exactly $10$ stones on the table and at night the brownie will order them in increasing weight. But, if the drum also lives in the house then surely he will in the morning change the places of some $2$ stones.Andryusha knows all about this but does not know if there is a drum in his house. Can he find out?
Problem
Source: Saint Petersburg MO 2020 Grade 10 Problem 1
Tags: combinatorics
18.05.2020 10:48
Yes he can. Consider a 10-tuple ,call the changed pair (if it exists) bad and let $S$ be the set of the $100$ stones. Step_1 Let him consider $3$ disjoint $10$-tuples $A, B$ and $C$ and have him note down all the greater-smaller relations as they occur after a night has passed. Step_2 Consider all 10-tuples of this type: $2$ stones from each of $A$, $B$ and $C$ ($6$ in total) and a fixed $4$tuple from $S/ \{A,B,C\}$. Have him do this so that all of the $\binom{10}{2} \binom{10}{2} \binom{10}{2}$ $6$tuples occur in one such $10$-tuple. This means that one of these $10$-tuples must contain all $3$ bad pairs of $A$, $B$ and $C$, wlog $(a_1,a_2), (b_1,b_2), (c_1,c_2)$, respectively. with $a_1<a_2$ , $b_1<b_2$ ,$c_1<c_2$ in the actual weight catalog but with $a_1>a_2$ , $b_1>b_2$ , $c_1>c_2$ in the drums catalog and the one that the guy playing has noted down. Since , drum can only change $2$ of these $6$ stones one of these pairs remains for sure unchanged and hence $A$ has his notes contradicted. Which means there is a drum. If after the above procedure none of the notes he has written are contradicted, then the drum is not in his house.