Toppling Curved Towers

Instead of rectangular prisms, now suppose the tower is part of an annulus. More specifically, it’s the region between two arcs of angle $\theta$ in circles of radius $1$ and $2,$ as shown below.

For small values of $\theta,$ the tower balances on one of its flat sides. But when $\theta$ exceeds some value, the tower no longer balances on a flat side. What is this critical value of $\theta$?

Again, we need to define the center of gravity $(\tilde{x}(\theta), \tilde{y}(\theta))$ and find for what value of $\theta$ do we have $\tilde{x}(\theta) \lt 1.$ Here we should use polar coordinates \begin{align*}x&=\rho \cos \phi \\ y&=\rho \sin \phi\end{align*} to integrate the annular region. We have \begin{align*}\tilde{x}(\theta) &= \frac{\int_0^\theta \int_1^2 \left( \rho \cos \phi \right) \rho \, d\rho \, d\phi}{\int_0^\theta \int_1^2 \rho \,d\rho \,d\phi} \\ &= \frac{ \int_0^\theta \left( \int_1^2 \rho^2 \,d\rho \right) \cos \phi \,d\phi }{ \int_0^\theta \left(\int_1^2 \rho \,d\rho \right) \, d\phi } \\ &= \frac{ \int_0^\theta \frac{2^3 - 1^3}{3} \cos \phi \,d\phi }{ \int_0^\theta \frac{2^2 - 1^2}{2} \,d\phi } \\ &= \frac{ \frac{7}{3} \sin \theta }{ \frac{3}{2} \theta } = \frac{14 \sin \theta}{9 \theta}.\end{align*}

We need to find the solution to the implicit equation $\tilde{x}(\theta) = \frac{14 \sin \theta}{9\theta} = 1.$ Therefore, we find that the point at which the curved tower will topple over is approximately $\theta^* \approx 1.55537048\dots$ radians.

Toppling Towers

A block tower consists of a solid rectangular prism whose height is $2$ and whose base is a square of side length $1$. A second prism, made of the same material, and with a base that’s $L$ by $1$ and a height of $1$, is attached to the top half of the first block, resulting in an overhang as shown below.

When $L$ exceeds some value, the block tower tips over. What is this critical length $L$?

While the problem was stated in three-dimensions, the depth dimension is inconsequential since we will go out on a limb and assume that the solid material that comprises the blocks is uniformly dense. Let's define the coordinate system as the right corner of the 1 x 2 block is at the origin, so that the left corner of the 1x2 block is at $(-1,0)$ and far left corner of the horizontal block is at $(-L-1, 2).$ The block tower tips over if and only if the center of gravity of the tower falls outside of the support the 1x2 block. That is, if $(\tilde{x}(L), \tilde{y}(L))$ is the center of gravity of the full tower, then the tower will fall over if and only if $\tilde{x}(L) \lt -1.$

So we've taken a three dimensional problem and reduced it down to a one dimensional problem. All we have left to do is to compute $\tilde{x}(L),$ so .... let's do that. Let's conveniently define the density so that the weight of the 1x2 block is $2$ units and the other block is $L$ units. The $x$-coordinate of the 1x2 block is at $-\frac{1}{2},$ while the $x$-coordinate of the second block is at $-\frac{L+2}{2}.$ Therefore we have $$\tilde{x}(L) = \frac{\left(-\frac{1}{2}\right) 2 + \left(-\frac{L+2}{2} \right) L}{L + 2} = -\frac{L^2 + 2L + 2}{2(L+2)}.$$ Therefore, we need to solve when $$-\frac{L^2 + 2L + 2}{2(L+2)} \lt -1,$$ which is equivalent to $L^2 - 2 \gt 0,$ so the critical length above which the tower will topple over is $L^* = \sqrt{2}.$

Sure, a bullseye is a bullseye, but what's the average?

Suppose each point on the dartboard is equally likely to be hit by a dart. On average, what score would you expect a single dart to earn?

