Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
    
29 percent accept rate? –  Gerry Myerson Sep 8 '12 at 3:04

1 Answer 1

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,

$$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.

share|improve this answer

Your Answer

 
discard

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.