The Soup Problem: how to asymptotically fairly split a geometric series and a constant one using a single pattern?

Question

Literally every time I'm serving some soup I'm thinking of this little mathematical problem I devised.

Imagine you have a very large (= infinite, for the purposes of the actual problem) bowl of soup and want to divide it into two halves using a (finite) ladle. The trouble is that some of the good stuff floated to the surface and every scoop takes a part $p$ of it, $p < \frac12$ (so its amount goes down geometrically with a quotient of $1-p$). The other good stuff is evenly dissolved in the volume. The protocol is that you always take a full scoop in this manner, so the only freedom is in what order do you empty the ladle into $A$ or $B$'s plate. What order would you take so that, asymptotically, both parties get fair shares in both respects?

Obviously the answer can't be $ABABAB\ldots$, because $A$ would always get $1/(1-p)$-times more than $B$. $\overline{ABBA}$ does not work either because $1+(1-p)^{-3}$ is always greater than $(1-p)+(1-p)^2$. In fact (except for a countable number of special values of $p$ (*)) it can't be any periodic infinite word of $A$ and $B$ for a slight variant of the same reason. One more thing I found is that the greedy algorithm (go $A$ until it has more than $B$, then swap) won't work either because while it would always satisfy splitting of the geometrical part, it would break the linear one (number of scoops). That's all I know at the moment.

Rephrased: for a given $1-p =: q \in (\frac12, 1)$, find a subset $M ∈ \mathbb{N}$ such that both