Let $E = \mathbb{E} [ S ]$ be the average score of a single dart. Based on the setup of the Apollonian gasket, we see that there are infinitely many circles which are only contained within the unit circle. Let's say that we enumerate the radii as $r_n, n \in \mathbb{N},$ say with $r_0 = 1$, $r_1 = r_2 = \frac{1}{2},$ etc. One important point is that the smaller circles entirely contained within the unit eventually mutually exclusively cover the entirety of the unit circle, so however we enumerate them we must have $$\sum_{n=1}^\infty r_n^2 = 1.$$ Additionally, we see that the Apollonian gasket is symmetric about the $x$-axis and about the $y$-axis, so as we are filling things up we can focus on say just enumerating all of the cicles in say the first quadrant and then using symmetrical arguments to fill in the rest.

Additionally, since each circle with radius, say $r_n,$ is then filled with a scaled copy of the Apollonian gasket we see that $$\mathbb{E} [ S \mid r_n ] = \pi + r_n^2 E,$$ since in addition to the scaled copy of the expectation the only other circle that adds to the score is the unit circle. From a law of total expectation, since $$\mathbb{P} [ r_k ] = \frac{\pi r_n^2}{\pi} = r_n^2,$$ we have $$E = \sum_{n=1}^\infty r_n^2 \left( \pi + r_n^2 E \right) = \pi + E \sum_{n=1}^\infty r_n^4,$$ or equivalently $$E = \frac{\pi}{1 - \sum_{n=1}^\infty r_n^4}.$$

Actually, with all of that setup out of the way, let's speak in terms of curvatures $k_n = \frac{1}{r_n}, n \in \mathbb{N},$ where $k_0 = -1$ (since it is encompassing all of the other circles of the gasket). From Descartes' theorem -- or from Soddy's The Kiss Precise, whichever format speaks to your soul best -- we see that if you have three mutually tangent circles, with curvatures $k_\ell$, $k_m,$ $k_n$ then you can find two circles which are mututally tangent to the other three with curvatures $k_\pm,$ satisfying the equation $$(k_\ell + k_m + k_n + k_\pm)^2 = 2 \left( k_\ell^2 + k_m^2 + k_n^2 + k_\pm^2 \right).$$ In particular, we have $$k_\pm = k_\ell + k_m + k_n \pm 2 \sqrt{ k_\ell k_m + k_\ell k_n + k_m k_n }.$$ In particular, if we start with smaller curvatures (bigger radii) and work our way smaller and smaller, we can focus on just the solution $k_+$ since $k_-$ will have already been enumerated. In this way we can enumerate the first $N=84$ largest circles, once symmetry is taken into account, which correspond to the $20$ smallest curvatures. Note that the next largest circle has a curvature of $m_N = \min_{n \geq N+1} k_n = 62.$

Now we see that $$\theta_N = \sum_{n=1}^N r_n^2 \approx 0.955398049382331\dots$$ and $$\phi_N = \sum_{n=1}^N r_n^4 \approx 0.153282259694304\dots.$$ We additionally have $$\sum_{n=N+1}^\infty r_n^4 \leq \left(\max_{n \geq N+1} r_n^2 \right) \left( \sum_{n=N+1}^\infty r_n^2 \right) = \frac{1 - \theta_N}{m_N^2} \approx 0.0000116030048433062\dots.$$ Therefore, we have $$ 1.181031 \pi \approx \frac{\pi}{1-\phi_N} \leq E \leq \frac{\pi}{1 - \phi_N - \frac{1-\theta_N}{m_N^2}} \approx 1.181047 \pi.$$ Therefore, despite the fact that I could do a lot more enumeration and even get some good infinite sequences going based on the recursion formulae above, we see that the expected value of the score of one dart is approximately $$ E \approx 1.1810 \pi \approx 3.7103\dots.$$

A bullseye is a bullseye is a bullseye

You are playing darts with your friend, Apollonius, who has brought his own dartboard. However, this dartboard is somewhat … different. Instead of being a circle divided into concentric rings and sectors, the dartboard is a unit circle (i.e., with radius 1) that’s divided via an Apollonian gasket. In particular, this gasket is defined by two horizontally adjacent, congruent circles with radius 1/2.

