[Yuhao Du Contest 7]Junk Problem

Difficulty Ratings

Idea Creativity: 4/5
Techniques Used: 3/5
Implementation : 2/5
By xudyh

Statement

Given $n \le 1e7$, find $s$ distinct integers $1 \le a_1,a_2, \cdots ,a_s \le n$ such that:
-For all pairs $(a_i,a_j)$ such that $i < j$, their XOR sum should be distinct.
-$s \ge \lfloor \sqrt{0.5n} \rfloor$

Solution

Well known in Poland
So obviously we pick the minimum valid $s$. As $s$ is $O( \sqrt{n})$, we would imagine splitting each integer into 2 parts, something like each integer is $u_i \times 2^q+v_i$ where $0 \le u_i,v_i \lt 2^q$, and all $u_i,v_i$ is distinct. Then we just have to guarentee that if $u_w \oplus u_x = u_y \oplus u_z$ then $v_w \oplus v_x \neq v_y \oplus v_z$. ( $\oplus$ is xor)

Let $q$ be the smallest integer such that $2^q \ge s$. Consider we create a function $f(x)=y$ that $0 \le x,y \lt 2^q$. Our final set will be $i \times 2^q + f(i)$ for all integers $i$ in $[0,s)$. It is easy to see that all integers generated is $\le N$. So now we will focus on the function.

Imagine that we write all integers in binary and view it as a polynomial. E.g $5$ -> $101_2$ -> $x^2 + 1$. Then, imagine after any operation, coefficents are adjusted modulo 2. E.g $5+3 = (x^2+1) + (x+1) = x^2+x+2 = x^2+x = 6$. You realise that addition suddenly became bitwise xor! Lets also add an additional rule: the resulting polynomial is done under modulo $P(x)$, where $P(x)$ is an special(?) polynomial of degree $q$. Eg: $q=3, P(x)=x^3+x+1$, $5 \times 7 = (x^2+1)(x^2+x+1) = (x^4+x^3+x^2+x^2+x+1) = x^2+x = 6$. So now we also invented multiplication. These rules are called arithmetic under the field $\mathbb{F_{2^q}}$. So the requirements of such $P(x)$ is that its irreducible under this field, because we will need to use bezout's theorem on it. Irredicible = not factorizable.

So now addition and multiplication is defined like the new rules, i want that if $w,x,y,z$ distinct and $w+x=y+z$ then $f(w)+f(x) \neq f(y)+f(z)$. Let $t=w+x$. That means we want $f(x)+f(t+x)=C$ to have two roots of $x$ (note that $t+x = t-x$ since the coefficents are modulo 2). So we want $f(x)+f(t+x)-c=0$ to be a quadratic equation. By the selection of $P(x)$ we guarenteed that under new rules, quadratic equation still only has two roots. Ultimately, we realize that if we let $f(x) = x^3+k$, $f(x)+f(t+x)-c = x^3 + t^3 + t^2x + tx^2 + x^3-c = (t)x^2 + (t^2)x + (t^3+c)$. As $w \neq x$, $t \neq 0$ and the equation would become quadratic.

Last thing is that as the elements have to be positive, $f(0)$ cannot be 0 so we should let $f(x) = x^3+1$ or just with any other constant term that is not $0$.