Pouring water from bottles

There are three buckets of size $x_1, x_2$, and $x_3$ liters (positive, but not necessarily integers), and some bottles, possibly of different sizes, containing a total of $x_1+x_2+x_3$ liters of water. We want to pour water from the bottles into the buckets. A bottle is split if it is poured into more than one bucket. Is it true that for any $x_1,x_2,x_3$, there are bottle sizes such that we need to split two bottles?

By pouring water into the first bucket until it is full, then second bucket, and third, we will never need to split more than two bottles.

For the case $(x_1,x_2,x_3)=(1,3,6)$, @WhatsUp's example with three bottles of capacity $10/3$ shows that we do need to split two bottles (that is, splitting one bottle does not suffice).

Solution 1:

This proof uses the same basic idea of having $N$ bottles with $\frac1N$ of the volume as @mathworker21’s proof and merely provides a more elementary proof of the existence of suitable fractional parts that doesn’t require ergodic theory or linear independence over $\mathbb Q$.

Without loss of generality, rescale the bucket sizes so that $x_1+x_2+x_3=1$. Consider $N$ bottles with volume $\frac1N$ each. The fractional parts of $Nx_i$ can add up to $0$, $1$ or $2$. If we can choose $N$ such that they add up to $2$, it will be necessary to split $2$ bottles (since one bottle can only fill fractional parts that add up to $1$). They add up to $2$ if and only if two of them add up to more than $1$. So we want to show that e.g. $(\{Nx_1\},\{Nx_2\})$ lies in the upper right half of $[0,1]^2$ for some $N$. It would be slightly surprising if it required advanced concepts to show that we can hit an entire half of the square.

If all $x_i$ are rational with common denominator $d$, choose $N=d-1$. Since $\{dx_i\}=0$, we have $\{Nx_i\}=\{dx_i-x_i\}=\{-x_i\}=1-x_i$, and thus $\sum_i\{Nx_i\}=3-\sum_ix_i=2$.

Else, at least two of the $x_i$ must be irrational; assume without loss of generality that $x_1$ and $x_2$ are and that $x_1\lt x_2$. If $x_2\lt\frac12$, some multiple $kx_2$ lies in $\left[\frac12,1\right]$, and either $\sum_i\{k x_i\}=2$ and we are done, or $\sum_i\{k x_i\}=1$ and we can replace the $x_i$ by $\{k x_i\}$; so we can assume $x_2\gt\frac12$.

Since $x_1+x_2\lt1$, by Dirichlet’s approximation theorem (which can be proved by an elementary application of the pigeonhole principle), there is $M\in\mathbb N$ such that $\{M x_1\}\gt x_1+x_2$ and thus $\{(M-1)x_1\}\gt x_2$. At least one of $\{Mx_2\}$ and $\{(M-1)x_2\}$ is at least $1-x_2$. (This is where $x_2\gt\frac12$ is needed.) Thus, for at least one of $N=M$ and $N=M-1$ we have $\{Nx_1\}+\{Nx_2\}\gt x_2+1-x_2=1$.

Solution 2:

Yes. Take $N$ as in Lemma $1$ with $\alpha = \frac{x_1}{x_1+x_2+x_3}$ and $\beta = \frac{x_2}{x_1+x_2+x_3}$. Let $b_1,\dots,b_N = \frac{x_1+x_2+x_3}{N}$. Suppose we could only split one bottle, giving $\delta_1,\delta_2$ of it to the buckets with $x_1,x_2$ liters (initially), respectively and possibly some to bucket $x_3$. Then there are $m_1,m_2 \in \mathbb{N}$ with $m_1\frac{x_1+x_2+x_3}{N} = x_1-\delta_1$ and $m_2\frac{x_1+x_2+x_3}{N} = x_2-\delta_2$. Then $\frac{Nx_1}{x_1+x_2+x_3} = m_1+\frac{N\delta_1}{x_1+x_2+x_3}$ and $\frac{Nx_2}{x_1+x_2+x_3} = m_2+\frac{N\delta_2}{x_1+x_2+x_3}$. Since $\delta_1,\delta_2 < \frac{x_1+x_2+x_3}{N}$ (if one of them were equal to $\frac{x_1+x_2+x_3}{N}$, then one of $\{\frac{Nx_1}{x_1+x_2+x_3}\},\{\frac{Nx_2}{x_1+x_2+x_3}\}$ would be $0$, contradicting that their sum is more than $1$), we see $\frac{N\delta_1}{x_1+x_2+x_3}+\frac{N\delta_2}{x_1+x_2+x_3} = \{\frac{Nx_1}{x_1+x_2+x_3}\}+\{\frac{Nx_2}{x_1+x_2+x_3}\} > 1$, meaning $\delta_1+\delta_2 > \frac{x_1+x_2+x_3}{N}$, a contradiction to having split a bottle properly.

