Here are two problems that have gotten me to think a lot.
The first one came from my Precalculus co-teacher James. We had been finishing up our unit on combinatorics and also creating new groups, and he devised a great question. So here’s the two-part problem I posed to my kids:
First Problem: We have a class of 14 students, with two groups of 3 and two groups of 4. If I were to have a computer program randomly create new groups: (a) what is the total number of different configurations/outcomes we could have? (b) what is the probability that your entire group was the exact same if you were in a 4-person group?
I thought I solved it successfully and was feeling really confident. Then James told me I was wrong. Then I tried but didn’t understand his logic. So I made a simpler case, and then I thought I understood it. My brain hurt so much. I kept switching back and forth between a couple different answers. It was marvelous! Finally, I felt like I understood things and felt confident. I shared it with my class, and lo and behold, a couple students got what I got, and a couple students didn’t. But the students who didn’t convinced me with their logic. And then I shared their thinking with James, who didn’t have the same answer, and he too was convinced. And I thoroughly enjoyed being wrong and telling the kids that this problem messed with my head, and they helped me see the light!
The second problem came from a student who emailed me about wanting to become a better problem solver. And they shared this old entrance exam for this summer camp they were thinking of possibly applying for, and wanted some guidance. The problem that I got nerdsniped by and ended up spending hours working on over Thanksgiving break was as follows:
This is from the 2019 entrance questions for a summer program. I think I was able to successfully solve (a) and (b). And then I think I solve (c) for n=3 and n=4 (and got an answer for n=5, but haven’t proved it is optimal). And I have no way to even start thinking about (d). But what I thought was lovely is how many different places my brain when went trying to think through this problem. And the neat geometric structure that arises out of the setup. (Even though I wasn’t able to fully exploit this structure in my thinking.)
I hope you enjoy thinking about these!
Sam, this is so cool. I’ve started playing with the Babab problem (you “nerd-sniped” me, as Rachel would call it.) I just came to the realization that the number of routes for part (a) is the number of edges of a n-dimensional cube – so mind-blowing! When I realized that for n = 4 the best way to visualize was a hyper cube I almost jumped for joy. Thank you for sharing.
OMG I’m so glad you had that insight! The moment when I saw that was so cool! So many things clicked. :)
For the problem 1a) I got 4204200=(14 choose 6)(6 choose 3)(8 choose 4).
For problem 1b) I got ~0.001998. Think of there being 14 slots that the 14 people are in. There are 8 slots that would put you in a 4-person group. Then 3 slots for person B, 2 for person C, and 1 for person D. That makes 8 * 3 *2 *1 / (14*13*12*11)
I’ve not looked at the second problem yet.
For problem 1a), not sure but shouldn’t this number, 4204200, be divided by 2*2 = 4 ? The two groups of 3 and the two groups of 4 are interchangeable. I had
14! ÷ (3! × 3! × 4! × 4! × 2 × 2) = 1051050
(14 choose 3) × (11 choose 3) × (8 choose 4) × (4 choose 4) ÷ (2 × 2) = 1051050
depending on how you view the problem.
Good point—the question is ambiguous. Since the groups were different sizes, I was assuming that there were 4 different projects, but if the groups of 3 are interchangeable and the groups of 4 are, then you are right that I overcounted by a factor of 4.
I’ve looked briefly at the second problem.
a) There are obviously 2^n islands and n 2^(n-1) ferry routes (n from each island, counted twice).
n=3 2 stores (aaa and bbb) max, as stores must have at least 3 letters different
n=4 again 2 stores, as all islands with at least 3 bs differ in at most 2 letters.
n=5 4 stores (e.g., aaaaa, aabbb, bbbaa, bbabb) I’m convinced of this result, but haven’t got a proof yet.
c) each store serves 1 + n islands, so you need at least ⌈2^n/(n+1)⌉ stores
n=3 2 stores needed: aaa, bbb cover everyone
n=4 at least 4 stores needed: aaaa, abbb, babb, bbab cover everyone
n=5 at least 6 stores needed: aaaaa, aabbb, bbbaa, cover everyone with 0, 1, or 2 bs
bbbbb, bbaaa, aaabb cover everyone with 5, 4, or 3 bs.
I’ve not looked at n=6 yet.