Maths Olympiad Prep

Track / Stage 5 / 98 of 400 #698 of 1964

Problem 698

AIME late
Combinatorics Difficulty 5.3 Find the answer

4 complex ones, their product is exactly a square number.

Translate the text above into English, please keep the original text's line breaks and format, and output the translation result directly.

Note: The provided translation is a direct interpretation of the given Chinese text. However, the phrase "斯4个繁" is somewhat ambiguous and could be interpreted differently based on context. The translation "4 complex ones" is a reasonable guess but might not be accurate without more context. If "斯" is a name or specific term, it should be translated or transliterated accordingly.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

From the observation, if (a,b)(a, b) is a pair of numbers among the 48 given numbers, for example, a=27385911,b=28375l1113a=2^{7} \cdot 3^{8} \cdot 5^{9} \cdot 11, b=2^{8} \cdot 3^{7} \cdot 5^{l} \cdot 11 \cdot 13, then the product ab=(2437511)2313a b=\left(2^{4} \cdot 3^{7} \cdot 5^{*} \cdot 11\right)^{2} \cdot 3 \cdot 13. Since (28375911)2\left(2^{8} \cdot 3^{7} \cdot 5^{9} \cdot 11\right)^{2} is already a perfect square, we only need to consider the remaining prime numbers 3 and 13 in the product aba b.

Let (a,b)(a, b) be any two numbers among the 18 given numbers, and express the product aba b as a perfect square and a set of prime numbers that are not squared. For example, the pair (a,b)(a, b) corresponds to the set {3,13}\{3,13\}.

Since there are C482=1128C_{48}^{2}=1128 different pairs of numbers chosen from 48 numbers, and there are 2n=10242^{n}=1024 subsets of a set of 10 different prime numbers, and since 1128 > 1024, there must be two different pairs (a,b)(a, b) and (c,d)(c, d) that correspond to the same subset of prime numbers {p1,p2,,pk}\left\{p_{1}, p_{2}, \cdots, p_{k}\right\}, where 0k100 \leqslant k \leqslant 10. Therefore,
ab=m2p1p2pk,cd=n2p1p2pk,abcd=(mnp1p2pk)2 \begin{array}{l} a b=m^{2} p_{1} p_{2} \cdots p_{k}, c d=n^{2} p_{1} p_{2} \cdots p_{k}, \\ a b c d=\left(m n p_{1} p_{2} \cdots p_{\mathrm{k}}\right)^{2} \end{array}
is a perfect square.
If the two pairs (a,b)(a, b) and (c,d)(c, d) have no common elements, then a,b,c,da, b, c, d are the desired numbers.
If these two pairs have a common element, let's say b=db=d, then aca c must be a perfect square.
In this case, consider the remaining 46 numbers. Since the product of these 46 numbers still has no more than 10 different prime factors, and there are C482=1035>1024=2nC_{48}^{2}=1035>1024=2^{n}, we can certainly find two different pairs (x,y)(x, y) and (u,v)(u, v) such that xyuvx y u v is a perfect square. If these two pairs have no common elements, then xx, y,u,vy, u, v are the desired numbers; if they have a common element, say x=vx=v, then yuy u is a perfect square. In this way, a,c,y,ua, c, y, u are the desired numbers.

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