Maths Olympiad Prep

Library / /308 of 348

Combinatorics Difficulty 5.1 AIME, harder Find the answer

Let TT be the set of numbers of the form 2a3b2^{a} 3^{b} where aa and bb are integers satisfying 0a,b50 \leq a, b \leq 5. How many subsets SS of TT have the property that if nn is in SS then all positive integer divisors of nn are in SS ?

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

Solution

Consider the correspondence (a,b)2a3b(a, b) \leftrightarrow 2^{a} 3^{b} for non-negative integers aa and bb. So we can view TT as the square of lattice points (a,b)(a, b) where 0a,b50 \leq a, b \leq 5, and subsets of TT as subsets of this square. Notice then that the integer corresponding to (a1,b1)\left(a_{1}, b_{1}\right) is a divisor of the integer corresponding to (a2,b2)\left(a_{2}, b_{2}\right) if and only if 0a1a10 \leq a_{1} \leq a_{1} and 0b1b20 \leq b_{1} \leq b_{2}. This means that subsets STS \subset T with the desired property, \section*{Guts Round} correspond to subsets of the square where if a point is in the set, then so are all points to the left and south of it. Consider any such subset SS. For each 0x50 \leq x \leq 5, let SxS_{x} be the maximum yy value of any point (x,y)S(x, y) \in S, or -1 if there is no such point. We claim the values SxS_{x} uniquely characterize SS. This is because each SxS_{x} characterizes the points of the form (x,y)(x, y) in SS. In particular, (x,z)(x, z) will be in SS if and only if zSxz \leq S_{x}. If (x,z)S(x, z) \in S with z>Sxz>S_{x}, then SxS_{x} is not the maximum value, and if (x,z)S(x, z) \notin S with zSxz \leq S_{x}, then SS fails to satisfy the desired property. We now claim that SxSyS_{x} \geq S_{y} for x<yx<y, so the sequence S0,,S1S_{0}, \ldots, S_{1} is decreasing. This is because if (y,Sy)\left(y, S_{y}\right) is in the set SS, then so must be (x,Sy)\left(x, S_{y}\right). Conversely, it is easy to see that if S0,,S1S_{0}, \ldots, S_{1} is decreasing, then SS is a set satisfying the desired property. We now claim that decreasing sequences S0,,S5S_{0}, \ldots, S_{5} are in bijective correspondence with walks going only right and down from (1,5)(-1,5) to (5,1)(5,-1). The sequence S0,,S5S_{0}, \ldots, S_{5} simply corresponds to the walk (1,5)(1,S0)(0,S0)(0,S1)(1,S1)(4,S5)(5,S5)(5,1)(-1,5) \rightarrow\left(-1, S_{0}\right) \rightarrow\left(0, S_{0}\right) \rightarrow\left(0, S_{1}\right) \rightarrow\left(1, S_{1}\right) \rightarrow \cdots \rightarrow\left(4, S_{5}\right) \rightarrow\left(5, S_{5}\right) \rightarrow(5,-1). Geometrically, we are tracing out the outline of the set SS. The number of such walks is simply (126)\binom{12}{6}, since we can view it as choosing the 6 of 12 steps at which to move right. Thus the number of subsets SS of TT with the desired property is (126)=924\binom{12}{6}=924.

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.