Treble Trouble!

Probability Level 4

$\large 2^a + 2^b + 2^c$

We are given the natural numbers $1\leq a \leq 100$ , $1\leq b \leq 50$ , $1 \leq c \leq 25$ . If the total possible number of ordered triplets $(a,b,c)$ such that the expression above is divisible by $3$ is $k$ , evaluate $k$ .

The answer is 31250.

1 solution

Jackson Abascal
Jul 5, 2015

Let's take a look at numbers of the form $2^x$ modulo $3$ . we can see $2^1$ is $2$ , $2^2$ is $1$ , $2^3$ is $1$ again, and more generally $2^x$ is $2$ for odd $x$ and $1$ for even $x$ .

Given we can replace each of $2^a$ , $2^b$ , and $2^c$ with either $1$ or $2$ modulo $3$ , how many ways can we do this such that the summation evaluates to a multiple of $3$ ?

There are only two: $1+1+1$ and $2+2+2$ .

Thus our answer is (# possible even a)(# possible even b)(# possible even c) + (# possible odd a)(# possible odd b)(# possible odd c)

= $(50)(25)(12) + (50)(25)(13)= \boxed{31250}$

My major obstacle was to prove to myself the rule for $2^x$ modulo $3$ . I still can't see why this is so, and made a leap of faith.

You got a typo " $2^3$ is $1$ again" should read " $2^3$ is $2$ again".

Anton Shkrunin - 5 years, 9 months ago

Treble Trouble!

The answer is 31250.

1 solution

0 pending reports