Parity Coefficient

Number Theory Level 5

If $\dbinom{n}{r_n}$ is an even number for natural numbers $r_n < n$ and denote $R_n$ as the smallest possible value of $r_n$ , find the value of $n$ less than $10^4$ such that its corresponding $R_n$ is maximized.

Details and Assumptions :

As an explicit example, ${13 \choose 2}, {13 \choose 3}, {13 \choose 6}, {13 \choose 7}, {13 \choose 10}, {13 \choose 11}$ are all even numbers. So the possible values of $r_{13}$ are $2,3,6,7,10,11$ . With $R_{13} = 2$ .
Note that there doesn't exist some values of $r_n$ . For example, ${7 \choose 1}, { 7 \choose 2} , \ldots , {7 \choose 6}$ are all odd numbers. So there's no value of $r_7$ nor $R_7$ .

Bonus : Can you generalize this for some constant $M$ such that $n < M$ ?

The answer is 6143.

2 solutions

Patrick Corn
Apr 28, 2015

The key fact here is Kummer's theorem: the largest power of $p$ dividing $\binom{n}{k}$ is the number of carries when adding $k$ and $n-k$ mod $p$ .

So if the binary expansion of $n$ has a $0$ in the $2^r$ place and a $1$ in all the places to the right of that, then $R_n = 2^r$ (because there are no binary carries when the digits sum to $1$ ). So we need a number for which the rightmost $0$ is as far left as possible. This number is $10111\cdots 1$ , which is $3 \cdot 2^r-1$ . For $n<10^4$ the largest possible $r$ is $11$ , which gives $n = \fbox{6143}$ and $R_n = 2048$ .

This generalizes for any $M$ : $n = 3 \cdot 2^r - 1$ for $r$ chosen as large as possible so that $n < M$ .

Chew-Seong Cheong
Apr 26, 2015

Using a Python program, I noticed that $R_{n_{max}} = 2^k$ are powers of $2$ . It is also noticed that:

$\begin{array} {} k = 0 & \Rightarrow n_0 = 2 & k = 1 & \Rightarrow n_1 = 5 & k = 2 & \Rightarrow n_2 = 11 \\ k = 3 & \Rightarrow n_3 = 23 & k = 4 & \Rightarrow n_4 = 47 & ... & \Rightarrow n_k = 3(2^k)-1 & \end{array} $

Therefore, the largest

$n_k < 10000\quad \Rightarrow 3(2^k) < 10000 \quad \Rightarrow \log{3} + k\log{2} < 4 \\ \Rightarrow k < \dfrac {4-\log{3}}{\log{2}} = 11.7 \quad \Rightarrow k = 11 \quad \Rightarrow n_11 = 3(2^{11}) - 1 = \boxed{6143}$

I have used a spreadsheet to plot out a Pascal Triangle with even coefficients shown as $0$ and odd, $1$ . You can check the first few $n_k$ with it.

But you need to prove that it must be of the form $3(2^k) - 1$ or why must $R_{n_{\text{max}}}$ be a power of $2$ .

Cool! Sierpinski triangle! I didn't expect that!

Pi Han Goh - 6 years, 1 month ago

I knew what I provided is inadequate. I was trained an engineer don't like to proof stuff. Let me look at it again.

Chew-Seong Cheong - 6 years, 1 month ago

Hint hint: see title of this very webpage.

Pi Han Goh - 6 years, 1 month ago

@Pi Han Goh – DAMN IT! I got the answer after following the pattern and entered Rn instead of n! I too tried to answer it with a program and ended up making two guesses that were wrong. Just my luck. Or it's my imprudence. Once I start on a hard problem, I lose track of the actual question. Just to prove that I'm not lying, I can share a few more nos with you:

I call what you call maximizing Rn, longest odd streak possible.

First off, all even nos are dismissed.

Secondly, all nos with configuration 4n+1 are also dismissed.

So, you have 4n+3 left.

I wrote down a few of these binomial coefficient that started with 4n+3 and arrived at the condition for the number to not fail to keep up the streak with increasing r's in (4n+3)Cr. I noticed a pattern that I only had to define these criteria for when the r was a power of 2.

For 4n+3=N, say, to fail the streak at $2^{k}$ , it must follow this configuration:

N= $2^{k+1} \times l + 2^{k} - 1.$ , where l is any +ve integer.

Then I checked whether you asked me to maximize Rn or n, cause I got a larger number when I put k=10. Then I got the maximum value under 10000 to be 6143, but I entered 2048 because I lost track of the question. I also got that for the N=number to fail at 4096, it must be at least 12287 and for 8192, it must at least be 24575.

It's upto you to believe me or not because I saw Chew -Seong Cheong's solution and it was very similar to mine.