But that’s not all! Every circle on the dartboard, no matter how small, is also its own Apollonian sub-gasket. Like the larger circle, every gasket, sub-gasket, sub-sub-gasket, etc., are defined by two horizontally adjacent, congruent circles with radii that are half the radius of their outer circle.

Now, when you throw a dart at this board, your score is the sum of the areas of every circle for which the dart lies inside or on the circumference. (Remember, the entire board is a unit circle.) What is the most a single dart can score?

Well as long as you hit the board at all you score $\pi$, so that's good. We note that if our dart hits the circumference of some circle, say with radius $r$, then there must be at lest some other circle, and in fact due to the nested Apollonian gaskets, infinitely many other circles of which this point is on the circumference. In particular, by recursion, if the dart lands at the point $z_0 + r_0 e^{i\theta}$ for some center, $z_0$, such that $\|z_0\|_2 \lt 1,$ and radius $r_0 \lt 1$, then there are infinitely many more circles $z_k + r_k e^{i\theta},$ where $r_k \leq \frac{1}{2^k}r_0,$ since all of the subcircles in the gasket have radius less than half of their outer circle, for some center $z_k$ satisfying $\|z_k - z_0\|_2 \lt r_0.$ Let's assume that the dart lands at the point of intersection between a circle of radius $r_1$ and a circle of radius $r_2,$ and that the smallest circle in the nested Apollonian gaskets that contains both of these circles is the unit circle, then the total score is $$S(r_1,r_2) \leq \pi + \sum_{n=0}^\infty \frac{\pi r_1^2}{4^n} + \sum_{m=0}^\infty \frac{\pi r_2^2}{4^m} = \pi \left( 1 + \frac{4}{3} \left( r_1^2 + r_2^2 \right) \right).$$

If we take any radii $r_1$, $r_2$ that appear in the Apollonian subgasket, then we get $$ \max S(r_1,r_2) \leq \max_{r_1, r_2} \pi \left( 1 + \frac{4}{3} \left(r_1^2 + r_2^2\right) \right) = \frac{5\pi}{3},$$ since $r_1, r_2 \leq \frac{1}{2}.$ On the other hand, if we get a bullseye, which sits exactly at the origin, then this sits in the circles indexed with centers at $z_k = (\textsf{sgn}(k) \frac{1}{2^{|k|}}, 0 )$ and radii $r_k = \frac{1}{2^{|k|}},$ for all $k \in \mathbb{Z}.$ So the score at the origin is $$S_0 = \sum_{k \in \mathbb{Z}} \pi \frac{1}{4^{|k|}} = \pi + 2\pi \sum_{k=1}^\infty \frac{1}{4^k} = \pi + 2\pi \frac{\frac{1}{4}}{1 - \frac{1}{4}} = \frac{5\pi}{3}.$$ Therefore, the bound is sharp and we must have that the maximum possible score of the dart, which occurs at a bullseye, is $\frac{5\pi}{3} \approx 5.235987756\dots.$

Sure, but I think Hotter Ones would prefer you buy all 100

You’re prepping for a new show, “Hotter Ones,” which has spices ranked from 1 to 100. Let $N$ be the minimum number of spices needed to generate all the numbers from 1 to 100. For how many sets of $N$ spice numbers is it possible to generate all the numbers from 1 to 100 using each spice at most once?

Ok, well at this point, we definitely should not be playing around with searching $\binom{100}{N}$ for ever higher values of $N$ until we get to some subset that actually works. So instead, we will lean on the Lemma that we laid out in the Classic problem, along with an observation below.