• $\displaystyle\lim_{N→∞} \frac{\#\left( M \cap \{1,\ldots,N\} \right)}{N} = \frac12$,
• $\displaystyle\sum_{n=1}^∞ q^n \chi_M(n) = \frac12 \sum_{n=1}^∞ q^n$.

I'm pretty sure the answer will lie somewhere in the theory of non-integer base systems or combinatorics on words or both, but I know little of those.

---

(*) For example, for $q = φ - 1$ the equality $q + q^2 + q^3 = 1 + q^4 + q^5$ holds, so for $p = 2 - φ \approx 0.381966$ the sequence $\overline{ABBBAA}$ would work.

Answer 1

Proposition. Let $(a_n)$ be an absolutely convergent series of real numbers such that for any natural $k$ we have $$|a_{2k-1}-a_{2k}|\le \sum_{n=k+1}^\infty |a_{2n-1}-a_{2n}|.\label{1}\tag{1}$$ Then there exists a subset $M$ of natural numbers such that $|M\cap \{2k-1,2k\}|=1$ for each natural $k$ and $\sum_{n\in M} a_n=\tfrac 12\sum_{n=1}^\infty a_n$.

Proof. For each natural $k$ put $b_k=|a_{2k-1}-a_{2k}|$. It suffices to show that we can consecutively choose signs for $b_k$, providing $\sum_{k=1}^\infty \pm b_k=0$. At the beginning choose a sign “$+$” for $b_1$ and for each $k>1$ choose for $b_k$ a sign “$+$”, if $\sum_{i=1}^{k-1} \pm b_i\ge 0$ and “$-$”, otherwise. It is easy to check that Condition \eqref{1} provides $\sum_{k=1}^\infty \pm b_k=0$. $\square$

Corollary. For each $q\in (1/\sqrt{2},1)$ there exists a subset $M$ of natural numbers such that $|M\cap \{2k-1,2k\}|=1$ for each natural $k$ and $\sum_{n\in M} q^n=\tfrac 12\sum_{n=1}^\infty q^n$.

Proof. It suffices to check that for any any natural $k$ we have $$q^{2k-1}-q^{2k}\le \sum_{n=k+1}^\infty q^{2n-1}-q^{2n}=\frac{q^{2k+1}}{1+q}. \square$$

Answer 2

Let $\{a_i\}$ be a G.P. with ratio $r\ge \frac{1}{2}$and sum $S$. Then, for any number $T$ in $(0,S]$ there is a subsequence $\{b_i\}$ of $\{a_i\}$ with sum $T$.

Proof. Let $b_1=a_m$ where $m$ is minimal such that $a_m\le T$. Then $$T<a_{m-1}=\frac{a_m}{r}\le \frac{a_m}{1-r}=a_m+\frac{a_{m+1}}{1-r}.$$ Therefore the initial conditions are reproduced for $T-a_m$ and $\{a_i\}_{i>m}$ and we can now successively choose $b_2, b_3,...$

Soup for $q\ge \frac{1}{\sqrt2}$

Let $r=q^2$. From the above result we can choose a set $I$ of positive integers such that $$\sum {{q^{2i}}_{i\in I}}= \frac{1}{2(1-q^2)}.$$

Then, for the sequence of As and Bs, place the As in positions $2i-1$ if $i\in I$ and in position $2i$ otherwise.

The absolute differences between the amount of 'good' given to A and B in successive pairs are then proportional to $1,q^2,q^4, ...$ and, by the definition of $I$, the total signed difference is zero.

Answer 3

I wrote a short paper devoted to your problem.

Solving it, I introduced the following notion, considered in a separate question. A number $q\in (1/2, 1)$ is approximating, if there exist non-negative numbers $A$ and $N$ such that for each $x_0\in [0,A]$ there exist $n\le N$ and a polynomial $P(x)$ of the form $\sum_{i=1}^n \pm x^i$ such that $P(1)=0$ and $|x_0-P(q)|\le Aq^n$.

Proposition. For each approximating number $q$ there exists a subset $M$ of natural numbers such that $\lim_{N\to\infty} |M \cap \{1,\ldots, N\} |/N = 1/2$, and $\sum_{n\in M} q^n=\tfrac 12\sum_{n=1}^\infty q^n$.

Proof. Let the number $q$ is approximating with the constants $A$ and $N$. Put $k_0=0$. Then we can inductively build an increasing sequence $(k_n)$ of natural numbers such that $k_{n+1}-k_n\le N$ for each $n$, assigning signs to numbers $q^i$ for $k_{n-1}<i\le k_n$ (a half of the assigned signs are “$+$” and the other half are “$-$”) assuring $\sum_{i=1}^{k_n} \pm q^i\le Aq^{k_n}$. Let $M$ be the set of natural $n$ such that $q^n$ has “$+$” sign. $\square$

In the paper is shown that each $q\in (q_\infty,1)$ is approximating, where $q_\infty=0.5845751\dots$ is a unique positive root of a polynomial $Q_\infty(x)=x^4+x^3+2x^2-1$.

Answer 4

There is an uncountable set of $q\in (1/2,1)$ for which there are only two sets $M$ (which are complements of each other) such that $\sum_{m\in M}q^m=\frac{1}2\cdot \frac{1}{1-q}$ - and uncountably many of these forced sets are not of asymptotic density $1/2$.

To prove this, let us define, for any subset $M$ of the natural numbers, the summing function $$f_M(q)=\frac{\sum_{m\in M}q^m}{\sum_{n\in\mathbb N}q^n}=(1-q)\cdot \sum_{m\in M}q^m$$ Note that for any $M$, the function $f_M$ is continuous where $|q|<1$ - and, in fact, the family of such functions is equicontinuous on this range.

Let's also define the left shift operator $$L(M)=\{m' \in \mathbb N : m'+1\in M\}$$ and note that $$f_{M}(q) = (1-q)\cdot \chi_{M}(0) + qf_{L(M)}(q)$$ where $\chi_M$ is the indicator function of $M$.

Let's say a set $M$ has $n$-bounded runs if there are no values $k$ such that $k\in M$ but $k+1,k+2,\ldots,k+n$ are all not in $M$ or such that $k\not\in M$ and the following $n$ integers are all in $M$.

We can now state a lemma:

Lemma: For any $n$, there is some $\varepsilon > 0$ such that if $M$ has $n$-bounded runs, then for all $q\in[1/2,1/2+\varepsilon)$ and all $M'\subseteq \mathbb N$ we have $f_M(q)=f_{M'}(q)$ implies $M=M'$.

