Let $n$ be a positive integer. Suppose that we have disks of radii $1, 2, . . . , n.$ Of each size there are two disks: a transparent one and an opaque one. In every disk there is a small hole in the centre, with which we can stack the disks using a vertical stick. We want to make stacks of disks that satisfy the following conditions: $i)$ Of each size exactly one disk lies in the stack. $ii)$ If we look at the stack from directly above, we can see the edges of all of the $n$ disks in the stack. (So if there is an opaque disk in the stack,no smaller disks may lie beneath it.) Determine the number of distinct stacks of disks satisfying these conditions. (Two stacks are distinct if they do not use the same set of disks, or, if they do use the same set of disks and the orders in which the disks occur are different.)
Problem
Source: Netherlands TST for IMO 2017 day 1,problem 1
Tags: combinatorics
01.02.2018 18:35
I suppose we can see the edge of transparent disk (otherwise the problem doesn't make much sense). For each subset $S$ of $[n]= \{ 1,2,...,n\}$, if we know that the stack will use opaque disk of radii $s$ if and only if $s\in S$. We get that the order of those opaque disks is fixed. If $S$ is not an empty set, let $S=\{ s_1,s_2,...,s_k\}$ where $s_1<s_2<...<s_k$ and $k=|S|$. For convenient, let $s_0=0$ and $s_{k+1}=n+1$. We get that we must arrange disks of radii in the interval $(s_i,s_{i+1})$ so that all such disks are above of the disk with radius $s_{i+1}$. Inductively put the disk with radius not appeared, from smallest to largest, we get that there are $$\prod_{i=0}^{k}{\prod_{j=s_i+1}^{s_{i+1}-1}{j}}=\frac{n!}{\prod_{i=1}^{k}{s_i}}$$distinct stacks (here we denote $\prod_{k=a}^{b}{k}=1$ for all positive integers $a>b$). Note that if $S$ is an empty set, there are $n!$ ways of stacking. Hence, we want to calculate $n!+\sum_{S\subseteq [n],S\neq \emptyset}{\frac{n!}{\prod_{s\in S}{s}}}$. It's equal to $n!\prod_{i=1}^{n}{\Big( \frac{1}{1}+\frac{1}{i}\Big) }=(n+1)!$, done.
01.08.2024 14:04
I found the answer is - $$\sum_{k=0}^{n} (n-k)! \times {(n-k+1)k \choose k} $$Is there any wrong? If not how can I manipulate it, Please help! $\color{green} \textbf{Explanation :}$ We will set $\mathbb{O}= (o_1,o_2,...o_k)$ be the set of opaque disks and they must be fixed from above to down by $o_1<o_2...<o_k$ Firstly, We assume $(n-k)$ places for remaining $(n-k)$ transparent disks. they can be placed in these places by $(n-k)!$ ways. Now assume there are $(n-k+1)$ spaces at the front and end and between the $(n-k)$ opaque disks, also let each of these $(n-k+1)$ spaces are divided into $k$ sub-spaces. We wish to place the $k$ opaque disks in these $(n-k+1)k$ sub-spaces in ${(n-k+1)k \choose k}$ ways, and the remaining spaces will be then removed