The observation is that for each $n \in \mathbb{N},$ the set $B_n = \{1, 2, 4, \dots, 2^{n-1} \} \in \mathcal{B}$ and in particular $\sigma(B_n) = 2^n - 1.$ We have already seen for $n = 1, 2, 3, 4$ that $\{1\},$ $\{1,2\},$ $\{1,2,4\},$ and $\{1,2,4,8\} \in \mathcal{B}.$ To prove the general case, we see that based on our lemma, if $B_n \in \mathcal{B}$ for some $n \geq 1,$ then since $2^n = \sigma(B_n) + 1,$ so $B_n \cup \{ 2^n \} = B_{n+1} \in \mathcal{B}.$ Note that these sets essentially are equivalent to using binary notation, since any number from $1 to 2^n-1$ can be represented by up to an $n$-digit binary representation. One further observation is that in fact for each $n \geq 1$, $B_n \in \mathcal{B}$ is the optimizer of the problem $\varsigma_n = \max \{ \sigma(A) \mid A \in \mathcal{B}, |A| \leq n \} = 2^n - 1.$

Since $2^6 = 64 \lt 100 \lt 2^7 = 128$ we see that $N = 7$ in this case. Even knowing this information I still don't want to test all $\binom{100}{7} = 16,007,560,800$ possible unique 7-tuples to see which ones work. We have already applied our Classic Fiddler lemma up to size $|A|=4,$ so let's just keep churning the crank a few more times. We see that \begin{align*}\mathcal{B}_5 &= \Biggl\{ \{1,2,3,4,5\}, \{1,2,3,4,6\}, \{1,2,3,4,7\}, \{1,2,3,4,8\},\Biggr. \\ &\quad\quad \{1,2,3,4,9\}, \{1,2,3,4,10\}, \{1,2,3,4,11\},\\ &\quad\quad \{1,2,3,5,6\}, \{1,2,3,5,7\}, \{1,2,3,5,8\}, \{1,2,3,5,9\},\\ &\quad\quad \{1,2,3,5,10\}, \{1,2,3,5,11\}, \{1,2,3,5,12\}, \\ &\quad\quad \{1,2,3,6,7\}, \{1,2,3,6,8\}, \{1,2,3,6,9\}, \{1,2,3,6,10\},\\ &\quad\quad \{1,2,3,6,11\}, \{1,2,3,6,12\}, \{1,2,3,6,13\}, \\ &\quad\quad \{1,2,3,7,8\}, \{1,2,3,7,9\}, \{1,2,3,7,10\}, \{1,2,3,7,11\},\\ &\quad\quad \{1,2,3,7,12\}, \{1,2,3,7,13\}, \{1,2,3,7,14\}, \\ &\quad\quad \{1,2,4,5,6\}, \{1,2,4,5,7\}, \{1,2,4,5,8\}, \{1,2,4,5,9\},\\ &\quad\quad \{1,2,4,5,10\}, \{1,2,4,5,11\}, \{1,2,4,5,12\}, \{1,2,4,5,13\}, \\ &\quad\quad \{1,2,4,6,7\}, \{1,2,4,6,8\}, \{1,2,4,6,9\}, \{1,2,4,6,10\},\\ &\quad\quad \{1,2,4,6,11\}, \{1,2,4,6,12\}, \{1,2,4,6,13\}, \{1,2,4,6,14\}, \\ &\quad\quad \{1,2,4,7,8\}, \{1,2,4,7,9\}, \{1,2,4,7,10\}, \{1,2,4,7,11\},\\ &\quad\quad \{1,2,4,7,12\}, \{1,2,4,7,13\}, \{1,2,4,7,14\}, \{1,2,4,7,15\}, \\ &\quad\quad \{1,2,4,8,9\}, \{1,2,4,8,10\}, \{1,2,4,8,11\}, \{1,2,4,8,12\},\\ &\quad\quad \{1,2,4,8,13\}, \{1,2,4,8,14\}, \{1,2,4,8,15\}, \{1,2,4,8,16\} \Biggr\}\end{align*} Now from $|\mathcal{B}_4| = 8$ to $|\mathcal{B}_5| = 60,$ we a 650% growth, so doing this two more times might not be that interesting, or efficient. But let's use our Lemma to trim some of the branches.

