The Roots of the Equation

So I was in my classroom last night with my boyfriend, waiting for his phone to charge before we went to dinner. Since we had some time, we played some of the math games I have in my room. (He’s a math PhD student, so he was all for it.) We played Set, of course, and then played a bit of 24. We idly wondered if it were possible to get 24 with any combination of 4 digits. So I looked at the box, and saw it came with 192 possible configurations. Well, if we determined how many possibilities there were (maybe there were 192), that might give us an idea of the feasibility.

So we tried to calculate how many configurations there were. Shouldn’t be too hard, right? Well, it kinda is, especially when you’re not already familiar with combinations with replacement. So we started using what we did know of combinations, but were stuck because we could use the same number multiple times, which made it trickier. Otherwise it would just be 9 C 4.

So, unsure how to solve, we tried to make a simpler case. What if we only had 2 digits to choose from, not 9? There’s there’s 5 possibilities. (1111, 1112, 1122, 1222, 2222.) And with 3 digits, there’s 15 (1111, 1112, 1113, 1122, 1123, 1133, 1222, 1223, 1233, 1333, 2223, 2233, 2333, 3333). We got a lot of fruitful thinking out of this, finding patterns, but didn’t really get closer to the answer. (Four digits had 35, btw. But we didn’t want to list all the ones for 5 digits and beyond.)

At this point it was time to go to dinner, so we put the whiteboard aside. But that couldn’t stop us thinking and talking about it, which we did as we walked to the restaurant and waited for out table, when we finally had a breakthrough.

Instead of trying to figure out the pattern with fewer digits but the same number of slots, let’s try to iterate up with the same number of digits, but using increasing number of slots. Let me explain, using 4 possible digits.

If we only have 1 number slot on the card, there are only 4 possibilities. (1, 2, 3, 4.) When we increase to 2 slots, we could start by putting a 1 in front of each of those possibilities. (11, 12, 13, 14). But, because order doesn’t matter, we can’t also put 2 in front of everything, because 21 is the same as 22. So we don’t use the one, and get 22, 23, 24. Same logic for 3 gives us 33, 34, and then finally 44.

This gives us a total of 10 possibilities. (4 + 3 + 2 + 1.) Now let’s think about 3 slots. In the same way, we can add a 1 in front of everything we’ve done so far. So for 3 digit possibilities there are 10 that start 1. Since we have to eliminate the four that two-digit configurations that have 1, there are 6 remaining, so that’s how many will start with 2. (3 + 2 + 1). Then three will start with 3. (2 + 1) And 1 will start with 4.

The process here is to add up all of what we had before, chopping off the start, to get the total number of new possibilities. So now, with 3 slots, we have 20 possibilities. (10 + 6 + 3 + 1.) To get for 4 slots, we use the same process: 20 start with 1, 10 start with 2 (6 + 3 + 1), 4 start with 3 (3 + 1), and 1 starts with 4, for a total of 35. Which is what we found before.

(If there were 5 slots, it would be 35 + 15 + 5 + 1, or 56.)

I don’t know of this recursive method of solving for combinations with replacements has been done before. I’m sure it is, but I haven’t found it in a very short google search. If someone knows of it, please let me know. But I wanted to share what I did. You can tell I love math, and so does my boyfriend, because we got completely distracted from a board game by solving a problem. He told me I’d make a good mathematician, because of how I tackled the problem. That may be true.