Proof. First, we need to choose $\varepsilon$ so that $\left|f_{M}(q) - \frac{1}2\right| > \varepsilon$ for all sets $M$ with $n$-bounded runs and all $q\in [1/2,1/2+\varepsilon)$ - this is possible since $|f_M(1/2)-\frac{1}2|$ can never be less than $\frac{1}{2^{n+1}}$ for such a set, considering binary representations, and the family of functions $f$ is equicontinuous, so the values $|f_M(q)-\frac{1}2|$ must remain bounded away from zero for all $q$ close enough to $\frac{1}2$ - which allows us to choose a $\varepsilon$ satisfying our condition. Note that this, more helpfully, ensures that $f_{M}(q)$ cannot ever be in $[1-q, q]$.

One can now fix any $M$ with $n$-bounded runs and any $M'$ with $f_M(q)=f_{M'}(q)$ for some $q\in [1/2,1/2+\varepsilon)$ and prove inductively that $M=M'$. Consider the equation: $$f_M(q)=f_{M'}(q)$$ $$(1-q)\chi_{M}(0)+qf_{L(M)}(q) = (1-q)\chi_{M'}(0)+qf_{L(M')}(q)$$ Note, however, that this expression is either less than $1-q$ (in which case it must be that $\chi_{M}(0)=\chi_{M'}(0)=0$) or greater than $q$ (in which case it must be that $\chi_{M}(0)=\chi_{M'}(0)=1$) by choice of $\varepsilon$. Thus, $0$ is either in both or neither of the sets. However, this also immediately then simplifies as: $$f_{L(M)}(q)=f_{L(M')}(q)$$ which then allows us to repeat this argument inductively to see that $M=M'$, proving the lemma.

Then we finish with another lemma:

Lemma 2: Let $M$ be a non-empty set with $\ell$-bounded runs such that $0\not\in M$. Define $M_n = \{0\} \cup (M + n + 1)$ to be a right shift of $M$ with an initial element appended. For all large enough $n$, there exists some $q\in [1/2,1]$ such that if $f_{M'}(q)=1/2$ and $0\in M'$, then $M'=M_n$.

Proof. Note that $L(M_n)$ is always a set with $\ell$-bounded runs since the initial large run of elements not in the set is not preceded by an element that is in our set, as our definition would require - and all other runs must be in $M$ itself. Moreover, note $$f_{M_n}(q)=(1-q) + q^{n+1}f_{M}(q).$$ Note, in particular, that $f_{M_n}(1/2)\geq \frac{1}2$ and that if $q^{n+1} \leq q - \frac{1}2$, then $f_{M_n}(q)\leq \frac{1}2$ - and note that, for any $\varepsilon>0$ there is some large enough $n$ so that this is true of some $q$ in $(1/2,1/2+\varepsilon)$. In particular, suppose we choose some $\varepsilon$ so that Lemma 1 applies to sets with $\ell$-bounded runs with that $\varepsilon$ and choose $n$ big enough so that $q_0^{n+1}\leq q_0 - \frac{1}2$ for some $q_0\in (1/2,1/2+\varepsilon)$. Then, by the intermediate value theorem, there has to be some $q\in [1/2,q_0]$ such that $f_{M_n}(q) = \frac{1}2$.

However, if we let $M'$ be such that $f_{M'}(q)=\frac{1}2$ and $0\in M'$, we can then realize that $$f_{L(M')}(q) = f_{L(M_n)}(q)$$ and apply Lemma 1 to see that $L(M')=L(M_n)$, which then, since both $M'$ and $M_n$ contain zero, implies that $M'=M_n$, completing Lemma 2.

To then reach our end goal: fix any pair $(q,M)$ with the property from Lemma 2 that if for any $M'$ with $0\in M'$ we have $f_{M'}(q)=\frac{1}2$ implies $M=M'$. Note that if we had some arbitrary set $M''$ with $f_{M''}(q)=\frac{1}2$, we would also have that $f(\mathbb N\setminus M'')=\frac{1}2$ - and either $M''$ or its complement must contain $0$ - thus must equal $M$.

Together, this gives us a method to construct a $q$ for which fairly splitting soup is impossible from any set with bounded runs but not with asymptotic density $1/2$. This gives an uncountable set of $q$ for which fairly splitting soup is not possible. Note that if you choose the set $M$ to be have a periodic pattern, the produced counterexamples will be algebraic.