Maths Olympiad Prep

Library / /312 of 348

Algebra Difficulty 5.2 AIME, harder Find the answer

Let nn be the answer to this problem. Box BB initially contains nn balls, and Box AA contains half as many balls as Box BB. After 80 balls are moved from Box AA to Box BB, the ratio of balls in Box AA to Box BB is now pq\frac{p}{q}, where p,qp, q are positive integers with gcd(p,q)=1\operatorname{gcd}(p, q)=1. Find 100p+q100p+q.

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

Solution

Originally, box AA has n/2n/2 balls and BB has nn balls. After moving, box AA has n/280n/2-80 balls and BB has n+80n+80 balls. The answer to the problem is thus 100(n/280)+(n+80)gcd(n/280,n+80)=51n8099gcd(n/280,n+80)=?n\frac{100(n/2-80)+(n+80)}{\operatorname{gcd}(n/2-80, n+80)}=\frac{51n-80 \cdot 99}{\operatorname{gcd}(n/2-80, n+80)} \stackrel{?}{=} n Write d=gcd(n/280,n+80)=gcd(n/280,240)d=\operatorname{gcd}(n/2-80, n+80)=\operatorname{gcd}(n/2-80,240). Then the problem is equivalent nd=51n8099nd=51n-80 \cdot 99 or (51d)n=8099(51-d)n=80 \cdot 99, with d240d \mid 240. Let's try to solve this. Either 51d51-d or nn must be divisible by 5. In the latter case, where nn is divisible by 5, we see that dd must be as well. Therefore dd is either 0 or 1mod51 \bmod 5. If nn is divisible by 4, then we know that dd is even and thus 51d51-d is odd. Therefore, since 16809916 \mid 80 \cdot 99, nn must be divisible by 16, meaning that dd is divisible by 8. Alternatively, if nn is not divisible by 4, then since 168099,51d16 \mid 80 \cdot 99,51-d must be divisible by 8, meaning that dd is 3mod83 \bmod 8. Therefore dd is either 0 or 3mod83 \bmod 8. Putting these results together, we find that dd must either be 0,11,160,11,16, or 35mod4035 \bmod 40. Since dd is a divisor of 240 and less than 51, we conclude that dd is either 16 or 40. If d=16d=16, then 51d=3551-d=35, which does not divide 809980 \cdot 99. If d=40d=40, then we get n=720n=720, which ends up working.

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.