30 thoughts on “The Nation Has Problems: Vol. 10”

1. Ah - there's a name I know. Lagrangian points are an important concept in astronomy.

   1. Ah. How? How? How.

      httpv://youtu.be/Vppbdf-qtGU

2. Spoiler	SelectShow
   30, 30, 14, 4 39, 21, 7, 1

   To be honest, this was guess and check. But it only took me five minutes.

3. To be honest, I feel like including the \(0^{2}\) term is cheating. I could say that any number can be written as the sum of 100 squares if 95 of them are \(0^{2}\).

   1. I don't think that the impressive part is supposed to be a large amount of squares. It's supposed to be how few squares it takes. For instance, each positive number cannot be written as the sum of three squares.

      1. That is correct.

         In most cases, I don't think the expression as a sum of 4 squares is unique. In most cases, there are many, many numbers that work. For instance, the solutions that Beau got above are both different than the two I got.

         Using 0 is sometimes necessary to make it work. For instance, \(3 = 1^2 + 1^2 + 1^2 + 0^2\) and that's the only way to do it.

         1. I get why \(0^{2}\) is useful, I just thought that it seemed like the rule should be "4 or fewer squares" instead of strictly 4 and using some filler.

            1. You could say that--it's an equivalent problem.

4. Spoiler: part 1	SelectShow
   30, 30, 14, 4 29, 27, 21, 1 Looking at a list of the squares to put these sums together. No real method.

5. I'm not sure where to start yet with #2, but something like that needs to appear in a Spookymilk Survivor strategy season.

   1. My first inclination that Player 2 was in the driver's seat due to there being an even number in each row was thwarted by the fact I still cannot parse instructions in math problems properly.

      1. That's my intuition, too.

         He just needs to stop the path at one spot, which doesn't seem too difficult. It seems like he'd want to try and force the larger numbers toward the outside as well, as that doesn't give the first player as many options.

   2. That site has put up some interesting math games. They're rather difficult, though.

      1. Yeah, I'd simplify it for the sake of SS.

