Please help me to construct an example of an injective map $F: \{0,1\}^{n} \to \mathbb{N}$ such that $$ |F(x_1,\ldots,x_n)-F(y_1,\ldots,y_n)| = \sum_{k=1}^{n} |x_k-y_k| $$ for all $x=(x_1,\ldots,x_n), \quad y=(y_1,\ldots,y_n) \quad (x_i, y_i =0 \,\,\text{or}\,\, 1)$.

Of course, there are $2^n$ such tuples and every such an $n$-tuple corresponds to a natural number.

  • $\begingroup$ $\mathbb{N}_0$ or $\mathbb{N}_+$? $\endgroup$ – orlp Jun 12 '18 at 8:33
  • $\begingroup$ $\mathbb{N}=\{0,1,2,\ldots\}$ or $\mathbb{N}=\{1,2,\ldots\}$ - it does not matter $\endgroup$ – monica_k Jun 12 '18 at 8:35
  • $\begingroup$ I think maybe Gray codes can help here. $\endgroup$ – monica_k Jun 12 '18 at 8:38

This is impossible. Consider $x$ to be a $n$-tuple with $n-1$ zeroes and a single $1$ in the $k$th position and $y = (0, \dots, 0)$.


$$|F(x_1, \dots, x_n) - F(0, \dots, 0)| = 1$$

This means that there are only two possible values for $F(x_1, \dots, x_n)$, namely $F(0, \dots, 0) \pm 1$.

But there are $n$ possible $x$ with the conditions above, meaning for $n > 2$ the mapping can't be injective.

  • $\begingroup$ Thank you very much! And what will be if one replace the above identity in the problem with the inequality $$ |F(x_1,\ldots,x_n)-F(y_1,\ldots,y_n)| \leq C \sum_{k=1}^{n} |x_k-y_k| $$ for some $C>0$ ? $\endgroup$ – monica_k Jun 12 '18 at 8:42
  • $\begingroup$ @monica_k Well by the same argument as above, $C$ can not be a constant irrespective of $n$, as it needs to be at least $n/2$. I don't know if that would be sufficient, but it would at least be necessary. $\endgroup$ – orlp Jun 12 '18 at 8:43
  • $\begingroup$ @monica_k As there are $n$ choices for $\mathbf x$ (for given $\mathbf y$) that leadt to $\sum=1$, you'll need $C\ge n/2$. However, there are $n\choose 2$ possibilities with $\sum=2$, so you need to pack ${n\choose 2}+n+1$ values into $2C+1$ allowed values, i.e., $C$ must be ate least $\sim n^2/4$. We could continue, or note directly that to cover all vectros, we need $2^n\le 2nC+1$ $\endgroup$ – Hagen von Eitzen Jun 12 '18 at 8:47
  • $\begingroup$ I'm sorry. Aren't there any positive examples for similar problems? I try the last attempt: What about an example of an injective map $F: B_{n,m} \to \mathbb{N}$ such that $$ |F(x_1,\ldots,x_n)-F(y_1,\ldots,y_n)| \leq C \sum_{k=1}^{n} |x_k-y_k| $$ for all $x,y\in B_{n,m}$ (for some $C>0$) ? Here $$ B_{n, m}=\{x=(x_1,\ldots,x_n)\in\{0,1\}^{n}: \,\, \sum_{k=1}^{n}x_k = m \}. $$ So, $B_{n, m}$ is the set of $n$-tuples of 0 and 1 with the fixed sum equal to $m$. ($m>1$ is the fixed natural number) $\endgroup$ – monica_k Jun 12 '18 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.