Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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}$?

share|cite|improve this question
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
up vote 1 down vote accepted

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,


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




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


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


as desired. This completes the proof.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.