The Nation Has Problems

The Nation Has Problems: Vol. 7

40 Comments

About Last Month

Once I thought about the first problem for a while, it brought me to remember another problem that I had come across recently, so I added it.

1. Twenty-one cards containing the integers from 1 to 21 are shuffled and placed face down on a table. Spooky then picks 11 of these cards and flips them over. Spooky loses if the sum of any combination of cards sums to 21. What is the probability that Spooky wins this game?

One of the things that makes this problem just a little bit tricky is the statement of the problem. As it turns out, there is no chance of him winning the game, so stating it as a probability question is a bit of a trick. Second, we don't need to consider all possible ways he could make 21, only a few are needed.

We first notice that if Spooky draws 21, then he automatically loses. So let's assume he doesn't. Then, he must draw 11 cards from the numbers between 1-20. Let's break them into the following 10 sets:

{1,20}, {2,19}, {3,18}, ... ,{10,11}

Since there are 10 sets and he must draw 11 cards, by the pigeonhole principle, he must pick two cards from the same set. But the cards in any one of these sets sums to 21, so he loses. Note that if he only has to draw 10 cards, then he can win. For instance, he can pick the cards 11,12,13,14,15,16,17,18,19,20.

2. For what values of n can the numbers 1,2,3,...,n be partitioned into 3 sets such that the sum of the numbers in each set is the same.

Let's say the sum of each set is k. Then the sum of all three sets is 3k. However, the sum of all three sets is also 1+2+...+n=n(n+1)/2. This gives n(n+1)/2=3k or n(n+1)=6k and so n(n+1) must be a multiple of 6. This happens if n=0,2,3, or 5 (mod 6) or equivalently n=0 or 2 (mod 3). One can check by hand that it is not possible for n=2 or 3 and n=1 and n=4 don't work by the above argument. So we must also have n >=5.

As it turns out, these conditions are sufficient as well, which is not surprising given the many ways we could potentially partition the set when n is large. I will use two different techniques to construct these sets, which I will call grouping and snaking. Both methods work if n=6k for some integer k, so I will use that case to demonstrate the two techniques.

The simpler method is the method of grouping. The idea here is to group all the numbers into sets so that each set as the same sum, then distribute the sets to our three partitions. If n=6k, then we group {i,6k+1-i} together so that each set has sum 6k+1. This gives us 3k sets, so we can distribute k sets to each of our three partitions. For instance, if n=12 then we have {[1,12],[2,11]}, {[3,10],[4,9]}, {[5,8],[6,7]}. Here, I'm using extra brackets within the partitions so that you can see how they were grouped originally.

The technique of snaking works much like snaking in a fantasy sports draft. We start at one end, putting one (or more) number in each box and then work our way backward. Let's do this for n=18.

Partition 1 Partition 2 Partition 3
1 2 3
6 5 4
7 8 9
12 11 10
13 14 15
18 17 16

Notice that if we look at the first two rows, the sum of the numbers in each partition is 7. For the next group of two rows, the sum is 19 and so forth.

Now, let's attack the other cases. If n is 5 mod 6, then we will wish to use the technique of grouping. In this case, however, we'll let n be in a group by itself and then pair off {i,n-i} for i=1,2,...n-1. For instance, if n=11 our groups would be {1,10},{2,9},{3,8},{4,7},{5,6},{11}. This gives us 6 groups, so we can put two into each partition.

Next, we'll try n=2 mod 6. In this case, we're going to use snaking, but we're going to group 1,2 and 3 together and treat them as a single entity. Rather than getting real technical with a proof, let's look at an example where n=20.

Partition 1 Partition 2 Partition 3
4 5 6
8 7 1,2,3
9 10 11
14 13 12
15 16 17
20 19 18

For n=3 mod 6, the technique is almost exactly the same, except we'll group 1,2,3 and 4 as a single entity. For example, n=21 looks like this:

Partition 1 Partition 2 Partition 3
5 6 7
10 9 8
1,2,3,4 11 12
15 14 13
16 17 18
21 20 19

These are by no means the only way to partition the sets. As Sean pointed out, there are many, many ways to do this once n=14 and the numbers of ways to do it will grow exponentially. For a bonus problem this week, try to come up with another technique for partitioning these numbers. In all likelihood, you'll have to break it into cases based on what n is mod 6.

The problems

These hat guessing game problems are fun, so let's try some of them this month!

1. Two players are each given either a red hat or a blue hat. They can each tell what color hat the other person is wearing, but don't know what color they are wearing. Before they get their hats, they are allowed to discuss a strategy, but may not communicate after they receive their hats. They are also required to guess simultaneously, so they can't infer anything from the other person's guess. Show that it is possible for them to develop a strategy such that at least one player is always right.

Side note: In such a strategy, it is never possible for both players to be correct, so the strategy will always involve one person guessing correctly and the second guessing incorrectly.

2. Now n players are sitting in a circle and each is given a hat. Given the same assumptions, if there are k differently possible colors of hats, show that it is possible for the players to come up with a strategy such that at least floor(n/k) of them are right. The floor function is the smallest integer less than or equal to that number. For instance, floor(7/3)=2, floor(5)=5, and floor(17.1)=17.

40 thoughts on “The Nation Has Problems: Vol. 7”

    1. Year-end financials approval this morning, then I've read the WW post-mortem.
      I'll probably obsess about this for the afternoon and post something half-baked before I leave for the day or after midnight.

  2. If the first question allows for any combination of red or blue hats, then yes, I'm stumped. I'm looking forward to kicking myself at this one. I get the sense there's something that'll seem obvious when I hear it.

    1. Yeah, I think so. Because it wouldn't make sense if there was always only one red and one blue hat, because then you always just have the opposite of your partner.

  6. Spoiler: Problem 1 SelectShow

  7. Darn, I meant to add a way to use LaTeX formulas before your next post. I'll try to do it tonight.

    1. That would be awesome!

      I'm out of good stock problems for next month. I'll need to think hard about these and I'm willing to take suggestions from anybody has them.

    2. Testing:

      $$x = {-b \pm \sqrt{b^2-4ac} \over 2a}.$$

      Edit: I didn't expect it to be centered like that.

      Testing again:

      $$x = {-b \pm \sqrt{b^2-4ac} \over 2a}.$$

      Yep, always centered. Hmmm.

        1. me too! that's that thing that we're supposed to know! without interneting... quadratic equation?

          1. Yep. Bonus points if you know the cubic equation! (I don't)

            You can always reduce your cubic to something of the form $$ax^3+bx +c=0$$ by "completing the cube" to get rid of the $x^2$ term. Then, you can do something and get one solution. Once you get one solution, it's easy to get the other two by factoring and using the quadratic equation.

      2. The double dollar sign always creates a new paragraph as well as centering. Is the another way to enter math mode?

        Let's try something: \begin{math}x\equiv 0 \pmod 4\end{math}.

          1. Yep, that did it. That's a backslash ('\') followed by an open parenthesis and then another backslash and close parentheses to end it. I'll try to add the single dollar sign as an alias for that.

      1. Ok, here's a more substantial hint:

        Spoiler SelectShow

      1. Note:

        Spoiler SelectShow

  9. For #2:

    Spoiler SelectShow
    1. Spoiler SelectShow

  10. Is this post the reason I keep getting a strange pop-up about mathJax not loading properly?

  11. They must be Rangers fans.

    #1:

    Spoiler SelectShow

    #2: Just some thinking.

    Spoiler SelectShow

Comments are closed.