We see that for any particular $A \in \mathcal{B}_5,$ the maximum possible value of any $A^\prime \supset A$ with $A^\prime \in \mathcal{B}_6$ is $\sigma(A^\prime) \leq 2\sigma(A) + 1.$ Similarly, for any $\tilde{A} \in \mathcal{B}_7$ with $\tilde{A} \supset A^\prime \supset A,$ we see that $$\sigma(\tilde{A}) \leq 2 \sigma(A^\prime) + 1 \leq 4 \sigma(A) + 3.$$ So since we are ultimately searching for $\mathcal{B}^*_7 = \{ A \in \mathcal{B}_7 \mid \sigma(A) \geq 100 \},$ we can focus on $$A \in \mathcal{B}^*_5 = \{ A \in \mathcal{B}_5 \mid \sigma(A) \geq 25 \},$$ since if $\sigma(A) \leq 24,$ then $\sigma(\tilde{A}) \leq 4 \sigma(A) + 3 \leq 99.$ From inspection, this therefore knocks us down to a much more reasonable set of twenty candidates to search \begin{align*}\mathcal{B}^*_5 &= \Biggl\{ \{1,2,3,6,13\}, \{1,2,3,7,12\}, \{1,2,3,7,13\}, \{1,2,3,7,14\}, \Biggr.\\ &\quad\quad \{1,2,4,5,13\}, \{1,2,4,6,12\}, \{1,2,4,6,13\}, \{1,2,4,6,14\}, \\ &\quad\quad \{1,2,4,7,11\}, \{1,2,4,7,12\}, \{1,2,4,7,13\}, \{1,2,4,7,14\}, \\ &\quad\quad \{1,2,4,7,15\}, \{1,2,7,8,10\}, \{1,2,4,8,11\}, \{1,2,4,8,12\}, \\ &\quad\quad \Biggl.\{1,2,4,8,13\}, \{1,2,4,8,14\}, \{1,2,4,8,15\}, \{1,2,4,8,16\} \Biggr\}\end{align*}

