Let $S = \{0,1,2,...,2^{2010}-1\}$ and $T=\{0,1,2,...,2^{2000}-1\}$. Does there exist a function $f(x)$ that
maps $S\rightarrow T$,
is onto
has the property that if $a,b\in S$are written in binary and leading zeroes are placed until the $2^{2009}$th place, then if $10$ consecutive binary digits are the same in the corresponding digits place, $f(a)\neq f(b)$.
For example, if $a=10101011010_2$ and $b=10101011011_2$, then $f(a)\neq f(b)$. However if $a=10101011010$ and $b = 11010101101$, it doesn't immediately follow from the third property.
If there doesn't exist such a function, what is the least $k$ where $S=\{0,1,2,...,2^{k}-1\}$ such that there will exist a function?
I have been stuck on this problem for a while and I've tried things, but haven't managed to find an explicit construction. Any help?
OK, I got it. The answer is yes, there is such a function.
Proof:
I'll prove (by induction on $n$) that for any $k$ and $n$:
The set $S$ of all $2^{k+n}$ binary strings of length $k+n$ can be partitioned into $2^n$ sets $S_1,S_2, ... S_{2^n}$ with $2^k$ elements each such that for any $1 \leq i \leq 2^n$, no 2 strings in $S_i$ have the same $k$ consecutive digits in the same (corresponding digit) place. (Note that with $k=10$ and $n=2000$, this is just another way of phrasing your problem)
OK, so take any $k$, and we'll prove the claim by induction on $n$:
Base: $n = 0$. The partition contains just 1 element, which is the very set S, which has $2^k$ different binary strings of length $k$, so indeed no two strings from S will have $k$ consecutive digits in the same place.
Step: Inductive Hypothesis: The claim is true for $n$. Now let's show it is also true for $n+1$:
Since by the inductive Hypothesis the claim is true for $n$, we know that there is a partition of all $2^{k+n}$ binary strings of length $k+n$ into $2^n$ sets $S_1,S_2, ... S_{2^n}$ with $2^k$ elements each such that for any $1 \leq i \leq 2^n$, no 2 strings in $S_i$ have the same $k$ consecutive digits in the same place. Take this partition, and focus on $S_i$ for any $1 \leq i \leq 2^n$. Since there are no 2 strings in $S_i$ with $k$ consecutive digits in the same place, there are also no 2 strings in $S_i$ ending with the same $k$ consecutive digits. This means that if we focus on the last $k$ digits of all strings in $S_i$, we find that all $2^k$ binary strings of length $k$ are covered by the $2^k$ strings in $S_i$. That means that we can split $S_i$ into two equal sets $S_{i1}$ and $S_{i2}$ (who have $2^{k-1}$ elements each) such that for any $2^{k-1}$ binary string of length $k-1$ there is a string in $S_{i1}$ that ends with that string, and the same goes for $S_{i2}$.
Then, make two copies of $S_{i1}$, and paste a $0$ at the end of all strings in the one copy (call this $S_{i1a}$), and paste a $1$ at the end of each string in the other (call this $S_{i1b}$). Note that these two sets have all different binary strings, since they all differed with respect to the last $k-1$ digits before adding the $0$ or $1$. Do the same for $S_{i2}$ to obtain $S_{i2a}$ and $S_{i2b}$. Note that at this point we have 4 sets of $2^{k+n-1}$ binary strings of length $k+n+1$ whose last $k$ digits are all different, since the strings in $S_{i1}$ were already all different from those in $S_{i2}$, and we just saw that $S_{i1a}$ and $S_{i1b}$ are all different, so $S_{i2a}$ and $S_{i2b}$ have no overlap as well. Now combine combine $S_{i1a}$ and $S_{i2b}$ to obtain $S_{ia}$, and combine $S_{i1b}$ and $S_{i2a}$ to obtain $S_{ib}$. Notice that in doing so, $S_{ia}$ contains $2^{k+n}$ binary strings whose last $k$ digits are all different, and the same goes for $S_{ib}$.
Repeating this process for all $S_i$ (where we obtain a $S_{ia}$ set and a $S_{ib}$ set), we obtain $2^{n+1}$ sets of binary strings of length $k+n+1$. These are all different, since the strings in any $S_i$ were already all different from the strings in $S_j$ where $i \neq j$, and we already saw that the resulting pair of sets $S_{ia}$ and $S_{ib}$ for any $i$ have no overlap as well. Hence, these $2^{n+1}$ sets form a partition of all possible binary strings of length $n+k+1$. More importantly, the sets in the original partition did no contain strings with $k$ consecutive digits in the same place, and the way we constructed the new partition guarantees that the sets in there have that property as well. This completes the inductive step.
OK, that's pretty abstract, so here is an example to see how this goes:
Example: say $k=2$ and $n=1$. We have a partition like this:
$S_1 = \{000,010,101,111\}$ (note how all two digit strings are covered by last two digits of strings) $S_2 = \{001,011,100,110\}$
We can split $S_1$ into $S_{11} = \{000,101\}$ and $S_{12} = \{010,111\}$ (both sets cover all 1-digit strings with last digits)
Now create a new set by pasting a $0$ at the end of each string of $S_{11}$, and create a second new set by pasting a $1$ to all strings, i.e. from $S_{11} = \{000,101\}$ we obtain $S_{11a} = \{0000,1010\}$ and $S_{11b} = \{0001,1011\}$. Similarly, from $S_{12} = \{010,111\}$ we obtain $S_{12a} = \{0100,1110\}$ and $S_{12b} = \{0101,1111\}$. Now combine $S_{11a}$ and $S_{12b}$ to obtain $S_{1a} = \{0000,1010,0101,1111\}$, and combine $S_{11b}$ and $S_{12a}$ to obtain $S_{1b} = \{0001,1011,0100,1110\}$.
Through a similar process on $S_2 = \{001,011,100,110\}$ we obtain $S_{2a} = \{0010,1000,0111,1101\}$ and $S_{2b} = \{0011,1001,0110,1100\}$.
And now note that $\{S_{1a},S_{1b},S_{2a},S_{2b}\}$ is a partition of all $2^{2+2} = 16$ binary strings so that no set in this partition contains 2 strings with the same $k=2$ in the same place.