Olympiad Maths Prep

Library / /2 of 5

Combinatorics Difficulty 6.1 National olympiad Prove it Greece

Find the number of ordered 6-tuples (α1,α2,α3,α4,α5,α6)(\alpha_1, \alpha_2, \alpha_3, \alpha_4, \alpha_5, \alpha_6) can be created, if the numbers α1,α2,α3,α4,α5,α6\alpha_1, \alpha_2, \alpha_3, \alpha_4, \alpha_5, \alpha_6 can take the values 00, 11 and 22 and the sum α1+α2+α3+α4+α5+α6\alpha_1 + \alpha_2 + \alpha_3 + \alpha_4 + \alpha_5 + \alpha_6 is even.

Solution

The sum α1+α2+α3+α4+α5+α6\alpha_1 + \alpha_2 + \alpha_3 + \alpha_4 + \alpha_5 + \alpha_6 is even, if and only if, the number of 11's is even, that is 00, 22, 44, 66.

In the case of zero 11's, the possible selections are 262^6, because for each αi\alpha_i we have 22 selections, (00 or 22).

When we have two 11's, then they can be selected in (62)\binom{6}{2} ways and the rest four places can be completed by 242^4 ways. It means that we have 24(62)2^4 \cdot \binom{6}{2} possible 66-tuples.

Similarly, in the case we have four 11's we conclude that we have 22(64)2^2 \cdot \binom{6}{4} possible 66-tuples.

When we have six 11's then obviously we have only one possible 66-tuple.

Therefore the possible 66-tuples are totally:
26+24(62)+22(64)+1=64+1615+415+1=365. 2^6 + 2^4 \cdot \binom{6}{2} + 2^2 \cdot \binom{6}{4} + 1 = 64 + 16 \cdot 15 + 4 \cdot 15 + 1 = 365.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.