Here again, as we step from $\mathcal{B}^*_5$ to $\mathcal{B}^*_6$ we can focus only on those $A \in \mathcal{B}_6$ with $\sigma(A) \geq 50,$ but this time we can do it from the get go. So we arrive at the somewhat unwieldy 104 candidates to search in \begin{align*}\mathcal{B}_6^* &= \Biggl\{ \{1,2,3,6,13,25\}, \{1,2,3,6,13,26\}, \{1,2,3,7,12,25\}, \{1,2,3,7,12,26\}, \Biggr.\\ &\quad\quad \{1,2,3,7,13,24\}, \{1,2,3,7,13,25\}, \{1,2,3,7,13,26\}, \{1,2,3,7,13,27\}, \\ &\quad\quad \{1,2,3,7,14,23\}, \{1,2,3,7,14,24\}, \{1,2,3,7,14,25\}, \{1,2,3,7,14,26\}, \\ &\quad\quad \{1,2,3,7,14,27\}, \{1,2,3,7,14,28\}, \{1,2,4,5,13,25\}, \{1,2,4,5,13,26\}, \\ &\quad\quad \{1,2,4,6,12,25\}, \{1,2,4,6,12,26\}, \{1,2,4,6,13,24\}, \{1,2,4,6,13,25\}, \\ &\quad\quad \{1,2,4,6,13,26\}, \{1,2,4,6,13,27\}, \{1,2,4,6,14,23\}, \{1,2,4,6,14,24\}, \\ &\quad\quad \{1,2,4,6,14,25\}, \{1,2,4,6,14,26\}, \{1,2,4,6,14,27\}, \{1,2,4,6,14,28\}, \\ &\quad\quad \{1,2,4,7,11,25\}, \{1,2,4,7,11,26\}, \{1,2,4,7,12,24\}, \{1,2,4,7,12,25\}, \\ &\quad\quad \{1,2,4,7,12,26\}, \{1,2,4,7,12,27\}, \{1,2,4,7,13,23\}, \{1,2,4,7,13,24\}, \\ &\quad\quad \{1,2,4,7,13,25\}, \{1,2,4,7,13,26\}, \{1,2,4,7,13,27\}, \{1,2,4,7,13,28\}, \\ &\quad\quad \{1,2,4,7,14,22\}, \{1,2,4,7,14,23\}, \{1,2,4,7,14,24\}, \{1,2,4,7,14,25\}, \\ &\quad\quad \{1,2,4,7,14,26\}, \{1,2,4,7,14,27\}, \{1,2,4,7,14,28\}, \{1,2,4,7,14,29\}, \\ &\quad\quad \{1,2,4,8,10,25\}, \{1,2,4,8,10,26\}, \{1,2,4,8,11,24\}, \{1,2,4,8,11,25\}, \\ &\quad\quad \{1,2,4,8,11,26\}, \{1,2,4,8,11,27\}, \{1,2,4,8,12,23\}, \{1,2,4,8,12,24\}, \\ &\quad\quad \{1,2,4,8,12,25\}, \{1,2,4,8,12,26\}, \{1,2,4,8,12,27\}, \{1,2,4,8,12,28\}, \\ &\quad\quad \{1,2,4,8,13,22\}, \{1,2,4,8,13,23\}, \{1,2,4,8,13,24\}, \{1,2,4,8,13,25\}, \\ &\quad\quad \{1,2,4,8,13,26\}, \{1,2,4,8,13,27\}, \{1,2,4,8,13,28\}, \{1,2,4,8,13,29\}, \\ &\quad\quad \{1,2,4,8,14,21\}, \{1,2,4,8,14,22\}, \{1,2,4,8,14,23\}, \{1,2,4,8,14,24\}, \\ &\quad\quad \{1,2,4,8,14,25\}, \{1,2,4,8,14,26\}, \{1,2,4,8,14,27\}, \{1,2,4,8,14,28\}, \\ &\quad\quad \{1,2,4,8,14,29\}, \{1,2,4,8,14,30\}, \{1,2,4,8,15,20\}, \{1,2,4,8,15,21\}, \\ &\quad\quad \{1,2,4,8,15,22\}, \{1,2,4,8,15,23\}, \{1,2,4,8,15,24\}, \{1,2,4,8,15,25\}, \\ &\quad\quad \{1,2,4,8,15,26\}, \{1,2,4,8,15,27\}, \{1,2,4,8,15,28\}, \{1,2,4,8,15,29\}, \\ &\quad\quad \{1,2,4,8,15,30\}, \{1,2,4,8,15,31\}, \{1,2,4,8,16,19\}, \{1,2,4,8,16,20\}, \\ &\quad\quad \{1,2,4,8,16,21\}, \{1,2,4,8,16,22\}, \{1,2,4,8,16,23\}, \{1,2,4,8,16,24\}, \\ &\quad\quad \{1,2,4,8,16,25\}, \{1,2,4,8,16,26\}, \{1,2,4,8,16,27\}, \{1,2,4,8,16,28\}, \\ &\quad\quad \Biggl.\{1,2,4,8,16,29\}, \{1,2,4,8,16,30\}, \{1,2,4,8,16,31\}, \{1,2,4,8,16,32\} \Biggr\} \end{align*} Rather than exhaustively write out all of the elements of $\mathcal{B}_7^*,$ we only need to enumerate the number of elements in that set, which we can do by just knowing the various qualities of the elements of $\mathcal{B}_6^*.$

In particular, we see that if some $A \in \mathcal{B}^*_6$ then there are exactly $2\sigma(A)-98$ distinct elements $A^\prime \in \mathcal{B}^*_7$ with $A^\prime \supset A$, so since the histogram of $\sigma$ values in $\mathcal{B}^*_6$ is shown in the table below, we can directly calculate that there are a total of $1,014$ sets of $N=7$ spice numbers that can generate all the numbers from $1$ to $100$ using each spice at most once.

$\sigma(A)$	$2\sigma(A) -98$	count
50	2	20
51	4	20
52	6	14
53	8	14
54	10	10
55	12	10
56	14	6
57	16	6
58	18	4
59	20	4
60	22	2
61	24	2
62	26	1
63	28	1

Sure, but I think Hot Ones would prefer you buy all 10

