In the tradition of my Holiday MathPuzzles, I’m here with an appropriately themed puzzle for this time of year.
It’s that time of year all right. You’re out and about, trick or treating with your friends or family and when you come home, you decide to dump all the candy out on the floor to sort through it. But then, as siblings often do, you begin to bicker about who has “more” than the other. In fact, there are some candies that you really like, and some you don’t like. You’d rather have a bunch of chocolate than a bunch of peppermints, for instance. But wait a minute! Of course you can’t like the same thing! Your sibling actually likes peppermints!
Here’s a table of the different candies you have. Each candy has a “value” to it; that is, how much you “want” it. Try to split up the candies such that you and your sibling both have as equal value as possible at the end. And no fighting!
So I don’t know if anyone else is familiar with this game, but I just remember playing it with friends in middle school and it occurred to me the other day that it would be an interesting game to analyze combinatorially, and perhaps write a game playing algorithm for. This game can be found in more detail here: http://en.wikipedia.org/wiki/Chopsticks_(hand_game)
Rules of Play: Players each begin with two “piles” of points, and each pile has 1 point to begin with. We used fingers to represent this, one finger on each hand.
On each turn, a player can choose to do one of two things:
Send points from one of the player’s pile to one of the opponents piles. So if Player 1 wanted to send 1 point to Player 2’s left pile, then Player 2 would have 2 points in the left pile and Player 1 would still have 1 point in his left pile. Player 1 does not lose points, they are simply “cloned” over to the opponents pile.
If the player has an even number of points in one pile and zero points in the other pile, the player may elect to split his points evenly between the two piles. This consumes the player’s turn. Example: if Player 1 has (0 4) then he can use his turn to split his points, giving him (2 2).
If a player gets exactly 5 points in either pile, that pile loses all of its points and reverts to 0. However, if points applied goes over 5 (such as adding 2 points to a 4 point pile), then the remainder of points are added. (meaning that 4 + 2 = 1). The opponent simply gets points mod 5.
If a player gets to 0 points in both their piles, then they lose. The last person that has points remaining wins.
Okay, so let’s break this down. Here’s an example game for those of you that are more visually oriented (follow the turns by reading left to right, moves are marked with red arrows):
Okay, so let’s point out a few things about this game.
On turn 4, player 2 adds 3 points to player 1’s 2 points, making 5. The rules state that any pile with exactly 5 points reverts to zero.
On turn 7, player 2 adds 3 points to 3 points. as we all know, but , so player 1 now has one point in his pile.
On turn 13, player 2 decides to split his points, turning his one pile of 4 into two piles of 2. This consumes his turn.
On turn 15, player 2 adds 2 points to player 1’s 3, thus reverting his pile to zero. Player 1 now has no more points to play with, so player 2 wins.
We can think about this game as a combinatorial problem. What are the optimal positions to play? How would one program a computer to play this game? I plan to create an interactive web game where players can try this for themselves.
That time of year is upon us once again, and what better way to celebrate than by doing a few holiday-themed puzzles?
#1: You brought home the perfect tree to decorate; however, it can only hold 10kg of decorations before the branches start to sag and it falls over. In addition, you can’t have too many items on the tree, there’s only so much space. Because of this, you only can hang 25 decorations of any kind at one time. These are the decorations you have available:
Type of Decoration
Coverage (% of tree covered, each)
Tinsel (limit 1)
Angel Topper (limit 1)
Popcorn String (limit 1)
Lights (limit 1)
We want to get the most covered tree we can without going over the weight limit. What is the lightest and most covered tree combination you can find?
So I didn’t post yesterday because I was travelling. I was at SNCURCS this weekend (apparently it is pronounced “snickers”, which was news to me) to present some work that I did at my REU last summer. I was pretty nervous because I thought that I didn’t remember the work very well since its been a while since last summer.
As it turned out, the talk went fairly well, even though I had to speed through my slides and risk losing people due to the time constraints. I also realized that \today in LaTeX does in fact print the current date, but only at the last time you compile it. So it ended up the date on my slides showed up as the day before, but no big deal. The group of people that I was presenting with also did graph theory related projects, so I thought that was pretty cool. I saw an interesting presentation about quantifying and mapping not only our social networks, but also our “meta-network”, which includes shared knowledge and the like. Network science sounds like pretty interesting stuff after hearing him talk about it.
My problem that I presented on was based on a variation of the game Nim but played on mathematical graphs. Instead of removing tokens from a pile we can remove a number of edges connected to a single vertex in the graph. The player that removes the last edge is the winner. We used these rules to analyze and determine the Sprague-Grundy number, or nimber of different states in the game and different types of graphs. I’m planning to do a whole post on this one of these days.
A side note: I’m realizing that this post-every-day schedule has led to some good ideas and writing experience but also has led to (in my opinion) a drop in quality. It was a learning experience for sure, but I’m not going to push myself to get out a post every day for the rest of the month I think. I have graduate school applications and school and work that I need to attend to. I’ll still be posting, I’ll just save up until I have a few good ones. Thanks for reading!
Tomorrow I’m giving a talk about my research. I’m cozied up in my hotel room, and ready for a good sleep and hot breakfast in the morning if we’re being honest. It wasn’t a bad drive down here (3 hours), but I felt like I was racing the sun the whole way, because I was arriving just as it had gotten dark. Nature always wins.
Things haven’t been going too well personally, but giving this presentation tomorrow will be good research experience. It’s called Champion Spiders in the Game of Graph Nim, and involves a modification of a classic game to give it a graph theory bent. It’s pretty interesting stuff.
Come back tomorrow and I’ll talk about it in more detail.
Not feeling like writing much today either. It’s been a tough day.
Making a hangman solving program would be pretty cool. I guess its sort of like an anagram solver in reverse, if that makes sense. We don’t have the word, we are trying to create the word based on a few known letters. Determining what letters are most common in certain positions and finding patterns of words (“ing”, “ed”, “ion”) would be helpful. Compare the current game state with a dictionary to make guesses about the word. Not really a fleshed out idea. Probably coming back to this one.
I think its interesting to think of how we can implement computer programs to “solve” different types of games.