Sunday, December 28, 2008

Dispatches from Vietnam: #2 - Shopping

There are lots of interesting things to buy here in Hanoi, and most of them are really cheap. In downtown Hanoi the streets had all sorts of street vendors on them. One thing you can get for very cheap here is DVDs - I got the first four seasons of The Office for only 100,000 VND (about $6). However when I got home I found out that it was actually the British version, not the American one (which was surprising because the front cover clearly displayed the characters from the American version).

But anyway, I have decided that my main goal for shopping in Vietnam is to get items that look like they belong in Amtgard, so I could use them or sell them at an Amtgard event. (Also it makes it a lot more fun to walk around if I'm actually looking for something.) I got a very cool looking silk robe that looks like it would be perfect for Amtgard for only $18 (this person actually took US dollars). Today, I went to a "craft village," a village full of stores that all sell the same kind of product. The one I went to was a pottery village. There was a whole road full of stores and then when I got to the end, there was an open-air market with even more stuff to buy. At one of the merchants I saw a basket full of small decorated bottles that could easily be magical healing potion bottles. I asked how much they were and the merchant held up two fingers. I at first thought this meant two dollars each but it turned out it meant 2,000 VND (about $0.12) each, so I got a whole bunch of them. I also got a small sculpture that llooked kind of like a castle for 60,000 VND (about $4).

Friday, December 26, 2008

Dispatches from Vietnam: #1 - Traffic

I will be in Vietnam for the next couple weeks visiting my parents, so I'll be blogging about interesting things I see there. One of the first things you notice in Vietnam is that there are few cars; there are mostly motorbikes. But the most amazing thing is that there are very few traffic lights and traffic laws are not well enforced. For example, at most intersections, traffic from two perpendicular directions will travel through the intersection simultaneously, and people will just avoid each other in the middle. Even in intersections which do have traffic lights what often happens is that on the road that has a red light, traffic going from each direction will spill out from their side over the entire road (rather than staying to their side like they do in ths U.S.) creating two opposed "walls" of motorbikes. Then when the light turns green, both sides will go at the same time!

Surprisingly, there are few crashes. Part of this may simply be due to the relatively slow speeds that traffic travels at (rarely more than 30 mph or so, at least on the parts that we've been on so far) but part of this may be due to the method used to punish drivers who are the cause of accidents. Apparently, in any crash, the driver of the larger vehicle is considered to be at fault. And, since Vietnam does not have a well-developed court system like in the U.S., they use the next best alternative: all the bystanders will pull the driver out of his car and beat him up. (Of course, this makes drivers in Vietnam much more careful than drivers in the U.S.)


At least in the context of traffic accidents, how does the Vietnamese justice system compare to the American justice system in terms of efficiency, cost, and effectiveness at deterring harmful behavior? Are there lessons that the U.S. could learn from Vietnamese experience in this area?

Sunday, December 21, 2008

Holiday Math - Bonus Problem!

Also in the spirit of the holiday season, I present a new math problem relating to Christmas gift-giving. This doesn't have anything to do with gaming, but it's still too good to pass up.

Bonus Problem: Divvying Up the Loot, Modern-Day Edition

The "white elephant gift exchange" protocol, featured in an episode of NBC's "The Office", is a procedure used for distributing Christmas gifts at large gatherings. In the protocol, each of the N participants brings a gift, for a total of N gifts, which are all placed into a central pile. The participants are numbered from 1 to N. The protocol consists of N rounds.

In the I'th round of the protocol, the following steps take place:

1. Player I selects a gift and places it in front of him. He can select a gift either from the central pile or any of the gifts in front of other players.
2. If he selects a gift from the central pile, the round ends. If he selects a gift from another player, then that player (who just had his gift taken) now has the option of choosing a gift, again either from the central pile or from another player. If he takes a gift from another player, then that player also has the option of choosing a gift as described. This process continues until someone chooses a gift from the central pile, at which point the round ends.
3. Once a gift has been selected, it cannot be selected again until the beginning of the next round.

After all N rounds have been completed, each player gets to keep the gift that is in front of them.

Is it possible that after this protocol is completed, there will be two people (A and B) who each prefer the gift that the other one ended up with to the one he ended up with? (Assume that each participant has a strict preference ordering over the available gifts, and that each time a participant makes a selection, that he chooses the gift he most prefers out of those that are available for selection.)

Saturday, December 20, 2008

RPG Math - Problem 4

It's time for more RPG Math again! This time, in the spirit of the holiday season, this puzzle is based upon that elusive goal that motivates almost every D+D adventurer - and underpins much of the activity in our real-world economy during the holiday season. That's right, I'm speaking of nothing other than treasure, money, and loot!

Problem 4: Divvying Up The Loot

The Dungeons and Dragons 3.5 edition rulebook contains a section on suggested methods for dividing up treasure. In this section, the book uses an example of a party of four adventurers (A, B, C, and D) who have stumbled across a treasure hoard consisting of 5,000 GP (gold pieces) and a magical shield. It suggests (paraphrased):

If two or more players want the shield, they should bid [on how much it is worth to them]. The highest bidder gets the shield, and the value is added in to the treasure stash when calculating each player's share of the loot. Then everyone gets an equal share, and the player who gets the shield has his amount of gold deducted by that amount. For example, if A won the bidding with 800 GP, then the total treasure size is 5800 GP, so each person gets 1450. That means A would get 650 GP and the shield, while B, C, and D would get 1450 each.

The maximum that a player can bid is his share of the treasure. For example, in this case, A could bid at most 1250 GP (one-fourth of the total of 5000 GP.) In this case, A would end up with the shield while the others would split up the 5000 GP worth of gold.

What is wrong with this section?

Answer is here.

Friday, December 19, 2008

The semester is over!

The semester is over! I finally finished the last final. I had three final exams this semester. The Topology final had eight problems and I had to choose six of them to complete. This was a good thing because there werw two of the problems that I couldn't figure out how to do. Then the Complex Analysis final was a lot easier because this final had way more problems than you actually had to do. There were about 700 or 800 points worth of problems on the test (each problem had a different point value) and you just had to do at least 400 points worth of problems. Also if you do more then incorrect answers don't count against you, so it provides a "buffer zone." (This is similar to what one of my old Computer Science professors did.) The Numerical Analysis final was the hardest because it didn't have any "skippable" problems. That one is the only one that I'm not sure how well I did - out of three problems on the test, I completed a total of 21/8 problems. (Two of the problems had four parts. On one of the problems I missed half of one part, on the other problem I missed a whole part because time ran out.)

Wednesday, December 17, 2008

RPG Math - Problem 3

Problem 3: Take Cover!

For this problem, we will say a line segment A crosses a line segment B if the following statements hold:

1. A and B are not parallel.
2. A intersects B.
3. The point at which A intersects B is not one of the endpoints of A.


In Dungeons & Dragons 3.5 edition, battle takes place on a square grid in which each character occupies one square. Some of the boundaries between squares are considered "walls" and cannot be seen through. A defender D is considered to be in the line of sight of attacker A if there exists a point in the attacker's square (including boundaries) and a point the defender's square (including boundaries) such that the line between those two points does not cross any wall. A defender D is considered to have cover from attacker A if for every corner of A's square, there exists a corner of D's square such that the line between those two points crosses a wall.

Now the questions:

3.1. Show that there exists a battlefield configuration such that A has line of sight to D and D does not have cover from A, but every line between an interior point of A's square and an interior point of D's square crosses a wall.

3.2. Suppose we remove condition (3) in the definition of crossing. (In fact, the D+D rule book is not clear on whether condition (3) should be in there.) Now show that there exists a battlefield configuration such that D has cover from A, but no line between an interior point of A's square and an interior point of D's square crosses a wall.


Now suppose we specify that instead of so-called "paper-thin" walls that just go along boundaries of squares, walls take up entire squares or contiguous groups of squares. Now we say a line segment A crosses a wall B if either of the following conditions hold:

1. The line segment A contains an interior point of B.
2. The line segment A crosses a boundary of B.

3.3. Solve problem 3.1 with these new conditions.
3.4. Solve problem 3.2 with these new conditions.


Solution to this problem is here.

Saturday, December 13, 2008

Seduced by Amazons?

"Open the case."

-Howie Mandel


I am currently in Seattle after having finished interviews with I have already been offered a full-time position but went over to talk to them and find out whether this was someplace I want to work. Pertinent information I found out was as follows:

  1. Amazon is divided up into several "organizations," and each organization has several "teams." I talked to two organizations (Distributed Systems Engineering and Financial Systems) and two to three teams within each organization. I found one team (Customer Experience Analytics, which analyzes data from how customers use to find out how to improve the Web site to generate more sales) that I want to work at, but I am not particularly interested in any of the other teams that I met with.
  2. It is not possible to lock in a position on a particular team when you choose to join. Instead, you select an organization. If you do not select an organization one will be selected for you. Then when you get closer to the start date (about a month or so out) you get to choose a team from all the teams that have openings. Of course the teams that have openings are constantly in flux, so there is no way to know what teams will be available when it comes time.
  3. The deadline date for accepting the offer is December 19. Thus I will have no idea which graduate schools I will get into when accepting this offer. I analogized this situation to "Deal or No Deal", because I have to decide whether to take the "Deal" at Amazon before knowing enough information about it.
  4. I talked to my recruiter about this situation and he said that one possibility is to decline this offer, and then in May 2009 call again to see what teams are available, and join a team if there's a team with openings then I want to be on. (they have already evaluated my qualifications so I don't have to go through the interview process again.) Of course there's always the chance that all the spots will be full by then. The way I think about it is that this option is a dominant strategy: if all the teams I want fill up by then, then I wouldn't want to work at Amazon anyway, while if not, then I can still get an offer.

I will probably ask my recruiter again about what happens if I sign the offer letter now, and then when the time comes find out that there aren't any teams I want to work on, but the above option is probably what I'm going to do. So in a few months, I'll find out what was in the "cases" that I opened. (I think one of the other students I was with, when I mentioned it being like "Deal or No Deal," said something about opening a door to find out what prize is behind it. I reminded him that doors as a device to hide prizes in game shows were outdated 20 years ago, and the only reason anyone remembers them is because of the associated math problem.)

Sunday, December 7, 2008

RPG Math - Problem 2

Problem 2: Too Many Men on the Playing Field

The HERO System is a role-playing game system designed to allow players to play superheroes. In the system, each character is given a point value, and he can use the points to buy powers, abilities, and stats. For the purposes of this problem, there are two powers that are important:

Followers - This power allows a character to have other characters as allies. The player can select the number of allies as well as the point value of those allies. The point cost of this power is computed as follows:

  • 1/5 of the point value of the ally characters. For example, a 50-point ally costs 10 points.
  • If the ally has a point value exceeding that of the original character, an additional cost equal to the difference in points. For example, if a 100-point character has a 150-point follower, that costs the character 80 points (30 points for 1/5 of the cost, plus an additional 50 points)
  • If there is more than one ally, a 5 point increase for each doubling of the number of allies. For instance, two 50-point allies costs 15 points, four 50-point allies costs 20 points, eight 50-point allies cost 25 points, etc.
Followers may not themselves have Followers, but they may have Duplicates.

Duplicates - This power allows a character to make multiple copies of himself. The cost of this power is 1/5 of the point value of the character for a single duplicate, and a 5 point increase for each doubling of the number of duplicates. For example, a 100-point character would pay 20 points for one duplicate, 25 points for two duplicates, 30 points for four duplicates, etc.

Duplicates may not have their own Followers or Duplicates.

Now the question: What is the maximum number of "units" (counting the original character and any Followers and Duplicates) that a 100-point character can field?

Here is the solution.

Saturday, December 6, 2008

RPG Math - Problem 1

I just finished taking the Putnam examination, a college math competition that lasts a whole day. There are two parts, and each part has 6 questions that you complete in 3 hours. Each question is graded out of 10, so there are a maximum of 120 points. The median score is usually 1-2 out of 120, but this time (at least the person running the competition told me) it could be as high as 10 because there were a couple problems that were really easy.

Anyway, this is as good a time as any to start a new feature of the blog: "RPG Math," a series of math problems based on actual scenarios from role-playing games.

Problem 1: Ineligible Receiver (of bullets) Downfield

In the tabletop wargame "Necromunda" (as well as several other similar games) a unit is only allowed to shoot at the closest enemy unit to him. (The game is played on a tabletop; there is no grid or 'game board' of any kind, and rulers are used for measuring distances.) Describe a simple way of determining which of two enemy units is closest to a particular friendly unit without actually measuring any distances. (You may use a compass and straightedge.)

Here is the solution.

Friday, December 5, 2008

What's this about a recession?

"Researchers at Harvard say that taking a power nap for an hour in the afternoon can totally refresh you. They say that by the time you wake up you'll feel so good, you'll be able to start looking for a new job."

- Jay Leno


I just learned that I have been offered a full-time job at as a Software Development Engineer for after I graduate. On December 11-14 I will be traveling over there in order to tour the campus, learn about what a great place Amazon is to work, and talk to different project teams to find out which ones I might want to work on.

I have also been offered an internship at the U.S. Census Bureau's Statistical Research Division to start sometime in January. There, I could quite possibly be working with some of the people responsible for the development of the "imputation" techniques that were the subject of a 2002 Supreme Court case.

Thursday, December 4, 2008

Media Watch: LARP Edition

"Should have gone to
And found out that those bankers were a bunch of ticking bombs.
We could have checked their credit and found out their loans won't work
But now we have to bail out a bunch of freakin' jerks."

- The Capitol Steps, "Free Credit", on the Wall Street bailout


Last week, I saw the movie "Role Models," which features live-action role-playing as a critical plot element. Although, like all movies, the movie takes some artistic license (for example, a melee-only battle in which each participant had only one life would certainly not last anywhere close to the whole day, and no LARP that I know of allows you to kick a defenseless opponent in the chest) it was still a fun movie to watch.

Also, here are two LARP-related commercials:

This commercial for Old Spice deodorant featuring Brian Urlacher.

This commercial for which does not feature LARPs, but does feature a renaissance faire, which I imagine is close enough.

CONSUMER ALERT:'s service is not as free as they say it is. They sign you up for a 30-day trial of a $14.99/month credit monitoring service, and if you fail to opt out by the end of the 30 day period they start charging you. The site allows you to get your credit reports for free with no hidden charges or other shenanigans.

Monday, December 1, 2008

Searching for hidden treasure (not related to geocaching or D+D)

"I think I just failed a Spot check."

- Belkar Bitterleaf, "Order of the Stick", by Rich Burlew


This article in Slate discusses a Supreme Court case in which a police officer was summoned to a domestic disturbance and when he got there, the husband was not home. The wife claimed her husband was dealing drugs and allowed the cop to search the house. During the search the husband got home and demanded that the search stop. The cop did not stop the search and eventually found drugs. The question of course is whether or not it was a legal search because the wife agreed to it, even if the husband did not.

One hypothetical situation that was not discussed in the article was: what would have happened if the husband did not show up before drugs were found, and only later claimed that the search was illegal because the wife did not have the authority to consent for him? If this would be considered illegal, then if I were a drug dealer, I would make sure to have an accomplice waiting in the wings to swoop down and claim the drugs were his when the police found them in a "consented" search, thus making the search illegal. The police would have no way to know about this plan in advance (even if they asked me, I could tell them that all the stuff in my house was mine, and the accomplice could argue that my false statement does not mean that the violation of his rights was legal). Therefore, the only way for the police to protect themselves against this tactic would be to wait for a warrant (if they had probable cause) even if the subject consents. This would significantly inconvenience innocent subjects, because they would have to be detained until a warrant was issued - even if they had nothing to hide and were perfectly willing to let them search right then and there!

If you accept the argument of the husband in this case that the wife did not have authority to consent for him, then presumably this fact would not depend on whether or not he happened to return in the middle of the search, so you would end up with the conclusion above.

Amtgard News #1

"You don't need to pass an IQ test to become a senator."

- Sen. Mark Pryor (D-AK), during an interview with Bill Maher


In my Amtgard group, I am currently running unopposed for the position of Champion, which involves designing the battlegames to be played and running them. However despite me being the only candidate running, there are a couple steps I need to go through. The first step is passing a "reeves test," which is a test on the rules of the game. This is a pretty easy test to pass because it's exactly the same test every time, you only need 75% to pass, and the questions aren't that hard. Nevertheless three of us took the test and one of them failed it (fortunately that person was not me). There was also a "vote of confidence" which I passed.

The next step is to qualify in the A&S (Arts and Sciences) competition. This is a competition where you enter your creations in several different categories (weapons, armor, art, performance, writing, etc.) In order to qualify, you have to submit entries that receive a passing grade (3 or more points out of 5) in at least two categories. You can submit in as many categories as you want.

The competition is on Dec. 13, and I am planning on submitting the following items:

1. (Fiction Writing) A fictional account of a debate between two candidates for "monarch," the leader of the group, based on the real presidential debates. For example one candidate will accuse the other of supporting "earmarks" based on his support of spending money on catering food at an event.

2. (Nonfiction Writing) An essay about common aspects of Amtgard rules that lead to disagreements, and how to reduce them. I plan to use this article (which I learned about from here) as part of my argument. The article describes a real court case in which a drug dealer faced a harsher sentence if the deal occurred within 1000 feet of a school, and the debate centered on whether this was to be measured "as the crow flies" or along the path one would walk to get there. My point is that it is impossible to come up with a set of rules that precisely defines allowable actions in every situation, and the best way to proceed is, rather than to try to outlaw specific "unfair" actions, to change the rules in such a way that it isn't worthwhile to do those actions in the first place. (An illustrative example is the "forward progress" rule in football. The intended purpose is to stop defenders from essentially grabbing the ball carrier and pushing or carrying him as far back as possible. Rather than trying to define some rule about how much is "excessive push-back", they simply decided to spot the ball at the farthest point forward the ball carrier reached, eliminating the incentive for the unwanted tactic in a way that does not involve any subjective judgments.)

3. (2D art) An advertising poster for Amtgard as if it were a video game. It will include "review" statements like "by far the most realistic graphics of any game ever" and "you'll feel like you're in the action!"

4. (3D art) A model of a spinnerbox from Fable II. This will even have working spinners.

Applying to Graduate School

William Gasarch: "It's generally not a good idea to go to the same university for graduate school as undergraduate, because different schools expose you to different ideas. For example, at the University of Maryland, there's almost nobody studying computer hardware. So there's not going to be a class where you solder chips together."

Vibha Sazawal: "Actually, some of my students do."

Gasarch: "But as you can see, the fact that I didn't know that demonstrates how little emphasis there is on hardware here.

- Two computer science professors giving students advice about graduate school


So I am almost finished applying to graduate school. The only thing I have left to do is I gave my personal statement to one of my professors to look at. I will be getting it back later this week and then will revise and resubmit it to the colleges. (Colleges currently use an online application system - you don't have to physically send anything to the colleges. They let you "submit" and pay the application fee before you have all the materials in, and they recommend you do that so that they can start looking at the parts you do have in before they get the rest. You can upload the new personal statement all the way up until the application deadline.)

I am applying to MIT, Carnegie Mellon, UIUC, and the University of Maryland. I am also going to apply to the AMSC program at Maryland, though I haven't submitted that application yet. That one is not due until next semester.