6. I've got #2, I think.

   1. Spoiler

      SelectShow

      The second player can always win. Here's the idea: Consider the following squares where \((i,j)\) represents the square in the \(i\)th row and \(j\)th column. (1,1),(1,2) (2,2),(2,3) (3,3),(3,4) (4,4),(4,5) (5,5),(5,6) Note that these squares block any path leading from the bottom to the top. If the second player can make sure that none of these squares are the squares colored black, then he wins. Doing this should be pretty easy, but there are some different cases to consider. (a) If the first player plays in one of these squares, play in one of the other squares in the same row that is not listed above with a larger number. (b) If the players plays in one of the first 5 rows in a square other than the ones listed, play a number in one of the listed squares in the same row that's listed with a smaller number. (c) If the first player plays in the 6th row, then just play something else in the 6th row. It is easy to see that one of these things will always be possible.

      1. Thought I had a way around this. Turns out not. This works for me (and is a bit more elegant than what I have below).

         1. It's exactly the same idea as what you have, just a bit simpler. I don't think there's a way around it.

            1. there isn't. I just had to carry out one scenario to show myself that it worked.

      2. Spoiler

         SelectShow

         I'd like to generalize this idea further and it's pretty easy in a lot of cases. I think any time \(n\ge m-1\) and \(n\ge 5\) this should work just by drawing a diagonal across the board, since the second player can always effectively block one square. If \(n\) is odd though, this might not quite work. Even in something like a \(4\times 2\) board, I haven't quite figured out if the second player can win, but I suspect that he can't.

      3. Very nice. What about proving that the strategy is optimal? (It isn't really clear to me what is meant by "optimal" in this case.)

         1. No clue about what is meant by "optimal". I've almost completely solved this game.

            Spoiler	SelectShow
            The second player can win when there are at least 3 rows and at least 3 columns. Analysis coming soon!

            1. Oops.

               Spoiler	SelectShow
               Make that, at least 4 columns.

            2. Spoiler

               SelectShow

               The idea is the same as before. We need to pick a set of "key squares". The key squares will be any set of squares such that the first player cannot win unless at least one of them is black. We'll further require that there are at least as many non-key squares in each row as key squares. Player 2's strategy is as follows: (a) If player one plays in a key square, player two plays in a non-key square in the same row with a larger number. (b) If player two plays in a non-key square in a row that still has key squares available, the second player plays a smaller number in one of the key squares. (c) If neither of the first two things happens, the second player plays at random in such a way that there are still as many non-key squares as key squares in each row. Part (c) requires some additional analysis which I will neglect. You can convince yourself it's possible. Note that if player 2 sticks to this strategy, none of the key squares can be the largest at the end of the game. Next, we need to show that we can find such a set of key squares so long as there are at least 3 rows and 4 columns. Perhaps the easiest way to do this is as follows (1) The rightmost floor(n/2) squares in the first row are key squares; (2) The leftmost floor(n/2) squares in the third row are key squares; and (3) The middlemost 2 or 3 squares in the second row are key squares. (2 if n is even, 3 if n is odd) If there are only 2 columns, then the game is a forced win for the first player, regardless of how either player plays. If there are 3 columns, then our construction above doesn't work because we need at least 2 key squares in one of the rows, leaving at most 1 non-key square. This still doesn't mean player two doesn't have a winning strategy, it just means that this strategy doesn't work. Same goes if there are only two rows. I suspect that player 2 has a winning strategy in any grid with more than 2 columns.

               1. Spoiler	SelectShow
                  Note that this strategy works "approximately" if the order in which the players play is reversed. The only difference is that the first player would need to play randomly in such a way that he doesn't create too many non-key squares in a row. For instance, it would fail with a 3x4 grid.

                  1. Spoiler

                     SelectShow

                     So Mike can win the case where there are exactly 3 columns. This works independently of who goes first. The idea is to make sure the highest entry is never in the rightmost column for each row. If this is true, then Mike will win. He can do this as follows. (1) If he's the first to play in a row, play in the rightmost column. Once your opponent plays in one of the other two columns, put a larger number in the remaining spot. (2) If your opponent plays first in a row, make a play so that there is a number in the rightmost column and that number is smaller than the other number. This can be done regardless of where your opponent plays.

7. Spoiler: part 2

   SelectShow

   Randall (player 2) should always play in the same row as Mike. For the first two times in each row it doesn't matter what numbers either of them play, since Randall will always have the opportunity to create the largest number in the row (since he gets the even numbered turns) Can Mike (player 1) keep 2 squares open in each row such that a path is possible? Either 1. Mike puts his 2 numbers on the edges in which case Randall has free reign in the middle to cut off a possible path. eg. (0 = empty square, X = filled) XXX00X X0XX0X X00XXX in the above case Randall always puts in a number greater than the other 5 in the row and no path can be drawn. or 2. Mike leaves one of the edge squares open and Randall can make that the highest number and then cut off any possible pathway in the next row. (there are only 2 available squares to move to from an edge square, Randall can fill both of them the first two times he plays in the row, and then set the largest number elsewhere with his final turn). Thus, Mike cannot keep a possible pathway open if Randall plays in the same row every time, so Randall will always win employing this strategy.

   1. Spoiler	SelectShow
      I think you have the same basic idea as me, but I'm having a little bit of a hard time following your strategy. Both of our strategies seem to rely on the same key, though. Play in the same row and block the path.

      1. I've got lots of 6x6 grids drawn on my scratch paper that might make it clearer. Or maybe not.

8. Problem 1:

   Spoiler	SelectShow
   \(2012=43^2+9^2+9^2+1^2=30^2+30^2+14^2+4^2\) \(2012=42^2+12^2+10^2+2^2=39^2+21^2+7^2+1^2\) via brute force (though it wasn't that hard, three minutes maybe?)

Comments are closed.