29 thoughts on “The Nation Has Problems: Vol. 6”

1. Spoiler	SelectShow
   My first inclination was that if Spooky manages to get only even cards, then he can never get to 21, but there are only 10 even cards in the deck. I feel like somehow the place to start is that story of Euler(?) needing to sum the first 100 digits and he did it by realizing there are 50 pairs that add up to 101.

   1. Yes, that is a very good thought!

      1. Nice to know I still have a little of that old math intuition left, however little it may be.

2. Spoiler	SelectShow
   If I pair 1-20, that's 21. If I pair 2-19, and so on, that's 21. There are ten pairs I could get, plus the 21 card itself. Given that I pick 11 cards, I either have to pick the 21 or make one of the pairs, so I can't possibly win. I never would have fallen for this trick, grifter!!!

   1. So we're on the same track. I think that's reassuring.

   2. Spoiler	SelectShow
      I should have tried this on someone more gullible, apparently. 🙂

   3. Spoiler

      SelectShow

      This is the same thing that I got, but I went through a much more convoluted construction to get there. Since spooky is choosing 11 cards from 21, at least one card (x) will have a value <11. To construct a winning hand, he would have to then avoid the card 21-x, which has a value >10. So now spooky has to choose 10 more cards, but has only 9 available cards with values >10 (21 and 21-x are not options). By the pigeon-hole principle one more card must be <11. You can repeat this until you come to the conclusion that, in order to win spooky must choose 11 cards with values <10. Since a winning hand cannot be constructed. Spooky cannot win.

      1. Spoiler	SelectShow
         Once you realize he can't win, a good related question is: What is the fewest number of ways he can lost? It's not too difficult a question when he picks 11 cards. If he picks 12 cards, it's (maybe) a bit harder.

3. OK, I've added a second problem with a similar flavor. This is one I came across a few weeks ago. It's harder than the first, but interesting!

4. For #2:

   Partitions don't have to be done in order, right? Like for A={1,2,3,4,5}, I can split the set A into partitions of {{1,5}, {2,4}, {3}}. It doesn't necessarily have to be {{1,2}, {3,4,5}} or anything like that. I guess what I'm saying is I can mix-and-match, right?

   1. Correct. So for n=5 it can be done as you described. For n<=4, however, some quick analysis will convince you it can't be done.

5. Whoops, I guess what you have doesn't work...but it can be done.

   1. Also, it has to be 3 sets. I mean, you can partition it into 2 sets, but then the third set would be empty and have a sum of 0, so that doesn't work...

   2. Yeah, sorry, n=5 wasn't meant to be an answer, just a point of clarification.

6. Here's what I have for #2 so far:

   Spoiler	SelectShow
   n = 3: doesn't work n = 4: doesn't work n = 5: { 5 }, { 4, 1 }, { 3, 2 } n = 6: { 6, 1 }, { 5, 2 }, { 4, 3 } n = 7: doesn't work n = 8: { 8, 4 }, { 7, 5 }, { 6, 3, 2, 1 } n = 9: { 9, 6 }, { 8, 7 }, { 5, 4, 3, 2, 1 } n = 10: ? I'm starting to see a bit of a pattern, but I need to finish 10 and 11, and possibly 12, to know for sure.

   1. Spoiler	SelectShow
      And I'm just realizing I missed a bunch of solutions when I did this before... Thinking about it now, I need to try and figure out how to do it in all the cases I missed.

      1. Spoiler	SelectShow
         Oh, and n=10 doesn't work for sure. n=11 does, though.

         1. Spoiler	SelectShow
            n=14 is the next case I'm unsure about.

            1. Spoiler	SelectShow
               I've solved it and figured out constructions for all cases. The constructions are rather tough...you can be proud of yourself if you manage to figure out why it can't happen in some cases. 🙂

