The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) 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 $n$ and $k$) needed to guarantee the correct answer?

Let $Q=\{0,1\}^n$, and let $A$ be a subset of $Q$ with $2^{n-1}$ elements. Prove that there are at least $2^{n-1}$ pairs $(a,b)\in A\times (Q\setminus A)$ for which sequences $a$ and $b$ differ in only one term.

Given is a natural number $n > 5$. On a circular strip of paper is written a sequence of zeros and ones. For each sequence $w$ of $n$ zeros and ones we count the number of ways to cut out a fragment from the strip on which is written $w$. It turned out that the largest number $M$ is achieved for the sequence $11 00...0$ ($n-2$ zeros) and the smallest - for the sequence $00...011$ ($n-2$ zeros). Prove that there is another sequence of $n$ zeros and ones that occurs exactly $M$ times.

The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) 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 $n$ and $k$) needed to guarantee the correct answer?

The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) 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 $n$ and $k$) needed to guarantee the correct answer?

For each positive integer $n$, let $a_n = 0$ (or $1$) if the number of $1$’s in the binary representation of $n$ is even (or odd), respectively. Show that there do not exist positive integers $k$ and $m$ such that $$a_{k+j}=a_{k+m+j} =a_{k+2m+j}$$ for $0 \leq j \leq m-1.$

For every non-negative integer $i$, define the number $M(i)$ as follows: write $i$ down as a binary number, so that we have a string of zeroes and ones, if the number of ones in this string is even, then set $M(i) = 0$, otherwise set $M(i) = 1$. (The first terms of the sequence $M(i)$, $i = 0, 1, 2, ...$ are $0, 1, 1, 0, 1, 0, 0, 1,...$ ) (a) Consider the finite sequence $M(O), M(1), . . . , M(1000) $. Prove that there are at least $320$ terms in this sequence which are equal to their neighbour on the right : $M(i) = M(i + 1 )$ . (b) Consider the finite sequence $M(O), M(1), . . . , M(1000000)$ . Prove that the number of terms $M(i)$ such that $M(i) = M(i +7)$ is at least $450000$. (A Kanel)

For every integer $n \ge 2$ let $B_n$ denote the set of all binary $n$-nuples of zeroes and ones, and split $B_n$ into equivalence classes by letting two $n$-nuples be equivalent if one is obtained from the another by a cyclic permutation.(for example 110, 011 and 101 are equivalent). Determine the integers $n \ge 2$ for which $B_n$ splits into an odd number of equivalence classes.

Let $n$ be a fixed positive integer. Oriol has $n$ cards, each of them with a $0$ written on one side and $1$ on the other. We place these cards in line, some face up and some face down (possibly all on the same side). We begin the following process consisting of $n$ steps: 1) At the first step, Oriol flips the first card 2) At the second step, Oriol flips the first card and second card . . . n) At the last step Oriol flips all the cards Let $s_0, s_1, s_2, \dots, s_n$ be the sum of the numbers seen in the cards at the beggining, after the first step, after the second step, $\dots$ after the last step, respectively. a) Find the greatest integer $k$ such that, no matter the initial card configuration, there exists at least $k$ distinct numbers between $s_0, s_1, \dots, s_n$. b) Find all positive integers $m$ such that, for each initial card configuration, there exists an index $r$ such that $s_r = m$. [i]Proposed by Dorlir Ahmeti[/i]

For any given non-negative integer $m$, let $f(m)$ be the number of $1$'s in the base $2$ representation of $m$. Let $n$ be a positive integer. Prove that the integer $$\sum^{2^n - 1}_{m = 0} \Big( (-1)^{f(m)} \cdot 2^m \Big)$$ contains at least $n!$ positive divisors.

The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) 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 $n$ and $k$) needed to guarantee the correct answer?

The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) 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 $n$ and $k$) needed to guarantee the correct answer?

