# Mathematical Food for Thought

Serves a Daily Special and an All-You-Can-Eat Course in Problem Solving. Courtesy of me, Jeffrey Wang.

• ## Meta

Digit To The Unit. Topic: Algebra. Level: AIME. December 6th, 2006

Problem: (2006-2007 Warm-Up 5 – #13) Determine the units digit in the decimal expansion of .

Solution: Well, in its current form it is quite an ugly expression, with half of the terms involving a radical. Maybe we can simplify this, a.k.a. get rid of the radicals. Consider

.

Since we know , then (it’s really small). The above expression is an integer because all of the radical terms cancel out. So if we find the units digit of this, we simply subtract one away and get the units digit of our original number. But this number is just

,

where every term in between is divisible by . That means they all have a units digit of zero, so we only need to look at the last term. Since powers of repeat the sequence

,

we know . So twice of this would give a units digit of . Subtracting one away as we mentioned above gives us a units digit of . QED.

——————–

Comment: This is an excellent application of the binomial theorem and a good test of your intuition, which basically consisted of noticing . The power was an arbitrary even number; in fact, for smaller powers we notice the exact same thing:

.

——————–

Practice Problem: Determine how many elements of the th row of Pascal’s Triangle are odd.

Posted in AIME, Algebra || 2 Comments »

### 2 Responses to “Digit To The Unit. Topic: Algebra. Level: AIME.”

1. t0rajir0u Says:

Probably the best question on today’s warmup, too bad I didn’t really cover anything like that XD

Anyway, I saw a solution by Lucas’ Theorem but I’ll go slightly more basic and use the lemma behind it instead:

Lemma: (a + b)^p = a^p + b^p mod p

Easy to prove. With this lemma, let n = 2^{e_1} + 2^{e_2}+ … + 2^{e_d}(its binary expansion). Then

(x + 1)^n = (x^{2^{e_1}} + 1)(x^{2^{e_2}} + 1)…(x^{2^{e_d}} + 1) mod 2

If this form is expanded every coefficient will be 1 because of unique represention base 2 so there’ll be 2^d odd coefficients, where d is the number of nonzero binary digits in n.

2. t0rajir0u Says:

BY THE WAY HARD QUESTION I COULDN’T DO:

Instead of (x + 1)^n find the number of odd coefficients in (x^2 + x + 1)^n

=(