7. Found a recursive set partitioner in Python. After some tweaking, I get a lot of sets:

   Spoiler

   SelectShow

   Sorry for the formatting, but it should be clear enough. (1, "doesn't work") (2, "doesn't work") (3, "doesn't work") (4, "doesn't work") (5, [set([5]), set([1, 4]), set([2, 3])]) (6, [set([1, 6]), set([2, 5]), set([3, 4])]) (7, "doesn't work") (8, [set([8, 4]), set([5, 7]), set([1, 2, 3, 6])]) (8, [set([8, 4]), set([2, 3, 7]), set([1, 5, 6])]) (8, [set([8, 1, 3]), set([5, 7]), set([2, 4, 6])]) (9, [set([9, 6]), set([8, 7]), set([1, 2, 3, 4, 5])]) (9, [set([9, 6]), set([8, 2, 5]), set([1, 3, 4, 7])]) (9, [set([9, 6]), set([8, 3, 4]), set([1, 2, 5, 7])]) (9, [set([9, 6]), set([8, 1, 2, 4]), set([3, 5, 7])]) (9, [set([1, 5, 9]), set([8, 7]), set([2, 3, 4, 6])]) (9, [set([1, 5, 9]), set([8, 3, 4]), set([2, 6, 7])]) (9, [set([9, 2, 4]), set([8, 7]), set([1, 3, 5, 6])]) (9, [set([9, 2, 4]), set([8, 1, 6]), set([3, 5, 7])]) (9, [set([1, 2, 3, 9]), set([8, 7]), set([4, 5, 6])]) (10, "doesn't work") (11, [set([1, 10, 11]), set([8, 9, 5]), set([2, 3, 4, 6, 7])]) (11, [set([1, 10, 11]), set([8, 9, 2, 3]), set([4, 5, 6, 7])]) (11, [set([1, 10, 11]), set([9, 6, 7]), set([8, 2, 3, 4, 5])]) (11, [set([1, 10, 11]), set([9, 2, 4, 7]), set([8, 3, 5, 6])]) (11, [set([1, 10, 11]), set([9, 2, 5, 6]), set([8, 3, 4, 7])]) (11, [set([1, 10, 11]), set([9, 3, 4, 6]), set([8, 2, 5, 7])]) (11, [set([9, 2, 11]), set([8, 10, 4]), set([1, 3, 5, 6, 7])]) (11, [set([9, 2, 11]), set([8, 1, 10, 3]), set([4, 5, 6, 7])]) (11, [set([9, 2, 11]), set([10, 5, 7]), set([8, 1, 3, 4, 6])]) (11, [set([9, 2, 11]), set([1, 10, 4, 7]), set([8, 3, 5, 6])]) (11, [set([9, 2, 11]), set([1, 10, 5, 6]), set([8, 3, 4, 7])]) (11, [set([9, 2, 11]), set([10, 3, 4, 5]), set([8, 1, 6, 7])]) (11, [set([8, 11, 3]), set([1, 2, 10, 9]), set([4, 5, 6, 7])]) (11, [set([8, 11, 3]), set([10, 5, 7]), set([1, 2, 4, 6, 9])]) (11, [set([8, 11, 3]), set([1, 10, 4, 7]), set([9, 2, 5, 6])]) (11, [set([8, 11, 3]), set([1, 10, 5, 6]), set([9, 2, 4, 7])]) (11, [set([8, 11, 3]), set([2, 4, 10, 6]), set([1, 7, 5, 9])]) (11, [set([8, 11, 3]), set([1, 2, 10, 4, 5]), set([9, 6, 7])]) (11, [set([8, 1, 2, 11]), set([9, 10, 3]), set([4, 5, 6, 7])]) (11, [set([8, 1, 2, 11]), set([10, 5, 7]), set([9, 3, 4, 6])]) (11, [set([8, 1, 2, 11]), set([10, 3, 4, 5]), set([9, 6, 7])]) (11, [set([11, 4, 7]), set([9, 10, 3]), set([8, 1, 2, 5, 6])]) (11, [set([11, 4, 7]), set([1, 2, 10, 9]), set([8, 3, 5, 6])]) (11, [set([11, 4, 7]), set([8, 1, 10, 3]), set([9, 2, 5, 6])]) (11, [set([11, 4, 7]), set([1, 10, 5, 6]), set([8, 9, 2, 3])]) (11, [set([11, 4, 7]), set([1, 2, 3, 10, 6]), set([8, 9, 5])]) (11, [set([11, 1, 3, 7]), set([8, 10, 4]), set([9, 2, 5, 6])]) (11, [set([11, 1, 3, 7]), set([2, 4, 10, 6]), set([8, 9, 5])]) (11, [set([11, 5, 6]), set([9, 10, 3]), set([8, 1, 2, 4, 7])]) (11, [set([11, 5, 6]), set([1, 2, 10, 9]), set([8, 3, 4, 7])]) (11, [set([11, 5, 6]), set([8, 10, 4]), set([7, 1, 2, 3, 9])]) (11, [set([11, 5, 6]), set([8, 1, 10, 3]), set([9, 2, 4, 7])]) (11, [set([11, 5, 6]), set([1, 10, 4, 7]), set([8, 9, 2, 3])]) (11, [set([11, 5, 6]), set([2, 3, 10, 7]), set([8, 1, 4, 9])]) (11, [set([1, 11, 4, 6]), set([9, 10, 3]), set([8, 2, 5, 7])]) (11, [set([1, 11, 4, 6]), set([10, 5, 7]), set([8, 9, 2, 3])]) (11, [set([1, 11, 4, 6]), set([2, 3, 10, 7]), set([8, 9, 5])]) (11, [set([11, 2, 3, 6]), set([8, 10, 4]), set([1, 7, 5, 9])]) (11, [set([11, 2, 3, 6]), set([10, 5, 7]), set([8, 1, 4, 9])]) (11, [set([11, 2, 3, 6]), set([1, 10, 4, 7]), set([8, 9, 5])]) (11, [set([2, 11, 4, 5]), set([9, 10, 3]), set([8, 1, 6, 7])]) (11, [set([2, 11, 4, 5]), set([8, 1, 10, 3]), set([9, 6, 7])]) (11, [set([11, 1, 2, 3, 5]), set([8, 10, 4]), set([9, 6, 7])]) (12, [set([11, 3, 12]), set([9, 10, 7]), set([1, 2, 4, 5, 6, 8])]) (12, [set([11, 3, 12]), set([1, 10, 6, 9]), set([8, 2, 4, 5, 7])]) (12, [set([11, 3, 12]), set([9, 2, 10, 5]), set([8, 1, 4, 6, 7])]) (12, [set([11, 3, 12]), set([1, 2, 4, 10, 9]), set([8, 5, 6, 7])]) (12, [set([11, 3, 12]), set([8, 1, 10, 7]), set([9, 2, 4, 5, 6])]) (12, [set([11, 3, 12]), set([8, 2, 10, 6]), set([1, 7, 4, 5, 9])]) (12, [set([11, 3, 12]), set([8, 1, 2, 10, 5]), set([9, 4, 6, 7])]) (12, [set([11, 3, 12]), set([1, 2, 10, 6, 7]), set([8, 9, 4, 5])]) (12, [set([11, 3, 12]), set([10, 4, 5, 7]), set([8, 1, 2, 6, 9])]) (12, [set([11, 3, 12]), set([1, 10, 4, 5, 6]), set([8, 9, 2, 7])]) (12, [set([1, 2, 11, 12]), set([9, 10, 7]), set([8, 3, 4, 5, 6])]) (12, [set([1, 2, 11, 12]), set([9, 10, 3, 4]), set([8, 5, 6, 7])]) (12, [set([1, 2, 11, 12]), set([8, 10, 3, 5]), set([9, 4, 6, 7])]) (12, [set([1, 2, 11, 12]), set([10, 3, 6, 7]), set([8, 9, 4, 5])]) (12, [set([1, 2, 11, 12]), set([10, 4, 5, 7]), set([8, 9, 3, 6])]) (12, [set([12, 10, 4]), set([9, 11, 6]), set([1, 2, 3, 5, 7, 8])]) (12, [set([12, 10, 4]), set([1, 11, 5, 9]), set([8, 2, 3, 6, 7])]) (12, [set([12, 10, 4]), set([11, 1, 2, 3, 9]), set([8, 5, 6, 7])]) (12, [set([12, 10, 4]), set([8, 11, 7]), set([1, 2, 3, 5, 6, 9])]) (12, [set([12, 10, 4]), set([8, 1, 11, 6]), set([9, 2, 3, 5, 7])]) (12, [set([12, 10, 4]), set([8, 2, 11, 5]), set([7, 1, 3, 6, 9])]) (12, [set([12, 10, 4]), set([2, 11, 6, 7]), set([8, 1, 3, 5, 9])]) (12, [set([12, 10, 4]), set([11, 3, 5, 7]), set([8, 1, 2, 6, 9])]) (12, [set([12, 10, 4]), set([1, 2, 11, 5, 7]), set([8, 9, 3, 6])]) (12, [set([12, 10, 4]), set([11, 1, 3, 5, 6]), set([8, 9, 2, 7])]) (12, [set([1, 10, 3, 12]), set([9, 11, 6]), set([8, 2, 4, 5, 7])]) (12, [set([1, 10, 3, 12]), set([9, 2, 11, 4]), set([8, 5, 6, 7])]) (12, [set([1, 10, 3, 12]), set([8, 11, 7]), set([9, 2, 4, 5, 6])]) (12, [set([1, 10, 3, 12]), set([8, 2, 11, 5]), set([9, 4, 6, 7])]) (12, [set([1, 10, 3, 12]), set([2, 11, 6, 7]), set([8, 9, 4, 5])]) (12, [set([1, 10, 3, 12]), set([11, 4, 5, 6]), set([8, 9, 2, 7])]) (12, [set([9, 12, 5]), set([1, 10, 11, 4]), set([8, 2, 3, 6, 7])]) (12, [set([9, 12, 5]), set([11, 2, 3, 10]), set([8, 1, 4, 6, 7])]) (12, [set([9, 12, 5]), set([8, 11, 7]), set([1, 2, 3, 4, 6, 10])]) (12, [set([9, 12, 5]), set([8, 1, 11, 6]), set([2, 3, 4, 10, 7])]) (12, [set([9, 12, 5]), set([8, 11, 3, 4]), set([1, 2, 10, 6, 7])]) (12, [set([9, 12, 5]), set([8, 1, 2, 11, 4]), set([10, 3, 6, 7])]) (12, [set([9, 12, 5]), set([2, 11, 6, 7]), set([8, 1, 10, 3, 4])]) (12, [set([9, 12, 5]), set([11, 1, 3, 4, 7]), set([8, 2, 10, 6])]) (12, [set([9, 12, 5]), set([11, 2, 3, 4, 6]), set([8, 1, 10, 7])]) (12, [set([1, 4, 12, 9]), set([10, 11, 5]), set([8, 2, 3, 6, 7])]) (12, [set([1, 4, 12, 9]), set([11, 2, 3, 10]), set([8, 5, 6, 7])]) (12, [set([1, 4, 12, 9]), set([8, 11, 7]), set([10, 3, 2, 6, 5])]) (12, [set([1, 4, 12, 9]), set([8, 2, 11, 5]), set([10, 3, 6, 7])]) (12, [set([1, 4, 12, 9]), set([2, 11, 6, 7]), set([8, 10, 3, 5])]) (12, [set([1, 4, 12, 9]), set([11, 3, 5, 7]), set([8, 2, 10, 6])]) (12, [set([9, 2, 3, 12]), set([10, 11, 5]), set([8, 1, 4, 6, 7])]) (12, [set([9, 2, 3, 12]), set([1, 10, 11, 4]), set([8, 5, 6, 7])]) (12, [set([9, 2, 3, 12]), set([8, 11, 7]), set([1, 10, 4, 5, 6])]) (12, [set([9, 2, 3, 12]), set([8, 1, 11, 6]), set([10, 4, 5, 7])]) (12, [set([9, 2, 3, 12]), set([11, 4, 5, 6]), set([8, 1, 10, 7])]) (12, [set([8, 12, 6]), set([10, 11, 5]), set([1, 2, 3, 4, 7, 9])]) (12, [set([8, 12, 6]), set([1, 10, 11, 4]), set([9, 2, 3, 5, 7])]) (12, [set([8, 12, 6]), set([11, 2, 3, 10]), set([1, 7, 4, 5, 9])]) (12, [set([8, 12, 6]), set([1, 11, 5, 9]), set([2, 3, 4, 10, 7])]) (12, [set([8, 12, 6]), set([9, 2, 11, 4]), set([1, 10, 3, 5, 7])]) (12, [set([8, 12, 6]), set([11, 1, 2, 3, 9]), set([10, 4, 5, 7])]) (12, [set([8, 12, 6]), set([11, 3, 5, 7]), set([1, 2, 4, 10, 9])]) (12, [set([8, 12, 6]), set([1, 2, 11, 5, 7]), set([9, 10, 3, 4])]) (12, [set([8, 12, 6]), set([11, 1, 3, 4, 7]), set([9, 2, 10, 5])]) (12, [set([8, 12, 6]), set([1, 2, 3, 4, 5, 11]), set([9, 10, 7])]) (12, [set([8, 1, 12, 5]), set([11, 2, 3, 10]), set([9, 4, 6, 7])]) (12, [set([8, 1, 12, 5]), set([9, 11, 6]), set([2, 3, 4, 10, 7])]) (12, [set([8, 1, 12, 5]), set([9, 2, 11, 4]), set([10, 3, 6, 7])]) (12, [set([8, 1, 12, 5]), set([2, 11, 6, 7]), set([9, 10, 3, 4])]) (12, [set([8, 1, 12, 5]), set([11, 2, 3, 4, 6]), set([9, 10, 7])]) (12, [set([8, 12, 2, 4]), set([10, 11, 5]), set([7, 1, 3, 6, 9])]) (12, [set([8, 12, 2, 4]), set([9, 11, 6]), set([1, 10, 3, 5, 7])]) (12, [set([8, 12, 2, 4]), set([1, 11, 5, 9]), set([10, 3, 6, 7])]) (12, [set([8, 12, 2, 4]), set([11, 3, 5, 7]), set([1, 10, 6, 9])]) (12, [set([8, 12, 2, 4]), set([11, 1, 3, 5, 6]), set([9, 10, 7])]) (12, [set([8, 1, 2, 3, 12]), set([10, 11, 5]), set([9, 4, 6, 7])]) (12, [set([8, 1, 2, 3, 12]), set([9, 11, 6]), set([10, 4, 5, 7])]) (12, [set([8, 1, 2, 3, 12]), set([11, 4, 5, 6]), set([9, 10, 7])]) (12, [set([1, 12, 6, 7]), set([10, 11, 5]), set([8, 9, 2, 3, 4])]) (12, [set([1, 12, 6, 7]), set([11, 2, 3, 10]), set([8, 9, 4, 5])]) (12, [set([1, 12, 6, 7]), set([9, 2, 11, 4]), set([8, 10, 3, 5])]) (12, [set([1, 12, 6, 7]), set([8, 2, 11, 5]), set([9, 10, 3, 4])]) (12, [set([1, 12, 6, 7]), set([8, 11, 3, 4]), set([9, 2, 10, 5])]) (12, [set([2, 12, 5, 7]), set([1, 10, 11, 4]), set([8, 9, 3, 6])]) (12, [set([2, 12, 5, 7]), set([9, 11, 6]), set([8, 1, 10, 3, 4])]) (12, [set([2, 12, 5, 7]), set([8, 1, 11, 6]), set([9, 10, 3, 4])]) (12, [set([2, 12, 5, 7]), set([8, 11, 3, 4]), set([1, 10, 6, 9])]) (12, [set([12, 3, 4, 7]), set([10, 11, 5]), set([8, 1, 2, 6, 9])]) (12, [set([12, 3, 4, 7]), set([9, 11, 6]), set([8, 1, 2, 10, 5])]) (12, [set([12, 3, 4, 7]), set([1, 11, 5, 9]), set([8, 2, 10, 6])]) (12, [set([12, 3, 4, 7]), set([8, 1, 11, 6]), set([9, 2, 10, 5])]) (12, [set([12, 3, 4, 7]), set([8, 2, 11, 5]), set([1, 10, 6, 9])]) (12, [set([1, 2, 4, 12, 7]), set([10, 11, 5]), set([8, 9, 3, 6])]) (12, [set([1, 2, 4, 12, 7]), set([9, 11, 6]), set([8, 10, 3, 5])]) (12, [set([3, 12, 5, 6]), set([1, 10, 11, 4]), set([8, 9, 2, 7])]) (12, [set([3, 12, 5, 6]), set([9, 2, 11, 4]), set([8, 1, 10, 7])]) (12, [set([3, 12, 5, 6]), set([8, 11, 7]), set([1, 2, 4, 10, 9])]) (12, [set([3, 12, 5, 6]), set([8, 1, 2, 11, 4]), set([9, 10, 7])]) (12, [set([1, 2, 12, 5, 6]), set([8, 11, 7]), set([9, 10, 3, 4])]) (12, [set([1, 2, 12, 5, 6]), set([8, 11, 3, 4]), set([9, 10, 7])]) (12, [set([1, 3, 4, 6, 12]), set([10, 11, 5]), set([8, 9, 2, 7])]) (12, [set([1, 3, 4, 6, 12]), set([8, 11, 7]), set([9, 2, 10, 5])]) (12, [set([1, 3, 4, 6, 12]), set([8, 2, 11, 5]), set([9, 10, 7])]) (12, [set([12, 2, 3, 4, 5]), set([9, 11, 6]), set([8, 1, 10, 7])]) (12, [set([12, 2, 3, 4, 5]), set([8, 11, 7]), set([1, 10, 6, 9])]) (12, [set([12, 2, 3, 4, 5]), set([8, 1, 11, 6]), set([9, 10, 7])]) (13, "doesn't work") (14, [set([8, 13, 14]), set([2, 11, 12, 10]), set([1, 3, 4, 5, 6, 7, 9])]) .... There are a lot of solutions for n=14.

   1. Spoiler	SelectShow
      So far, it looks like n = 7, 10, 13, 16(?), ... there might be no solutions.

      1. Spoiler	SelectShow
         Nice! And that is correct. These partitions are by no means unique. Can you come up with a good reason why it doesn't work for 7, 10, 13, etc.?

         1. Spoiler	SelectShow
            It has to be the case that the sum of the integers needs to be divisible by 3 for it to work, so where the sum of 1-6=21, adding 7 to that results in a sum not divisible by 3. So where the set for n=y works, set n=y+1 can only work if y+1 is divisible by 3. n=5 works, n=6 works, n=7 cannot work.

   2. I count 761 solutions for n=14 and 1480 solutions for n=15. There could be some double counting. I'll try 16-19 next. Counting the 1-15 case took 9.33 minutes, so I expect this one to take at least that long.

      1. I imagine counting these things would be a beast. I'm not sure there's even a good way to do it. When I tried to come up with solutions, I tried to do it in a way that was generalizable for all of the related cases.

         Spoiler	SelectShow
         There are 4 different cases and they all need to be treated somewhat differently. The cases are n=0,2,3,or 5 mod 6. If n=1 mod 3, then it doesn't work.

         1. I killed it at 130 minutes. I don't know how long it took to determine 16 wouldn't work, but it was still on n=17. I have a ton of computing resources available here at work, but I would first need to translate the code to C or Fortran and try to parallelize it.

            1. Yeah, this thing is going to grow exponentially. There are 3^n possible ways to partition into 3 sets. I have some idea of how I would try to prove the number of possible solutions, but I'm not sure how fruitful it would be.

8. Problem 1.
   I wrote this at about 8am, but then the renewal that I thought had been put to bed last Thursday needed more work. So tomorrow, I'll finally get to the things that I thought I'd have all day last Friday to work on. Famous last words, right?

   Spoiler

   SelectShow

   The probability is zero. For N from 1 to 10, there is a card in the set valued 21-N. If Spooky's 11 cards contain any pair of N and 21-N, then Spooky loses. As there are ten such pairs, a necessary condition for Spooky to win would be at most one card from each pair. However, Spooky draws 11 cards, so the only way for him to avoid drawing both cards from such a pair is to pick the only unpaired card, the 21 (which is an automatic loss, assuming that "any combination" = one card). QED.

   I'm interested how to calculate this probability when Spooky has to draw fewer cards, or if the cards would be 0 to 20 or 0 to 21.

   1. We did it the exact same way.

Comments are closed.