good times
Mood: happy
Posted on 2006-09-22 23:06:00
Tags: math
Words: 636

- We went to game night tonight and had a lot of fun. We played three games, all of which are guaranteed to terminate! Although the proof for the last one was a little tricky to come up with. Here are the rules:

You start with a stack of cards. There may also be cards in front of you, and cards on the table (that anyone can access). On your turn, you start one of two ways:
a) Drawing two cards from the stack
b) Drawing a set of cards from the table (not from in front of you).
Then, you do one of two things:
1) Play one card from your hand to the table (not in front of you)
2) Play a set of cards from your hand to in front of you.
If you started your turn with b), you must end it with 2), and you must play those cards you drew from the table to in front of you (along possibly with cards from your hand).

Given these rules, can you prove the game terminates? (the game terminates when the stack of cards is depleted, or some other condition that isn't relevant here)

So I first tried to show that the number of cards in the stack plus the total number of cards in everyone's hand must decrease on every turn (which means eventually the number of cards in the stack will go to 0, which ends the game). This, however, is not true: if you pick up cards from the table then play them in front of you (with no additions from your hand), that stays constant.

So, someone pointed out that the flow of cards is unidirectional: they always flow in the direction of

stack -> someone's hand -> table -> in front of someone

(sometimes they jump around, but they always go from left to right). So you can formalize this by showing that the sum

N^3*(number of cards in stack) + N^2*(total number of cards in everyone's hand) + N*(number of cards on table) + (total number of cards in front of someone)

is decreasing on every turn for sufficiently large N. It turns out that N=20 or so is sufficiently large, since that's the most number of cards that can be played in front of someone in one turn.

- djedi seems to be happy about work, which is nice. I'm excited about the project I'm working on.

- I've been going to the gym every other day, and lifting weights at my computer the other days (we've been playing a lot of WoW recently and it's convenient to do during downtime). I gained some weight last week mostly due to a batch of delicious brownies that I ate in like two days, but I'm back down to the previous weight already. (and I had two donuts for lunch on Thursday...and then I discovered "cookie time"!)

- We're going to the Maryland Renaissance Festival (weird that they picked the domain rennfest.com, although renfest.com was already taken: why not marylandrenfest.com or something?) tomorrow, which should be fun. The weather has nice (if a little chilly at times) so hopefully it'll be a beautiful day and not rain like my forecastfox is suggesting.

random: Last year a Japanese company had Sotheby's and Christie's compete for the right to sell their paintings by playing rock, paper, scissors. Christie's won by consulting teenage daughters of an executive, who came up with the correct strategy. Note that they got around the usual "on 3 or after 3?" question by having the combatants write down their choice on a sheet of paper. (via kottke via girlhacker)

I have the top Google Images result for her extra legs. Awesome!

Also, I've been extremely out at work and there haven't been any problems and I feel pretty good about that.

This backup was done by LJBackup.