MathDB

3

Part of 1990 Turkey Team Selection Test

Problems(1)

Two n-digit numbers sharing some digits in base 2

Source: Turkey TST 1990 - P3

9/11/2013
Let nn be an odd integer greater than 1111; k∈Nk\in \mathbb{N}, k≥6k \geq 6, n=2k−1n=2k-1. We define d(x,y)=∣{i∈{1,2,…,n}∣xi≠yi}∣d(x,y) = \left | \{ i\in \{1,2,\dots, n \} \bigm | x_i \neq y_i \} \right | for T={(x1,x2,…,xn)∣xi∈{0,1},i=1,2,…,n}T=\{ (x_1, x_2, \dots, x_n) \bigm | x_i \in \{0,1\}, i=1,2,\dots, n \} and x=(x1,x2,…,xn),y=(y1,y2,…,yn)∈Tx=(x_1,x_2,\dots, x_n), y=(y_1, y_2, \dots, y_n) \in T. Show that n=23n=23 if TT has a subset SS satisfying
[*]∣S∣=2k|S|=2^k [*]For each x∈Tx \in T, there exists exacly one y∈Sy\in S such that d(x,y)≤3d(x,y)\leq 3
combinatorics proposedcombinatorics