For a positive integer $n$, let $s(n)$ denote the sum of the binary digits of $n$. Find the sum $s(1)+s(2)+s(3)+...+s(2^k)$ for each positive integer $k$.

Let $B(n)$ be the number of ones in the base two expression for the positive integer $n.$ Determine whether $$\exp \left( \sum_{n=1}^{\infty} \frac{ B(n)}{n(n+1)} \right)$$ is a rational number.

If the binary representations of the positive integers $k$ and $n$ are $k = \sum_{i=0}^{\infty} k_i 2^i$ and $n = \sum_{i=0}^{\infty} n_i 2^i$, then the logical sum of these numbers is \[ k \oplus n =\sum_{i=0}^{\infty} |k_i-n_i|2^i. \] Let $N$ be an arbitrary positive integer and $(c_k)_{k \in \mathbb{N}}$ be a sequence of complex numbers such that for all $k \in \mathbb{N}$, $ |c_k| \le 1$. Prove that there exist positive constants $C$ and $\delta$ such that \[ \int_{[-\pi,\pi] \times [-\pi, \pi]} \sup_{n<N, n \in \mathbb{N}} \frac{1}{N} \Big| \sum_{k=1}^{n} c_k e^{i(kx+(k \oplus n) y)} \Big| \mathrm d(x,y) \le C \cdot N^{-\delta} \] holds.

The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) 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 $n$ and $k$) needed to guarantee the correct answer?

Keith has $10$ coins labeled $1$ through $10$, where the $i$th coin has weight $2^i$. The coins are all fair, so the probability of flipping heads on any of the coins is $\tfrac{1}{2}$. After flipping all of the coins, Keith takes all of the coins which land heads and measures their total weight, $W$. If the probability that $137\le W\le 1061$ is $\tfrac{m}{n}$ for coprime positive integers $m,n$, determine $m+n$.

The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) 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 $n$ and $k$) needed to guarantee the correct answer?

The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) 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 $n$ and $k$) needed to guarantee the correct answer?

The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) 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 $n$ and $k$) needed to guarantee the correct answer?

The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) 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 $n$ and $k$) needed to guarantee the correct answer?

We say that a positive integer $n$ is [i]memorable[/i] if it has a binary representation with strictly more $1$'s than $0$'s (for example $25$ is memorable because $25=(11001)_{2}$ has more $1$'s than $0$'s). Are there infinitely many memorable perfect squares? [i]Proposed by Nikola Velov[/i]

The leader of an IMO team chooses positive integers $n$ and $k$ with $n > k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader’s in exactly $k$ positions. (For example, if $n = 3$ and $k = 1$, and if the leader chooses $101$, the deputy leader would write down $001, 111$ and $100$.) 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 $n$ and $k$) needed to guarantee the correct answer?

Serge and Tanya want to show Masha a magic trick. Serge leaves the room. Masha writes down a sequence $(a_1, a_2, \ldots , a_n)$, where all $a_k$ equal $0$ or $1$. After that Tanya writes down a sequence $(b_1, b_2, \ldots , b_n)$, where all $b_k$ also equal $0$ or $1$. Then Masha either does nothing or says “Mutabor” and replaces both sequences: her own sequence by $(a_n, a_{n-1}, \ldots , a_1)$, and Tanya’s sequence by $(1 - b_n, 1 - b_{n-1}, \ldots , 1 - b_1)$. Masha’s sequence is covered by a napkin, and Serge is invited to the room. Serge should look at Tanya’s sequence and tell the sequence covered by the napkin. For what $n$ Serge and Tanya can prepare and show such a trick? Serge does not have to determine whether the word “Mutabor” has been pronounced.

Messages are coded using sequences consisting of zeroes and ones only. Only sequences with at most two consecutive ones or zeroes are allowed. (For instance the sequence $011001$ is allowed, but $011101$ is not.) Determine the number of sequences consisting of exactly $12$ numbers.