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 |
No comments:
Post a Comment