# Proof- set uniqueness

Moderator Note: This question is from a contest which ended 22 October 2012.

Suppose that for $1\leq y\leq x$, and $x\geq 3$,

$$\Gamma_{x,y}=\left\{\left\lfloor\frac{2^x-1}{2^{y-1}}n - 2^{x-y} +1\right\rfloor: n=1,2,3,\dots\right\}\;.$$

Then, for example, $$\Gamma_{3,3}= \left\{\left\lfloor\frac{7}{4}n\right\rfloor: n=1,2,3,\dots\right\}= \{1,3,5,\dots\}\;.$$

How is a proof that for any $x\geq 3$ each positive integer only appears in one set $\Gamma_{x,y}$?

-
Are $x$ and $y$ integers? (By the way, this question is probably not related to proof theory.) – Trevor Wilson Sep 8 '12 at 2:14

Note that

\begin{align*} \Gamma_{3,3}&=\left\{\left\lfloor\frac74n\right\rfloor:n\in\Bbb Z^+\right\}=\{1,3,5,7,8,10,12,14,15,\dots\}\overset{?}=\{1,3,5,7\}+7\Bbb Z^+\;,\\ \Gamma_{3,2}&=\left\{\left\lfloor\frac72n\right\rfloor-1:n\in\Bbb Z^+\right\}=\{2,6,9,13,16,\dots\}\overset{?}=\{2,6\}+7\Bbb Z^+\;,\text{ and}\\\\ \Gamma_{3,1}&=\{7n-3:n\in\Bbb Z^+\}=\{4,11,18,25,32,\dots\}\overset{?}=\{4\}+7\Bbb Z^+\;. \end{align*}

This suggests the conjecture that

\begin{align*} \Gamma_{x,y}&=\left\{\left\lfloor\frac{2^x-1}{2^{y-1}}n - 2^{x-y} +1\right\rfloor: n=1,2,3,\dots\right\}\\\\ &=B_{x,y}+(2^x-1)\Bbb Z^+\;, \end{align*}

where $$B_{x,y}=\big\{2^{x-y}+k2^{x-y+1}:k=0,\dots,2^{y-1}-1\big\}\;.$$

Note that $2^{x-y}+\left(2^{y-1}-1\right)2^{x-y+1}=2^x-2^{x-y+1}+2^{x-y}=2^x-2\cdot2^{x-y}+2^{x-y}=2^x-2^{x-y}$. Thus,

$$B_{x,y}+m(2^x-1)\subseteq\{1,\dots,2^x-1\}+m(2^x-1)$$

for each $m\in\Bbb N$.

Suppose for now that the conjecture is true and that $1\le y<z\le x$. It follows immediately from the preceding observation that $\Gamma_{x,y}\cap\Gamma_{x,z}\ne\varnothing$ iff $B_{x,y}\cap B_{x,z}\ne\varnothing$.

Let $a=x-y$ and $b=x-z$, and note that $a\ge b+1$. Then

$$B_{x,y}=\big\{2^a+k2^{a+1}:k=0,\dots,2^{y-1}-1\big\}\;,$$

and

$$B_{x,z}=\big\{2^b+k2^{b+1}:k=0,\dots,2^{z-1}-1\big\}\;.$$

Every member of $B_{x,y}$ is divisible by $2^a$ and hence by $2^{b+1}$, but every member of $B_{x,z}$ is congruent to $2^b$ mod $2^{b+1}$, so $B_{x,y}\cap B_{x,z}\ne\varnothing$, and hence $\Gamma_{x,y}\cap\Gamma_{x,z}\ne\varnothing$.

It’s also pretty easy to see that $\bigcup_{1\le y\le x}B_{x,y}=\{1,\dots,2^x-1\}$, from which it follows immediately that $\bigcup_{1\le y\le x}\Gamma_{x,y}=\Bbb Z^+$: $B_{x,y}$ is the set of $k\in\{1,\dots,2^x-1\}$ such that $2^{x-y}$ is the highest power of $2$ dividing $k$, and $x-y$ ranges from $0$ to $x-1$ inclusive. Thus, it remains only to prove the conjecture, which we can now restate as follows:

