Secondary Special Camp 2011: NT P 4

[Moon]

Problem 4: Determine all the positive integers $n \geq 3$, such that $2^{2000}$ is divisible by \[
1+\binom{n}{1}+\binom{n}{2}+\binom{n}{3}\]

[Masum]

I think this problem should be posed for higher secondary level. This is a problem from $\text{1998 Chinese National Olympiad}$.
However, here is a solution.

$\text{Solution}$ :
Obviously $n\ge3$
Since $2$ is a prime, we need $1+\binom{n}{1}+\binom{n}{2}+\binom{n}{3}=2^k$ for some $k\in\mathbb{N},k\le2000$.
Note that $1+\binom{n}{1}+\binom{n}{2}+\binom{n}{3}=\frac{(n+1)(n^2-n+6)}{6}$
So, $(n+1)(n^2-n+6)=3\cdot2^{k+1}$
We have two cases:
$\#1$. $n+1$ is a power of $2$ i.e. $n+1=2^r$.
Because $n+1\ge4,r\ge2$. We get
$\ \ \ 2^{2r}-2^{r+1}+1-2^r+1+6=3\cdot2^s$ where $s=k+1-r$.
$\Longrightarrow 2^{2r}-3\cdot2^r+8=3\cdot2^{s}$
If $r\ge4$, $3\cdot2^s\equiv8\pmod{16}\Longrightarrow s=3$
But then $2^r(2^r-3)=16\Longrightarrow 2^r-3=1,r=2$ which is not a solution.
So, $r=2,3$ which gives the solution $n=7,3$
$\#2$. $n+1=3\cdot2^a$ for some $a\in\mathbb{N}$
Now, $a\ge1$ and $9\cdot2^{2a}-9\cdot2^a+8=2^t$ for some $t$
Then if $a>3$, $9\cdot2^{2a}-9\cdot2^a+8=2^3(9\cdot2^{2a-3}-9\cdot2^{a-3}+1)$ would have an odd factor namely $9\cdot2^{2a-3}-9\cdot2^{a-3}+1$.
But obviously $a\neq1,2$ which gives $a=3,n=23$.

[mutasimmim]

Masum vai, haven't you missed the case when $(n+1)$ is a power of $2$ but $(n^2-n+6)$ is divisible by $3$?

[mutasimmim]

My solution sketch( a lot like the previous one):
After simplifying we get $(n+1)(n^2-n+6) \mid 3.2^{2001}$. Thus we have three cases:

Case 1:Both $(n+1)$ and $(n^2-n+6)$ are powers of $2$.
In this case, letting $n=2^u-1$, we have $2^{2u}-3.2^u+8-=2^v$. Quick checking for $u=0,1,2,3$ and $v=0,1,2,3$ yields no solution. So we must have both $u,v$ greater than $3$,

but then all terms of the equation except $8$ is divisible by $16$. Thus this case yields no solution.

Case 2: $(n+1)$ is a power of $2$ and $(n^2-n+6)$ is divisible by $3$
Similarly let $n=2^u-1$ and $(n^2-n+6)=3.2^v$ and we get $2^{2u}-3.2^u+8=3.2^v$. Checking for $u=0,1,2,3$, $v=0,1,2,3$ we have the solutions are $(u.v)=(0,0),(1,1),(2,2)$. And

if Both $u,v$ cannot be greater than $3$, so these are all the solutions in this case.

Case3: (n+1) is a power of $2$ and divisible by $3$, $(n^2-n+6)$ is a power of $2$.
Letting $n=3.2^u-1$, get $9.2^{2u}-9.2^u+8=2^v$. Similar to the previous cases, check for $u=0,1,2,3$ and $v=0,1,2,3$ and get solutions. And similarly there is no solutoin with
both $u,v$ greater than $3$.

So we get all solutions from these three cases, and of course we don't have to consider the case where both $(n+1)$ and $(n^2-n+6)$ are divisible by $3$.

[Masum]

Masum vai, haven't you missed the case when $(n+1)$ is a power of $2$ but $(n^2-n+6)$ is divisible by $3$?

May be, but I often miss some cases(intentionally sometimes though, carelessly in other cases). But I don't want to read my old post again, so I am not gonna see if I missed anything. However, that should be some debugging