Maths Olympiad Prep

Library / /840 of 860

Algebra Difficulty 5.8 AIME, harder Find the answer

For how many unordered sets {a,b,c,d}\{a, b, c, d\} of positive integers, none of which exceed 168, do there exist integers w,x,y,zw, x, y, z such that (1)wa+(1)xb+(1)yc+(1)zd=168(-1)^{w} a+(-1)^{x} b+(-1)^{y} c+(-1)^{z} d=168? If your answer is AA and the correct answer is CC, then your score on this problem will be 25e3CAC\left\lfloor 25 e^{\left.-3 \frac{|C-A|}{C}\right\rfloor}\right..

A number or a short expression. Spacing and $ signs are ignored.

Solution

As an approximation, we assume a,b,c,da, b, c, d are ordered to begin with (so we have to divide by 24 later) and add to 168 with a unique choice of signs; then, it suffices to count e+f+g+h=168e+f+g+h=168 with each e,f,g,he, f, g, h in [168,168][-168,168] and then divide by 24 (we drop the condition that none of them can be zero because it shouldn't affect the answer that much). One way to do this is generating functions. We want the coefficient of t168t^{168} in the generating function (t168+t167++t167+t168)4=(t169t168)4/(t1)4\left(t^{-168}+t^{-167}+\ldots+t^{167}+t^{168}\right)^{4}=\left(t^{169}-t^{-168}\right)^{4} /(t-1)^{4}. Clearing the negative powers, it suffices to find the coefficient of t840t^{840} in (t3371)4/(t1)4=(14t337+6t674)1(t1)4\left(t^{337}-1\right)^{4} /(t-1)^{4}=\left(1-4 t^{337}+6 t^{674}-\ldots\right) \frac{1}{(t-1)^{4}}. To do this we expand the bottom as a power series in tt: 1(t1)4=n0(n+33)tn\frac{1}{(t-1)^{4}}=\sum_{n \geq 0}\binom{n+3}{3} t^{n}. It remains to calculate (840+33)4(840337+33)+6(840674+33)\binom{840+3}{3}-4 \cdot\binom{840-337+3}{3}+6 \cdot\binom{840-674+3}{3}. This is almost exactly equal to 16(843345063+61693)1.83×107\frac{1}{6}\left(843^{3}-4 \cdot 506^{3}+6 \cdot 169^{3}\right) \approx 1.83 \times 10^{7}. Dividing by 24, we arrive at an estimation 762500. Even if we use a bad approximation 1624(85034\frac{1}{6 \cdot 24}\left(850^{3}-4\right.. 5003+61503500^{3}+6 \cdot 150^{3}) we get approximately 933000, which is fairly close to the answer.

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.