Let be the set of numbers of the form where and are integers satisfying . How many subsets of have the property that if is in then all positive integer divisors of are in ?
Solution
Consider the correspondence for non-negative integers and . So we can view as the square of lattice points where , and subsets of as subsets of this square. Notice then that the integer corresponding to is a divisor of the integer corresponding to if and only if and . This means that subsets 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 . For each , let be the maximum value of any point , or -1 if there is no such point. We claim the values uniquely characterize . This is because each characterizes the points of the form in . In particular, will be in if and only if . If with , then is not the maximum value, and if with , then fails to satisfy the desired property. We now claim that for , so the sequence is decreasing. This is because if is in the set , then so must be . Conversely, it is easy to see that if is decreasing, then is a set satisfying the desired property. We now claim that decreasing sequences are in bijective correspondence with walks going only right and down from to . The sequence simply corresponds to the walk . Geometrically, we are tracing out the outline of the set . The number of such walks is simply , since we can view it as choosing the 6 of 12 steps at which to move right. Thus the number of subsets of with the desired property is .