سؤال

Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ such that we always have $\pi(S) \ne \pi(S')$. For example, we can define $a_i = 2^i$. This function satisfies the property because for each $A \subseteq N$, $\pi(A)$ uniquely represents an integer written in base 2. However, in this function $a_i$ is bounded above by $\mathcal{O}(2^n)$. I am looking for a function such that $|a_i|$ and $\frac{1}{|a_i|}$ are bounded above by a polynomial. As an example that does not satisfy this last condition we can consider $a_i = 2^{i-n}$. It would be great to know different functions that satisfy this property. I will try to proof the uniqueness myself (if it is not so difficult!), so please let me know if you are aware of such functions.

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top