Only 1

Logic Level 4

How many ways are there to write \parallel or + + in to every square (only one of them in each square) so that 30 30 is a divisor of X X ?

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 = X 1\square 1\square 1\square 1\square 1\square 1\square 1\square 1\square 1\square 1\square 1\square 1\square 1\square 1\square 1=X

Note: The \parallel means concatenate, so for example 4 5 = 45 4\parallel 5=45 .


This problem is inspired by a puzzle from THE HARVARD-MIT MATHEMATICS TOURNAMENT


The answer is 2002.

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.

1 solution

Boi (보이)
Aug 11, 2017

Let f ( n ) f(n) as the sum of all digits of a natural number n . n.

Note that 111 1 1 ( m o d 10 ) . 111\cdots1 \equiv 1 \pmod{10}.

Then if we divide the 1's into n n parts, X n ( m o d 10 ) . X\equiv n \pmod{10}.

Since X X is divisible by 30 , 30, we need n n to be 10. 10.

Nextly, note the strangeness of the multiples of 3. 3.

"If N = k = 1 n a k , \displaystyle N=\sum_{k=1}^n a_k, then f ( N ) k = 1 n f ( a k ) ( m o d 3 ) . \displaystyle f(N)\equiv \sum_{k=1}^n f(a_k) \pmod{3}. "

This is because 1 0 n 1 0 k 0 ( m o d 3 ) 10^n-10^k\equiv0 \pmod{3} for all integers n 1 n\ge1 and k 0. k\ge0.

(= Advancing more up doesn't change anything about the modular value of the sum of the digits)

Since k = 1 n a k \displaystyle \sum_{k=1}^n a_k is always going to be 15 15 in this case, X X must be a multiple of 3. 3.

Therefore the number of ways to write those symbols in the squares is equivalent to the number of ways to select 9 9 squares and writing + + 's in them.

14 C 9 = 14 13 12 11 10 5 4 3 2 1 = 2002 . _{14}C_9=\dfrac{14\cdot13\cdot12\cdot11\cdot10}{5\cdot4\cdot3\cdot2\cdot1}=\boxed{2002}.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...