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.