IMO Hk TST

We construct the numbers recursively. Firstly, we start from the following $2^2$ integers:
77, 78, 87, 88,
each of which has $2^1$ digits, and at most $2^0$ digit of each pair is the same.
Suppose we have constructed $k = 2^{n+1}$ integers $a_1, a_2, \dots, a_k$ with digits 7, 8, each of which has $2^n$ digits, and at most $2^{n-1}$ digits of each pair are the same. We construct $2k = 2^{n+2}$ integers as follows:
$$\overline{a_1a_1}, \overline{a_2a_2}, \dots, \overline{a_ka_k}, \overline{a_1b_1}, \overline{a_2b_2}, \dots, \overline{a_kb_k},$$
where $b_j$ means the integer having the same number of digits as $a_j$ such that each digit is different from that of $a_j$ (and is still 7 or 8). For example, when $n=1$, we construct
7777, 7878, 8787, 8888, 7788, 7887, 8778, 8877.

Note that each of the integers constructed has $2 \cdot 2^n = 2^{n+1}$ digits. Also, one can easily prove by induction that $b_1, b_2, \dots, b_k$ is a permutation of $a_1, a_2, \dots, a_k$.
* For $\overline{a_i a_i}$ and $\overline{a_j a_j}$ (with $i \neq j$), at most $2 \cdot 2^{n-1} = 2^n$ of their digits are the same by the inductive hypothesis. Similarly, the same holds for the pair $\overline{a_i a_i}$ and $\overline{a_j b_j}$ unless $a_i = b_j$, and for the pair $\overline{a_i b_i}$ and $\overline{a_j b_j}$.
* For $\overline{a_i a_i}$ and $\overline{a_j b_j}$ with $a_i = b_j$, the first $2^n$ digits are different, while the last $2^n$ digits are the same.
* For $\overline{a_i a_i}$ and $\overline{a_j b_j}$, the first $2^n$ digits are the same, while the last $2^n$ digits are different.
Thus, in any case, each pair of integers shares at most $2^n$ same digits. Repeating the same procedure, we eventually obtain $2^{2006}$ integers satisfying all the conditions.