candy pieces and places them in a row on a table. Then, she chooses one of the following operations (if available) and executes it:
She eats a candy of type 
followed by one candy type 
(we consider type 
to be type 1, and type 0 to be type 
She chooses two consecutive candies which are the same type, and eats them.
and any configuration of candies on the table.
of 
with 
elements. Prove that there exist three elements 
from 
.
be a convex hexagon with 
and 
.
which is equidistant from sides 
and 
.
and 
are the centers of mass of 
and 
,
.
Y by Davi-8191, tenplusten, MathbugAOPS, Welp..., OlympusHero, mathleticguyyy, centslordm, jhu08, iker_tz, Adventure10, lian_the_noob12, RandomPerson11, NicoN9
The leader of an IMO team chooses positive integers 
and 
with 
, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an -digit binary string, and the deputy leader writes down all -digit binary strings which differ from the leader’s in exactly positions. (For example, if 
and 
, and if the leader chooses 
, the deputy leader would write down 
and 
.) The contestant is allowed to look at the strings written by the deputy leader and guess the leader’s string. What is the minimum number of guesses (in terms of and ) needed to guarantee the correct answer?
and 
with 
, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an -digit binary string, and the deputy leader writes down all -digit binary strings which differ from the leader’s in exactly positions. (For example, if 
and 
, and if the leader chooses 
, the deputy leader would write down 
and 
.) The contestant is allowed to look at the strings written by the deputy leader and guess the leader’s string. What is the minimum number of guesses (in terms of and ) needed to guarantee the correct answer?
The binary strings of length 
under the metric 
given explicitly by 
It can be checked that this satisfies the requisite axioms. (This is the exact same measure of "distance" used in the problem.)
equipped with the standard Euclidean metric 
given explicitly by
Again, it is well-known that this satisfies the axioms of a metric on a space.
.
that maps as 
and satisfies 
Because the map 
is monotonic and injective, all geometric equalities (and inequalities) are preserved through the above mapping. Lastly, let 
.
and 
,
.
-
through 
and orthogonal to 
,
(and thus the distance in Lemma III is 
)
(and pick the correct one). On the other hand, if ![\[\begin{cases}
2\text{ tries } & \text{if}\ k=0.5n\\
1\text{ try } & \text{otherwise}\\
\end{cases}
\]](http://latex.artofproblemsolving.com/d/4/9/d4968c30f0e06d9b6fe417a4c47c74be6f5c0bdf.png)
be the set of the numbers writen by the deputy leader
in 
, there is a set of 
elements that contains the numbers that have exacly 
. Then , let 
be the number that has every digits different from 
and 
on the paper of the deputy leader , if the digits 
of 
of 
, which implies that the intersection of every 
,
. Suppose that the contestant must guess more than one time, that means , the intersection of every 
such that for every way to change 
, we can find a way to change 
has very digits different. So , we change the 
digits are different. Then We must change the last 
which is a contradiction
equal numbers. For convinient, we move these 
and 
, because , if 
, we change 
in 
in 
digits 
in 
,
digits 
and 
,
.
,
then 
which is a contradiction
.
then we can avoid the case 
,
be positive integers. 
and writes down 
strings, how much of these strings are actually necessary?
and 
.
positions and differ in 
positions. For each non-negative integer 
in the interval ![$[k - b, \min(a, k)]$](http://latex.artofproblemsolving.com/4/3/7/43710235d0ebac6d07821426664aa8c41af9f304.png)
consider a string 
that differs from 
of the positions where 
,
.
this gives 
and thus 
are equal, which is impossible. Thus 
and 
,
which implies 
,
is a valid choice. As this must be the only choice we obtain 
and hence 
as 
.
which implies 
zeroes and 
method in the case that 
:
as in post# 3. Compute 
.
.
to be 
if 
and 
,
,
entry equal to 
.
,
.
algorithm for the case with 
.
remains linearly independent (this may be checked with gaussian elimination in 
time where 
is the number of accumulated vectors.) Stop when we have 
.
with 
and save 
for later. Define 
to be the 
entry of 
matrix 
.
so that 
.
with gaussian elimination. Construct 
satisfying 
for 
and 
.
so that 
and 
.
and 
.
,
(= 111...1) differs from each of these 
and 
(the first string starts with 
or 
.
,
and the string is 
,
,
,
,
strings and from these 
have the 
'
wrong.
.
and 
.
has the first 
be it's 
be the collection of strings we've been given.
.
strings in 
strings which are the same as ![\[\binom{n - 1}{k - 1} = \binom{n - 1}{k} \iff n = 2k.\]](http://latex.artofproblemsolving.com/e/d/c/edc7dfe9bbef3f89f873c3cf5aea0274fa2ba932.png)
since 
we can uniquely determine the first position of the string.
and consider only the last 
positions of 
.
and 
.
,
,
so we need to consider both the scenarios. From here we can either continue with our process as in case 1 and 2. To uniquely determine our string except for the first position.
.
strings which have the wrong digit at the 
position, and 
strings which have the correct digit at the 
.
.
groups each consisting of two complementary binary strings. Select one group at random, and label its elements 
and 
.
strings out of the deputy leader's list would also suffice (which is obvious by using PHP and our argument). Thus, the question could also have asked for the minimum number of strings which the contestant needs to be shown in order for him to guess the leader's string in minimum number of guesses.
), which fortunately doesn't really affect the problem much. The contestant can easily figure out 
,
equals 
,
of Zuming's strings have their 
strings have their 
.
,
be a string which produces the same 
strings from Zuming. Suppose that 
differs from 
places.
,
,
places that 
places, which poses a contradiction.
,
then the same reasoning for when 
works again. Hence there are 
and the number of incorrect values is 
.
,
,
when 
.
.
,
,
strings with these 
and 
Po-Shen needs 
then for each of the 
then for each of the 
of the strings in the given set will have that digit correct (among the other 
place values, we need 
of the strings in the given set will have that digit wrong (among the other 
and if 
so it can always be determined which digit is correct and which digit is wrong for each place value of the mystery string before making the first guess, as desired.
there is a strategy to guess the mystery string on the first attempt, we've finished our proof. 
and 
.
with the string 
.
ways but the first digit is correct and second digit incorrect in 
ways. Thus we can deduce the second digit and in a similar fashion the rest of the sting. The case where the first digit is incorrect gives the other case, so we are done.
digit will be flipped in 
of the given binary strings. So unless 
Po-Shen can directly find what each digit must be and in find the correct string in 1 guess. Now, suppose 
.
strings ending with 
,
the first 
places. Otherwise, we can view it as being given a string of length 
places. In each of these cases, the contestant needs just one attempt, hence 
strings written down. The original bit will appear 
times and the flipped bit will appear 
times as 
by considering only the 
times is the correct digit. The only problem arises when 
which is true iff 
,
times and the wrong one will appear 
times (even if the first digit is wrong, the digits in this place will have the same number of occurrences in the reverse order). These two aren't equal since 
is even, so pick the one that appears 
we have 
Therefore there are multiple pairs of strings that differ at 
guess.
we can look at pairs of strings that differ by 
places. Then, for the other 
possibilites as there were 
.
times. Thus at each digit the contestant can look at all of the binary strings written and pick the digit that appears 
times and that gives them the correct bit.
so the contestant can no longer pick the correct digit just by looking at the number of times they appear. However, the contestant can guess the first bit to be 
