2
$\begingroup$

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

  • 0
    Are $x$ and $y$ integers? (By the way, this question is probably not related to proof theory.)2012-09-08

1 Answers 1

1

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

Clearly $0\le 2^x-2^a, 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

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.