RMO 2003 ; Part - 2

If n n is an integer greater than 7 7 then ( n 7 ) n 7 \dbinom{n}{7}- \left\lfloor \dfrac{n}{7} \right \rfloor is divisible by:

7 6 5 4

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Prasun Biswas
Jun 8, 2015

Since n Z > 7 n\in\Bbb{Z_{\gt 7}} , its base 7 7 representation contains more than or equal to 2 2 digits. More precisely, consider the base 7 7 representation of n n as follows:

n = k = 0 q n k 7 k where 7 q n < 7 q + 1 n=\sum_{k=0}^q n_k7^k~\textrm{where }7^q\leq n\lt 7^{q+1}

where q q is some non-negative integer 1 \geq 1 depending on the value of n n satisfying the inequality (bounding) stated above.

Also, it's obvious by definition of base 7 7 expansion that all the n i n_i 's are non-negative integers depending on the value of n n which satisfy 0 n i 6 0\leq n_i\leq 6 (this idea is used while evaluating the floor expression).

Also, we have 7 10 = 10 7 = 000 ( q 1 ) digits 10 7 \overline{7}_{10}=\overline{10}_7=\overline{\underbrace{000\cdots}_{(q-1)\textrm{ digits}}10}~_{7} .

Claim: The given expression in the problem is divisible by 7 7 .

Proof: We use Lucas' Theorem noting the fact that 7 7 is a prime.

( n 7 ) ( n 0 0 ) ( n 1 1 ) k = 2 q ( n k 0 ) 1 n 1 k = 2 q 1 n 1 ( m o d 7 ) \binom n7\equiv \binom{n_0}{0}\cdot\binom{n_1}{1}\cdot\prod_{k=2}^q\binom{n_k}{0}\equiv 1\cdot n_1\cdot\prod_{k=2}^q 1\equiv n_1\pmod7

Then again, using the base 7 7 expansion of n n , we easily have,

n 7 = ( k = 2 q n k 7 k 1 ) + n 1 + n 0 7 = ( k = 2 q n k 7 k 1 ) + n 1 + n 0 7 n 7 = ( k = 2 q n k 7 k 1 ) + n 1 + 0 0 + n 1 + 0 n 1 ( m o d 7 ) \begin{aligned}\left\lfloor\frac n7\right\rfloor=\left\lfloor\left(\sum_{k=2}^q n_k7^{k-1}\right)+n_1+\frac{n_0}{7}\right\rfloor=\left(\sum_{k=2}^q n_k7^{k-1}\right)+n_1+\left\lfloor\frac{n_0}{7}\right\rfloor\\ \implies\left\lfloor\frac n7\right\rfloor=\left(\sum_{k=2}^q n_k7^{k-1}\right)+n_1+0\equiv 0+n_1+0\equiv n_1\pmod7\end{aligned}

Hence, we conclude that n Z > 7 \forall~n\in\Bbb{Z_{\gt 7}} , we have,

( n 7 ) n 7 n 1 n 1 0 ( m o d 7 ) 7 ( n 7 ) n 7 \binom n7-\left\lfloor\frac n7\right\rfloor\equiv n_1-n_1\equiv 0\pmod{7}\iff 7\mid\binom n7-\left\lfloor\frac n7\right\rfloor


For disproving the other options, it's easy to show a counter-example like n = 8 n=8 which Z > 7 \in\Bbb{Z_{\gt 7}} easily disproves all the other three options.

Original solution:::::


We have ( n 7 ) = n ( n 1 ) ( n 2 ) ( n 6 ) 7 ! \dbinom{n}{7} = \dfrac{n(n-1)(n-2)\cdots(n-6)}{7!} .

In the numerator, there is a factor divisible by 7, and the other six factors leave the remainders 1, 2, 3, 4, 5, 6, in some order when divided by 7.

Hence the numerator may be written as

7 k ( 7 k 1 + 1 ) ( 7 k 2 + 2 ) ( 7 k 6 + 6 ) 7k(7k_1 + 1)(7k_2+2)\cdots(7k_6+ 6)

Also we conclude that [ n p ] = k \left [ \frac np \right ] = k , as in the set { n , n 1 , , n 6 } \{n,n-1,\ldots,n-6\} , 7 k 7k is the only number which is a multiple of 7. If the given number is called Q Q , then

Q = 7 k ( 7 k 1 + 1 ) ( 7 k 2 + 2 ) ( 7 k 6 + 6 ) 7 ! k = k ( 7 k 1 + 1 ) ( 7 k 2 + 2 ) ( 7 k 6 + 6 ) 6 ! 6 ! = 7 t k 6 ! \begin{aligned} Q &=& 7k \dfrac{(7k_1 + 1)(7k_2+2)\cdots(7k_6+ 6)}{7!} - k \\ &=& k \cdot \dfrac{(7k_1 + 1)(7k_2+2)\cdots(7k_6+ 6) - 6!}{6!} \\ &=& \dfrac{7tk}{6!} \\ \end{aligned}

We know that Q Q is an integer, and so 6 ! 6! divides 7 t k 7tk . Since gcd ( 7 , 6 ! ) = 1 \gcd(7,6!) = 1 , even after cancellation there is a factor of 7 still left in the numerator. Hence 7 divides Q Q , as desired.


Just kidding, got it from Solutions to CRMO-2003 .

Pi Han Goh - 5 years, 9 months ago

Log in to reply

Whoa! Nice work! +1

Prasun Biswas - 5 years, 9 months ago

Log in to reply

I know. I thought of it myself.

Pi Han Goh - 5 years, 9 months ago

Log in to reply

@Pi Han Goh No doubt about that. :D

Prasun Biswas - 5 years, 9 months ago

@Ameya Salankar , is this the intended proof? I'm not sure whether we're allowed to use such heavy machinery like Lucas' Theorem for RMO problems. Is there, perhaps, a more elementary solution to this (other than my approach) ?

If there is, I'm guessing it's quite possibly an inductive proof?

Prasun Biswas - 6 years ago

Log in to reply

elemetary hint - 7 is a prime number

U Z - 6 years ago

Log in to reply

If you observe, I also used the fact that 7 7 is a prime number in my solution.

Prasun Biswas - 6 years ago
Raven Herd
Jun 9, 2015

Does anyone have an elementary solution ? I am unable to find one.

There might be. Try searching for one in the official website of RMO.

Prasun Biswas - 6 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...