0
$\begingroup$

let $n \in \mathbb{N}$. Is is possible to find a sequence $S = \{ s_1, \dots, s_{n+k} \}$ ($k \leq n$) with a polynomial algorithm, so that for every pair $(x,y) \in S \times S$, the products $x \cdot y$ are pariwise distinct? Also $s_i \in S$ should be polynomial bounded with respect to $n$.

Regards,

Kreschew

  • 1
    Need at least a small change, because if $(x,y)\in S\times S$ then $(y,x)\in S\times S$. Maybe additional condition $x \le y$?2011-08-18
  • 1
    Why talk about s_{n+k} and not s_{n}? I fail to see the role of k here.2011-08-18
  • 0
    Umm yeah, thank you, forgot about that ;). Should be $x < y$. So you have $0.5(n-1)n$ possible choices for pairs...2011-08-18
  • 1
    Crossposted on http://mathoverflow.net/questions/73167/sequence-with-a-special-property2011-08-21

2 Answers 2