Winter Mathematical Competition

a) Let the length of the strip be $n$. Denote by $g(n)$ and $f(n)$ respectively the number of $1$'s in the binary representation of $n$ and the minimum possible number of bad cuts. Let $n=2^{k_1}+2^{k_2}+\cdots +2^{k_l}$. Consider the following sequence of cuts: first cut a strip of length $2^{k_1}$, next cut a strip of length $2^{k_2}$ and so on. After the last cut we obtain two strips of lengths $2^{k_{l-1}}$ and $2^{k_l}$. Note that a strip whose length is a power of $2$ can be cut into strips of length $1$ without bad cuts. Therefore the number of bad cuts equals $l-1$, i.e. $$(1)f(n)\le g(n)-1.$$ We prove by induction on $n$ that $f(n)\ge g(n)-1$. For $n=1$ we have $f(1)=0$ and $g(1)=1$, i.e. the statement is true. Suppose it is true for all $n\le k$, where $k$ is a positive integer and let $n=k+1$.

1. Suppose the first cut is bad and it leaves two strips of lengths $a$ and $b$. Then $a+b=k+1$ and $f(k+1)=1+f(a)+f(b)$. If the binary representations of $a$ and $b$ have no common digit $1$ then $g(k+1)=g(a)+g(b)$ and therefore $$f(k+1)=1+f(a)+f(b)\ge 1+g(a)-1+g(b)-1=g(k+1)-1.$$ If the binary representations of $a$ and $b$ have at least one common digit $1$ then $g(k+1)\le g(a)+g(b)-1$ and therefore $$f(k+1)=1+f(a)+f(b)\ge 1+g(a)-1+g(b)-1\ge g(k+1)>g(k+1)-1.$$

2. Suppose the first cut is not bad, i.e. the strip is cut into two parts each of length $a$. Then $k+1=2a$ and $g(k+1)=g(a)$. If $g(k+1)=1$ then $f(k+1)=0$ and the statement is true. Otherwise $$f(k+1)=f(a)+f(b)=2f(a)\ge 2g(a)-2=2g(k+1)-2>g(k+1)-1.$$ Thus, when $g(k+1)>1$ we have $f(k+1)>g(k+1)-1$.

This proves the induction hypothesis giving $$(2)f(n)\ge g(n)-1.$$ It follows from (1) and (2) that $f(n)=g(n)-1$.

a) Since the binary representation of $2007$ is $1111010111$, i.e. $g(2007)=9$, we obtain $f(2007)=8$.

b) It follows from the above arguments that if the number of bad cuts is $f(n)=g(n)-1$ then every bad cut leaves two parts of lengths $a$ and $b$ such that the binary representations of $a$ and $b$ have no common digit $1$. Moreover the good cuts are done only over strips whose lengths are powers of $2$. It is clear that rearranging the cuts we may assume that the first cuts are bad. Their number equals $g(n)-1$ and each bad cut gives two new numbers on the table. Therefore after all bad cuts we have $2g(n)-2$ distinct numbers. The powers of $2$ that appear are all powers up to the highest power in the binary representation of $n$. Thus, the number of distinct numbers on the table equals $2g(n)-2+k+1=2g(n)+k-1$, where $k$ is the highest power of $2$ in the binary representation of $n$.