Maths Olympiad Prep

Library / /337 of 348

Algebra Difficulty 5.3 AIME, harder Find the answer

Kevin writes down the positive integers 1,2,,151,2, \ldots, 15 on a blackboard. Then, he repeatedly picks two random integers a,ba, b on the blackboard, erases them, and writes down gcd(a,b)\operatorname{gcd}(a, b) and lcm(a,b)\operatorname{lcm}(a, b). He does this until he is no longer able to change the set of numbers written on the board. Find the maximum sum of the numbers on the board after this process.

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

Solution

Since vp(gcd(a,b))=min(vp(a),vp(b))v_{p}(\operatorname{gcd}(a, b))=\min \left(v_{p}(a), v_{p}(b)\right) and vp(lcm(a,b))=max(vp(a),vp(b))v_{p}(\operatorname{lcm}(a, b))=\max \left(v_{p}(a), v_{p}(b)\right), we may show the following: Claim. For any prime pp and non-negative integer kk, the number of numbers nn on the board such that vp(n)=kv_{p}(n)=k doesn't change throughout this process. Let the 15 final numbers on the board be a1a2a3a15a_{1} \leq a_{2} \leq a_{3} \cdots \leq a_{15}. Note that aiaja_{i} \mid a_{j} for all i<ji<j. For each prime pp, let Xp,i=vp(ai)X_{p, i}=v_{p}\left(a_{i}\right). Note that by the lemma, we have (X2,1,X2,2,,X2,15)=(0,0,0,0,0,0,0,0,1,1,1,1,2,2,3)(X3,1,X3,2,,X3,15)=(0,0,0,0,0,0,0,0,0,0,1,1,1,1,2)(X5,1,X5,2,,X5,15)=(0,0,0,0,0,0,0,0,0,0,0,0,1,1,1)(X7,1,X7,2,,X7,15)=(0,0,0,0,0,0,0,0,0,0,0,0,0,1,1)(X11,1,X11,2,,X11,15)=(0,0,0,0,0,0,0,0,0,0,0,0,0,0,1)(X13,1,X13,2,,X13,15)=(0,0,0,0,0,0,0,0,0,0,0,0,0,0,1)\begin{aligned} \left(X_{2,1}, X_{2,2}, \ldots, X_{2,15}\right) & =(0,0,0,0,0,0,0,0,1,1,1,1,2,2,3) \\ \left(X_{3,1}, X_{3,2}, \ldots, X_{3,15}\right) & =(0,0,0,0,0,0,0,0,0,0,1,1,1,1,2) \\ \left(X_{5,1}, X_{5,2}, \ldots, X_{5,15}\right) & =(0,0,0,0,0,0,0,0,0,0,0,0,1,1,1) \\ \left(X_{7,1}, X_{7,2}, \ldots, X_{7,15}\right) & =(0,0,0,0,0,0,0,0,0,0,0,0,0,1,1) \\ \left(X_{11,1}, X_{11,2}, \ldots, X_{11,15}\right) & =(0,0,0,0,0,0,0,0,0,0,0,0,0,0,1) \\ \left(X_{13,1}, X_{13,2}, \ldots, X_{13,15}\right) & =(0,0,0,0,0,0,0,0,0,0,0,0,0,0,1) \end{aligned} Thus, since ai=ppXp,ia_{i}=\prod_{p} p^{X_{p, i}} for each ii, so we get the 15 final numbers on the board are 1,1,1,1,1,1,1,1,2,2,6,6,60,420, and 3603601,1,1,1,1,1,1,1,2,2,6,6,60,420, \text { and } 360360 Adding these up gives 360854 .

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.