.

Lemma 1: Given any $\alpha,\beta > 0$ with $\alpha+\beta < 1$, there is some $N \in \mathbb{N}$ with $\{\alpha N\}+\{\beta N\} > 1$.

Proof: If $\alpha,\beta$ are $\mathbb{Q}$-linearly independent, then $\{(\{\alpha N\},\{\beta N\}) : N \ge 1\}$ is dense in $\mathbb{T}^2$, so clearly a desired $N$ exists. Otherwise, $\beta = \frac{c}{d}\alpha+\frac{p}{q}$ for some $c,d,p,q \in \mathbb{Z}^{\ge 0}$. Then $\{\alpha N\}+\{\beta N\} = \{\alpha N\}+\{\alpha\frac{c}{d} N+\frac{Np}{q}\}$. First suppose $\alpha$ is irrational. Then since $\{\{\alpha N'dq\} : N' \ge 1\}$ is dense in $\mathbb{T}$, we get a desired $N$ by taking $N = N'dq$ with $\{\alpha N'dq\} > 1-\frac{1}{c^2d^2}$, since then $\alpha cqN' = \frac{(k+1)c}{d}-\frac{c}{d}\epsilon$ for some $k \in \mathbb{Z}$ and $0 < \epsilon < \frac{1}{c^2d^2}$, meaning $\{\alpha cqN'\}$ is either at least $1-\frac{c}{d}\epsilon$ or at least $\frac{1}{d}-\frac{c}{d}\epsilon$, both large enough. Now suppose $\alpha = \frac{m}{n}$ is rational, with $\gcd(m,n) = 1$. Then write $\frac{m}{n}\frac{c}{d}+\frac{p}{q} = \frac{m'}{n'}$ with $\gcd(m',n') = 1$. We wish to show $\{\frac{m}{n}N\}+\{\frac{m'}{n'}N\} > 1$ for some $N \in \mathbb{N}$. WLOG suppose $n \ge n'$. We can take $N$ so that $Nm \equiv -1 \pmod{n}$ and $n' \nmid N$; indeed, if $n' \mid n$, then clearly $Nm \equiv -1 \pmod{n'}$ as well, and otherwise, $N = kn+m^*$ for an appropriate $k$ works, where $m^*m \equiv -1 \pmod{n}$. For this $N$, we have $\{\frac{m}{n}N\}+\{\frac{m'}{n'}N\} \ge \frac{n-1}{n}+\frac{1}{n'} \ge 1$, with equality only if $n' = n$ and $mN \equiv -1 \pmod{n}$ and $m'N \equiv 1 \pmod{n}$. But if we had equality, then $(m+m')N \equiv 0 \pmod{n}$, meaning $\alpha+\beta = \frac{m}{n}+\frac{m'}{n} = 1$, which is false.

.

Fact: If $\alpha,\beta$ are $\mathbb{Q}$-linearly independent, then $\{(\{\alpha N\},\{\beta N\}) : N \ge 1\}$ is dense in $\mathbb{T}^2$.

Proof: Define $T: \mathbb{T}^2 \to \mathbb{T}^2$ by $T(x,y) = (x+\alpha,y+\beta)$. It suffices to show that $T$ is ergodic w.r.t. the Lebesgue measure. Suppose $f \in L^2(\mathbb{T}^2)$ is $T$-invariant. By basic fourier analysis, $f(x_1,x_2) = \sum_{k_1,k_2 \in \mathbb{Z}} c_{k_1,k_2}e^{2\pi i (k_1x_1+k_2x_2)}$. Then $\sum_{k_1,k_2} c_{k_1,k_2} e^{2\pi i (k_1x_1+k_2x_2)} = f(x_1,x_2) = f\circ T(x_1,x_2)= \sum_{k_1,k_2} c_{k_1,k_2} e^{2\pi i (k_1(x_1+\alpha)+k_2(x_2+\beta))} = \sum_{k_1,k_2} e^{2\pi i(k_1\alpha+k_2\beta)}c_{k_1,k_2}e^{2\pi i (k_1x_1+k_2x_2)}$ Therefore, $c_{k_1,k_2} = c_{k_1,k_2}e^{2\pi i (k_1\alpha+k_2\beta)}$ for each $k_1,k_2 \in \mathbb{Z}$. Since $\alpha,\beta$ are $\mathbb{Q}$-linearly independent, we have $c_{k_1,k_2} = 0$ for all $(k_1,k_2) \not = (0,0)$. It follows that $f$ is a.e. constant, as desired.