Difference between revisions of "2010 OIM Problems/Problem 1"
(Created page with "== Problem == There are ten indistinguishable coins placed in a line. It is known that two of them are false and occupy consecutive positions on the line. For each set of posi...") |
(solution) |
||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | There are ten indistinguishable coins placed in a line. It is known that two of them are | + | There are ten indistinguishable coins placed in a line. It is known that two of them are fake and occupy consecutive positions on the line. For any set of positions, you can ask how many fake coins it contains. Is it possible to determine which coins are fake asking only two of these questions, without knowing the answer to the first one before formulating the second? |
~translated into English by Tomas Diaz. ~orders@tomasdiaz.com | ~translated into English by Tomas Diaz. ~orders@tomasdiaz.com | ||
== Solution == | == Solution == | ||
| − | + | The intuition behind the setup below is that the answer will always be <math>2,1,</math> or <math>0</math>. Thus we have <math>3</math> possibilities, so we can determine the difference between <math>3</math> sets of coins. Since we have two questions, there are <math>3\times3=9</math> sets we can differentiate, which is exactly the number of consecutive positions there are. | |
| + | |||
| + | We claim that the coins we should ask (marked in red below) are: | ||
| + | <asy> | ||
| + | dot((0,0));dot((1,0));dot((2,0),red);dot((3,0),red);dot((4,0),red);dot((5,0),red);dot((6,0));dot((7,0));dot((8,0));dot((9,0),red); | ||
| + | </asy> | ||
| + | <asy> | ||
| + | dot((0,0));dot((1,0));dot((2,0),red);dot((3,0),red);dot((4,0));dot((5,0));dot((6,0));dot((7,0),red);dot((8,0),red);dot((9,0),red); | ||
| + | </asy> | ||
| + | Every pair of answers corresponds to exactly one of the consecutive pairs, so we are done. | ||
| + | |||
| + | ~ [https://artofproblemsolving.com/wiki/index.php/User:Eevee9406 eevee9406] | ||
== See also == | == See also == | ||
[[OIM Problems and Solutions]] | [[OIM Problems and Solutions]] | ||
Latest revision as of 16:05, 23 March 2025
Problem
There are ten indistinguishable coins placed in a line. It is known that two of them are fake and occupy consecutive positions on the line. For any set of positions, you can ask how many fake coins it contains. Is it possible to determine which coins are fake asking only two of these questions, without knowing the answer to the first one before formulating the second?
~translated into English by Tomas Diaz. ~orders@tomasdiaz.com
Solution
The intuition behind the setup below is that the answer will always be 
or 
. Thus we have 
possibilities, so we can determine the difference between sets of coins. Since we have two questions, there are 
sets we can differentiate, which is exactly the number of consecutive positions there are.
We claim that the coins we should ask (marked in red below) are:
![[asy] dot((0,0));dot((1,0));dot((2,0),red);dot((3,0),red);dot((4,0),red);dot((5,0),red);dot((6,0));dot((7,0));dot((8,0));dot((9,0),red); [/asy]](http://latex.artofproblemsolving.com/9/0/e/90e4448ec6c22b3da26900413974afc6b9244fe3.png)
![[asy] dot((0,0));dot((1,0));dot((2,0),red);dot((3,0),red);dot((4,0));dot((5,0));dot((6,0));dot((7,0),red);dot((8,0),red);dot((9,0),red); [/asy]](http://latex.artofproblemsolving.com/f/1/d/f1dfa644cb66b805145c6a2cf3d6353aa022fb4f.png)
Every pair of answers corresponds to exactly one of the consecutive pairs, so we are done.