For every $m\in\Bbb Z^+$ the following are equivalent:

1. $m\in\Gamma_{x,y}$;
2. $m=\left\lfloor\dfrac{2^x-1}{2^{y-1}}n - 2^{x-y} +1\right\rfloor$ for some $n\in\Bbb Z^+$;
3. $m\bmod(2^x-1)\in B_{x,y}$;
4. the highest power of $2$ dividing $m\bmod(2^x-1)$ is $2^{x-y}$.

Of course we already know that (1) and (2) are equivalent, as are (3) and (4). Thus, it suffices to show the equivalence of (2) and (4).

Let $M=2^x-1$ and $a=x-y$, and suppose that $n=2^{y-1}q+r$, where $0\le r<2^{y-1}$. Let $$m=\left\lfloor\frac{2^x-1}{2^{y-1}}n-2^{x-y}+1\right\rfloor=\left\lfloor\frac{Mn}{2^{y-1}}\right\rfloor-2^a+1\;,$$ and let $m_0=m\bmod M$. Then

\begin{align*} m&=\left\lfloor\frac{Mn}{2^{y-1}}\right\rfloor-2^a+1\\ &=\left\lfloor\frac{M(2^{y-1}q+r)}{2^{y-1}}\right\rfloor-2^a+1\\ &=\left\lfloor Mq+\frac{Mr}{2^{y-1}}\right\rfloor-2^a+1\\ &=\left\lfloor\frac{Mr}{2^{y-1}}\right\rfloor+Mq-2^a+1\\ &=Mq-2^a+1+\left\lfloor\frac{(2^x-1)r}{2^{y-1}}\right\rfloor\\ &=Mq-2^a+1+\left\lfloor2^{a+1}r-\frac{r}{2^{y-1}}\right\rfloor\\\\ &=Mq-2^a+1+\begin{cases}0,&\text{if }r=0\\2^{a+1}r-1,&\text{otherwise}\end{cases}\\\\ &=\begin{cases} M(q-1)+2^x-2^a,&\text{if }r=0\\ Mq+2^{a+1}r-2^a,&\text{if }0<r<2^{y-1}\;. \end{cases} \end{align*}

Clearly $0\le 2^x-2^a<M$, and $0\le 2^{a+1}r-2^a<2^x-2^a\le M$, so

$$m_0=\begin{cases}2^x-2^a=2^a(2^y-1),&\text{if }r=0\\ 2^{a+1}r-2^a=2^a(2r-1),&\text{if }0<r<2^{y-1}\;,\end{cases}$$

and $2^a$ is indeed the highest power of $2$ dividing $m_0$, and we’ve shown that (2) implies (4).

To show that (4) implies (2), it suffices to show that $B_{x,y}\subseteq\Gamma_{x,y}$. In other words, we want to show that for each $k\in\{0,\dots,2^{y-1}-1\}$ there is a positive integer $n_k$ such that

$$2^a+2^{a+1}k=\left\lfloor\dfrac{2^x-1}{2^{y-1}}n_k-2^a+1\right\rfloor=\left\lfloor\frac{2^x-1}{2^{y-1}}n_k\right\rfloor-2^a+1$$

or, equivalently, such that

\begin{align*} 2^{a+1}(k+1)&=\left\lfloor\dfrac{2^x-1}{2^{y-1}}n_k\right\rfloor+1\\ &=2^{a+1}n_k+\left\lfloor-\frac{n_k}{2^{y-1}}\right\rfloor+1\\ &=2^{a+1}n_k-\left\lceil\frac{n_k}{2^{y-1}}\right\rceil+1\;. \end{align*}

Set $n_k=k+1$; then $1\le n_k\le 2^{y-1}$, so $\left\lceil\dfrac{n_k}{2^{y-1}}\right\rceil=1$, and

$$2^{a+1}n_k-\left\lceil\frac{n_k}{2^{y-1}}\right\rceil+1=2^{a+1}(k+1)\;,$$

as desired. This completes the proof.

-