You have been invited on as a guest and want to prepare for the show. However, you don’t feel like purchasing all 10 sauces in advance. Your plan is to purchase fewer sauces, and then to combine sauces together for any you are missing. For example, if you are missing sauce #7, then you can instead simultaneously consume sauces #3 and #4, since $3 + 4 = 7$. (I know the spiciness of the sauces isn’t linear, but for the purposes of this puzzle, let’s assume it is.)

After some pencil-and-paper scratch work, you realize you only need four spices. For example, here’s how you can generate all the values from 1 to 10 using the spices #1, #2, #3, and #4 at most once:

• $1=1$
• $2=2$
• $3=3$
• $4=4$
• $5=1+4$
• $6=2+4$
• $7=3+4$
• $8=1+3+4$
• $9=2+3+4$
• $10=1+2+3+4$

Including this particular set of four spices (i.e., #1 through #4), for how many sets of four spice numbers is it possible to generate all the numbers from 1 to 10 using each spice at most once?

The brute force way of doing this would be to check all $\binom{10}{4} = 210$ sets of four spice numbers with no repeats and check whether they are able to generate all the numbers from $1$ to $10$ while using each spice at most one. But that seems tiresome, so let's instead try to work on the general solution that we will use for the Extra Credit problem.

Let $[n] := \{ 1, 2, \dots, n \} \subset \mathbb{N}.$ For some subset $A \subseteq \mathbb{N},$ let's define the $$\Sigma(A) = \{ n \in \mathbb{N} \mid \exists ! i_1, \dots, i_k \in A, n = i_1 + \dots + i_k \},$$ whereas we will let $\sigma(A) = \sum_{a \in A} a$ and $M(A) = \max \{ a \in A \}.$ Let's define $$\mathcal{B} = \{ A \subseteq \mathbb{N} \mid [\sigma(A)] = \Sigma(A) \}.$$ For the Classic problem, we then want to find all $A \in \mathcal{B}$ with $|A| = 4$ and $\sigma(A) \geq 10.$

It will help to have one additional lemma of sorts: If $A \in \mathcal{B},$ then, for any $\ell \in \{ M(A)+1, \dots, \sigma(A) + 1 \},$ $A \cup \{\ell\} \in \mathcal{B}$ as well. To prove this point, since obviously $[\sigma(A)] = \Sigma(A) \subset \Sigma(A \cup \{\ell\}),$ we need to show that $$[\sigma(A) + \ell] \setminus [\sigma(A)] = \{\sigma(A)+1, \dots, \sigma(A)+\ell \} \subset \Sigma(A \cup \{\ell\}).$$ Let's take any $q \in [\sigma(A) + \ell] \setminus [\sigma(A)],$ then $q - \ell \lt \sigma(A),$ so $\exists ! i_1, i_2, \dots i_k \in A$ such that $i_1 + \dots + i_k = q - \ell,$ for some $k = 1, \dots, |A|.$ Furthermore, $\ell \gt M(A),$ so $i_j \ne q,$ for $j = 1, \dots, k,$ so $i_1, i_2, \dots, i_k,$ and $\ell$ are all unique elements of $A \cup \{\ell\}$ and sum to $q.$ Thus, $[\sigma(A) + \ell] \setminus [\sigma(A)] \subset \Sigma(A \cup \{\ell\}),$ therefore if $A \in \mathcal{B}$ then $A \cup \{\ell\} \in \mathcal{B}$ as well for $\ell \in \{M(A) + 1, \dots, \sigma(A) + 1 \}.$

Now let's start by indentifying all $A \in \mathcal{B}$ with $|A| = 4,$ well, er, ... I guess let's start a bit before that. Clearly, $\{1\} \in \mathcal{B}.$ From our lemma, we then see that $\{1,2\} \in \mathcal{B}.$ Using the lemma again gives the two members of $\mathcal{B}$ with cardinality of $3,$ that is $\{1,2,3\}$ and $\{1,2,4\}.$ Therefore, with one additional application of the lemma, we get \begin{align*}\mathcal{B}_4 = \{ A \in \mathcal{B} \mid |A| = 4 \} &= \Biggl\{ \{1,2,3,4\}, \{1,2,3,5\}, \{1,2,3,6\}, \{1,2,3,7\},\Biggr. \\ &\quad\quad\quad \Biggl. \{1,2,4,5\}, \{1,2,4,6\},\{1,2,4,7\}, \{1,2,4,8\}\Biggr\}.\end{align*} Since by inspection $\sigma(A) \geq 10$ for each $A \in \mathcal{B}_4,$ we conclude that there are 8 sets of four spice numbers where all the numbers from 1 to 10 can be generated using each spice at most once.

An N person class?! Now that's really deranged!

If there are $N$ students in the class, where $N$ is some large number, how likely is it that they form a single loop that includes the entire class, in terms of $N$?

In the classic problem, we actually went through the various types of assignments that could work, but even there we showed roughly enough to know that the number of single loop gift exchange assignments is $(N-1)!$. The somewhat trickier piece is for the total number of all acceptable gift exchange assignments. Here, if you were paying attention to the titles of these posts, you might have been alerted to the fact that an acceptable gift exchange assignment, that is a permutation where no number is assigned to itself, is called a derangement. The number of derangements of $N$ elements is sometimes called the sub-factorial, denoted $!N,$ which can be shown to have the formula $$!N = N!\sum_{i=0}^N \frac{(-1)^i}{i!}.$$ Thus, we see that the probability of having a single loop for some large number $N$ students is $$\frac{(N-1)!}{N! \sum_{i=0}^N \frac{(-1)^i}{i!} } \approx \frac{e}{N}$$ as $N \to \infty,$ since $\sum_{i=0}^\infty \frac{(-1)^i}{i!} = e^{-1}.$

You know, it honestly takes a smidgeon of the fun out of knowing the solution, rather than doing much work for it. So, I dunno, maybe let's derive the formula $$!N = N! \sum_{i=0}^N \frac{(-1)^i}{i!}.$$ Let $U$ be the set of all inappropriate gift exchange assignments, that is where someone receives themselves as the giftee. In particular, for each $k = 1, \dots, N,$ let $U_k$ be the set of assignments where $k$ receives herself as the giftee. Using the inclusion/exclusion principle, we have \begin{align*}|U| = |U_1 \cup U_2 \cup \dots \cup U_N| &= \sum_{i=1}^N |U_i| -\sum_{1 \leq i \lt j \leq N} |U_i \cap U_j| \\ &\quad\quad\quad+ \sum_{1 \leq i \lt j \lt k \leq N} |U_i \cap U_j \cap U_k | + \dots \\ &\quad\quad\quad\quad+ (-1)^{N+1} |U_1 \cap U_2 \cap \dots \cap U_N|.\end{align*} Now the $k$ summand in the above formula, e.g., $|U_{i_1} \cap U_{i_1} \cap \dots \cap U_{i_k}|$ counts all permutations where $i_1 \lt i_2 \lt \dots \lt i_k$ receive themselves as giftees leaving the other $N-k$ students free to explore all possible permutations. Therefore, we have $|U_{i_1} \cap \dots \cap U_{i_k}| = (N-k)!$, which is coupled with the fact that there are $\binom{N}{k}$ ways of choosing $i_1, \dots, i_k.$ So we have \begin{align*}|U| &= \binom{N}{1} (N-1)! - \binom{N}{2} (N-2)! + \dots + (-1)^{N+1} 0! \\ &= \sum_{i=1}^N (-1)^{i+1} \binom{N}{i} (N-i)! \\ &= N! \sum_{i=1}^N \frac{(-1)^{i+1}}{i!}.\end{align*} Since the number of total derangements would be the number of all permutations minus the non-derangements, we get $$!N = N! - |U| = N! \left(1 - \sum_{i=1}^N \frac{(-1)^{i+1}}{i!}\right) = N! \left( 1 + \sum_{i=1}^N \frac{(-1)^i}{i!} \right) = N! \sum_{i=0}^N \frac{(-1)^i}{i!}.$$ Pretty neat, if not anticlimactic, I guess.