Mysterious Riddle-Giving Wizards Hate Him!

Consider a permutation of the positive integers up to $n$. This permutation is streamed one item ($x_i$) at a time to an observer (you!). After observing an item, you must make two choices. First, choose whether to add $x_i$ to a working set ($D$) or discard $x_i$. Second, choose whether to observe an additional value or stop observing subsequent items.

Once you’ve stopped the stream, a (non-adversarial) wizard chooses an integer $\omega$ on $[1, n)$. Your goal is to find some $D_\omega \subseteq D$ such that $\sum_{D_\omega} d_i \ \operatorname{mod} \ n = \omega$. A good algorithm should:

• Succeed at choosing $D$ such that $D_\omega$ exists $\textit{w.h.p}$
• Use little memory while storing $D$.

Clearly, we could view the entire stream, store all items so that $\lvert D \rvert$ = $n$, and succeed all the time because $\omega \in D$. Can we do better though?

I propose that we include the first $z=\log_{2}\big(n\ln\big(n))$ items in $D$. The $2^{z}$ subsets of $D$ have sums that aren’t uniformly distributed, but when $\operatorname{mod} n$ is applied this distribution becomes near uniform on $\big[1, n)$. If this distribution is in-fact uniform, then we have a success probability of $1 - e^{-2^z/n} \approx 1 - 1/n$.

$\textbf{Ahem, Source?}$ — This result re: $\operatorname{mod} n$ comes from Sampling Correctors: Section 8.1. To be quite honest, I think the exact problem (i.e. sum must be $\omega$ instead of $kn + \omega$ with $k \in \mathbb{N}_0$) is more interesting, but I liked that fact so we shoehorn it in. This post was inspired by $\textbf{Proposition 3.19}$ of Jay Cummings’ $\underline{Proofs}$. In that problem, we see (via. pigeonhole principle) that for any subset of size $z \geq \log_2\big(n)$ there is at least one positive integer $\omega \leq n$ that can be constructed by at least two subsets of $z$.