Maths Olympiad Prep

Library / /353 of 520

Combinatorics Difficulty 6.8 National olympiad Find the answer

Let nn be a positive integer. Given are circular discs with radii 1,2,,n1, 2, \ldots, n. For each size, we have two discs: a transparent one and an opaque one. Each disc has a hole in the middle, allowing us to stack the discs on a vertical rod. We want to create stacks that meet the following conditions:

- Exactly one disc of each size is on the stack.
- When viewed from directly above, the outer edges of all nn discs on the stack can be seen. (This means that if there is an opaque disc on the stack, then no smaller discs may lie below it.)

Determine the number of different stacks that can be made under these conditions. (Two stacks are different if they do not use exactly the same set of discs, but also if they do use exactly the same set of discs but not in the same order.)

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

Solution

A stack is considered valid if it meets the conditions. Let ana_{n} be the number of valid stacks with nn disks (with radii 1,2,,n1, 2, \ldots, n). We prove by induction that an=(n+1)!a_{n}=(n+1)!. For n=1n=1, we can make two stacks: one with the transparent disk of radius 1 and one with the opaque disk of radius 1, so a1=2=2!a_{1}=2=2!. Suppose now that for some n1n \geq 1 we have proven that an=(n+1)!a_{n}=(n+1)!. Consider a valid stack with n+1n+1 disks. If we remove the disk with radius n+1n+1, all remaining disks are still visible from above, so we are left with a valid stack of nn disks. Every valid stack with n+1n+1 disks can thus be created by inserting the disk with radius n+1n+1 into a valid stack of nn disks at a suitable position. In principle, there are n+1n+1 positions where we can insert the disk with radius n+1n+1: above the top disk, above the second disk, ..., above the bottom disk, and also below the bottom disk. The disk with radius n+1n+1 is always visible, regardless of where we insert it. If we insert the disk with radius n+1n+1 below the bottom disk, it can be either transparent or opaque; in both cases, the view of the other disks is not blocked. Thus, there are 2an2 a_{n} valid stacks where the disk with radius n+1n+1 is at the bottom. However, if we insert an opaque disk with radius n+1n+1 at any other position, it blocks the view of the disks below it. Therefore, we can only insert the transparent disk with radius n+1n+1 at the other nn positions. Thus, there are nann a_{n} valid stacks where the disk with radius n+1n+1 is not at the bottom. We find

an+1=2an+nan=(n+2)an=(n+2)(n+1)!=(n+2)! a_{n+1}=2 a_{n}+n a_{n}=(n+2) a_{n}=(n+2)(n+1)!=(n+2)!

This completes the induction.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.