Maths Olympiad Prep

Library / /81 of 100

Combinatorics Difficulty 5.7 AIME, harder Prove it China

Let an=C200n(63)200n(12)na_n = C_{200}^n \cdot (\sqrt[3]{6})^{200-n} \cdot \left(\frac{1}{\sqrt{2}}\right)^n (n=1,2,,95)(n = 1, 2, \dots, 95). Then the number of terms that are integers in {an}\{a_n\} is ______.

Solution

We have an=C200n3200n324005n6a_n = C_{200}^n \cdot 3^{\frac{200-n}{3}} \cdot 2^{\frac{400-5n}{6}}. When ana_n (1n95)(1 \le n \le 95) is an integer, 200n3\frac{200-n}{3} and 4005n6\frac{400-5n}{6} must be integers. Then 6n+46 \mid n+4.

When n=2,8,14,20,26,32,38,44,50,56,62,68,74,80n = 2, 8, 14, 20, 26, 32, 38, 44, 50, 56, 62, 68, 74, 80, 200n3\frac{200-n}{3} and 4005n6\frac{400-5n}{6} are all non-negative integers. So the corresponding ana_n, totally 14, are integers.

When n=86n = 86, we have a86=C2008633825a_{86} = C_{200}^{86} \cdot 3^{38} \cdot 2^{-5}. The number of the factors of 2 in 200!200! is
[2002]+[20022]+[20023]+[20024]+[20025]+[20026]+[20027]=197. \left[ \frac{200}{2} \right] + \left[ \frac{200}{2^2} \right] + \left[ \frac{200}{2^3} \right] + \left[ \frac{200}{2^4} \right] + \left[ \frac{200}{2^5} \right] + \left[ \frac{200}{2^6} \right] + \left[ \frac{200}{2^7} \right] = 197.
By the same reason, the numbers of the factors of 2 in 86!86! and 114!114! are 82 and 110, respectively. Therefore, the number of the factors of 2 in C20086=200!86!114!C_{200}^{86} = \frac{200!}{86! \cdot 114!} is 19782110=5197 - 82 - 110 = 5. So a86a_{86} is an integer.

When n=92n = 92, we have a92=C20092336210a_{92} = C_{200}^{92} \cdot 3^{36} \cdot 2^{-10}. In the same way, we find the numbers of the factors of 2 in 92!92! and 108!108! are 88 and 105, respectively, which means that in C20092C_{200}^{92} is 19788105=4197 - 88 - 105 = 4. Therefore, a92a_{92} is not an integer.

Overall, the required number is 14+1=1514 + 1 = 15. ☐

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.