EXCELLENT question though.

vishnu c - 6 years, 1 month ago

@Vishnu C – I just found out why exactly my criteria for continuation for the odd streak were defined at powers of 2:

This is quite lengthy because I've mentioned a lot of obvious steps.

Say we start at 4n+3/1!. This is always going to be odd. Next, we move on to (4n+3)(4n+2)/2! We needn't worry about the previous number, i.e, 4n+3/1 satisfying the odd criterion, because we've already verified that. So, we only need to focus on (4n+2)/2 and we can see that this is also going to be odd. Next, we need to go to $\left( ^{ 4n+3 }_{ 3 } \right)$ but now, since we've seen that (4n+3)(4n+2)/2! is odd, we can see that we need to focus on the new numbers:

(4n+1)/3.

This gives you the general pattern that we need to focus on the new numbers. Let's use induction.

If you've seen to it that the criterion for the number PASSING ${ 2 }^{ k }$ (in the denominator) is met, i.e, the number that you start with can be expressed as $N = 2^{ k+1 }(m+1)-1$ , where $m=l-1$ , say, is any positive integer.

Now we only need to focus on the new numbers. It's not going to need to be redefined till the next power of 2 because of the following:

$N-{ 2 }^{ k }-r+1 ={ 2 }^{ k+1 }l-{ 2 }^{ k }-r$ , for $r=1...{ 2 }^{ k }-1$ . We need to focus on the new term $\frac { { 2 }^{ k+1 }l-{ 2 }^{ k }-r }{ { 2 }^{ k }+r }$ .We only need to worry about even r's because the odd r's cannot make the numerator even, and the denominator is also going to stay odd.

We focus on, for r = 2m, the following:

$\frac { { 2 }^{ k+1 }l-{ 2 }^{ k }-2m }{ { 2 }^{ k }+2m } = \frac { { 2 }^{ k }l-{ 2 }^{ k-1 }-m }{ { 2 }^{ k-1 }+m }$ .

We can see that for odd m, the expression is odd in the numerator and denominator and we can focus on even m, i.e, m=2a. This means r=4a.

Now, again, we can reduce the expression to $\frac { { 2 }^{ k-1 }l-{ 2 }^{ k-2 }-a }{ { 2 }^{ k-2 }+a }$ . It's similar to the previous expression with m. Again, we have to worry about a being even, and so on till $r={ 2 }^{ k-1 }b$ , where we get:

$\frac { 4l-2-b }{ 2+b }$ .

Again, this is odd for when b is odd. For when b is even, b=2 and $r={ 2 }^{ k }$ . So now, we have, from our first expression, $\frac { { 2 }^{ k+1 }l-{ 2 }^{ k }-{ 2 }^{ k } }{ { 2 }^{ k+1 } }$ .

We can see that $l-1 = m$ = even for this to FAIL at ${ 2 }^{ k+1 }$ and $l-1= m$ = odd for N to PASS ${ 2 }^{ k+1 }$ . Now we have, $m={ 2 }c+1$ , where c is any positive integer, to make $N={ 2 }^{ k+1 }(2c+1+1)-1= { 2 }^{ k+2 }(c+1)-1$ PASS. For it to fail, we have $N={ 2 }^{ k+1 }(2c+1)-1=\quad { 2 }^{ k+2 }c+{ 2 }^{ k+1 }-1.$

QED.

vishnu c - 6 years, 1 month ago

@Vishnu C – Note that by PASSING, i mean that the oddness streak continues even beyond 2^k. Failing means that it becomes even at 2^k. I was talking to myself when I was solving this problem and that's why it's not as formal and concise as other proofs.

vishnu c - 6 years, 1 month ago

@Vishnu C – Please refrain from typing text in $\LaTeX$

Pranjal Jain - 6 years ago

@Pranjal Jain – I was still abusing it back then. Sorry!

vishnu c - 6 years ago

@Pranjal Jain – I fixed it.

vishnu c - 6 years ago

@Vishnu C – Please post your solution here! Thanks!

Pi Han Goh - 6 years, 1 month ago

Hey, I just noticed you're in the same district as me! Meet up meet up!

Pi Han Goh - 6 years, 1 month ago

Another Hint: binary expansion

The answer in binary is 1011111111111

Joel Tan - 6 years, 1 month ago

For $^{n}C_{r}$ , binomial coefficient to start being even from r= $2^k$ , the number n should satisfy this equation : $2^{ k+1 }\times l+2 ^{ k } -1$ where l, is any +ve integer.

vishnu c - 6 years, 1 month ago

Superb solution!

A Former Brilliant Member - 6 years, 1 month ago

Parity Coefficient

The answer is 6143.

2 solutions

0 pending reports