Maths Olympiad Prep

Library / /340 of 860

Combinatorics Difficulty 5.1 AIME, harder Find the answer

We wish to color the integers 1,2,3,,101,2,3, \ldots, 10 in red, green, and blue, so that no two numbers aa and bb, with aba-b odd, have the same color. (We do not require that all three colors be used.) In how many ways can this be done?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

The condition is equivalent to never having an odd number and an even number in the same color. We can choose one of the three colors for the odd numbers and distribute the other two colors freely among the 5 even numbers; this can be done in 325=963 \cdot 2^{5}=96 ways. We can also choose one color for the even numbers and distribute the other two colors among the 5 odd numbers, again in 96 ways. This gives a total of 192 possibilities. However, we have double-counted the 32=63 \cdot 2=6 cases where all odd numbers are the same color and all even numbers are the same color, so there are actually 1926=186192-6=186 possible colorings.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.