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