Monday, March 22, 2010

A Mathematical Bridge Problem

Playing a spade contract, you reach trick 10 in your hand to see the following four card configurations:

Dummy holds: ♠ - ♥ AQJ ♦ - ♣ A
You hold: ♠ 2 ♥ 2 ♦ 2 ♣ 2

How do you play to maximize your chance of getting all of the last four tricks? Assume that the only point card left is the king of hearts and there is a diamond higher than the 2 in one of the opponents' hands.

Obviously it depends on your situation, so say that the following happened: your partnership started with 21 high card points between you and during play LHO has played 16 points and RHO has played none. Does this change your answer? What are the probabilities now?

Does your answers change depending on which of the following situations happened?
  • Neither opponent bid during the auction
  • LHO opened an artificial 1♣ showing 16+ points
  • LHO opened a standard bid showing 13-21 points. Does it matter what bid it was?
I'm not sure of the answer to this question, so I'm interested to see what the readers of my blog think.

Tuesday, March 2, 2010

Medalia de Aur

As some of you know, I went to Târgu Mureş, Romania for the Central European Olympiad in Informatics. This year, I went to Bucharest, Romania for the Romanian Masters in Mathematics. The team consisted of Allen Yuan, Vlad Firoiu, Sam Keller, Tim Chu, Albert Gu, and myself, headed by coaches Po-Shen Loh and Yi Sun.

Two days before we were to leave, Po-Shen sent us an email that, among other things, notified us that Lufthansa was currently experiencing a strike and that if our flight out of DC was canceled, the entire trip would be also. Obviously, this did not sit well with us, as we were all strongly looking forward to the trip.

Luckily, the strike was called off before we left, although Lufthansa was still short pilots, so some of the flights got canceled, but ours wasn't one of them. The flights to Bucharest actually went pretty well, including the AMC B. I did worse on the B than the A, but it really doesn't matter. I took it mainly because I figured everyone else would also and I didn't want to be bored for those 75 minutes. Tim had gotten a 96 on the A and was worried that he didn't qualify for AIME, and he wasn't exactly relieved when he got a 96 on the B as well.

On the trip there, we were expecting to be housed at Hotel Moxa, a 4 star hotel in Bucharest. However, it turns out that it was actually Complex Moxa, which is used for college dorms and is just an annex of the hotel or something. The rooms were pretty unfortunately bad, but ours had a TV in it! (the others apparently didn't). Because of the 7 hour time difference, the Olympics were on after all of the events for a day ended, which was extremely convenient. I definitely watched more of the Olympics while in Romania than any other time.

Sam checking out the room
We also found out that the complex didn't have an open wireless access point....But Vlad had this USB thing that allowed him to get internet access in Romania. It's called Zapp or something. At least we had internet access, even though it was pretty bad.

The next day we still weren't competing. We got our first taste of Romanian breakfast, which included an interesting tea (I think it was purple) that tasted pretty good, as well as some cheese. Being American, we obviously thought the portions were way too small so we ate masses of bread with oil and vinegar.

Our first Romanian breakfast
After breakfast, we met our guides and went to the high school where we would be taking the contest in the following two days. After touring the school and dropping in on a ``superior algebra'' class, the guides asked us if we wanted to go into the gym to play some sports. Inside, there were lots of people from various teams playing volleyball, but the court was pretty full so we didn't join them. Instead, we saw a ping-pong table, but nobody had any paddles, so we started playing basketball while we waited for a guide to retrieve paddles from the complex.

For some reason, someone thought it would be a good idea to play outside, even though there were huge puddles of water on the ground and the court was not very even. There were also ping-pong tables outside, but they looked pretty bad. They were really low, weren't flat, and the nets were actually iron fences.

China plays on them anyway
Eventually we got some paddles and played some ping-pong, as did the Chinese. The Chinese team didn't know much English and the only Chinese speakers were on the US team as either a student or a coach, so they spent a lot of time with us (and also Allen and Tim were in a room with two of them).

At some point we went back to our room to hang out until dinner, after which would be the opening ceremony. But as we were just starting to chill in our room, our guides came up to inform us that the opening ceremony got moved from 2000 to 1600, and we had to go back to the school.

The opening ceremony was actually quite nice. Only a small part of it was dual-run in Romanian and English. All of the guest speakers spoke in English, so translation was unnecessary, and they also all kept it very short. It made the opening ceremony much shorter than what I expected.

The next day was competition day 1.

Go go go!
I read the problems and solved 1i on sight, as did the rest of the team except for Vlad, who apparently took 1.5 hours on it. I then spent a bit of time on 1ii, but wasn't quite getting the details. I figured it would be easy anyway and went to do number 2 before finishing.

Number 2 was dispatched rather readily, and at this point I had about 3 hours left, if I remember correctly. I drew the diagram for 3 (although I actually drew the wrong diagram, thinking ``external'' meant that the quadrilateral was external to the circle, rather than the circle is external to the quadrilateral), wrote down some random stuff, and went back to 1ii. After all, surely a number 1 number theory would be easier for me than a number 3 geometry, right?

So it turned out that I didn't solve 1ii, and didn't have anything worth partial on 3, whoops. In the last 5 minutes I wrote down some stuff for 1ii that I figured had no hope of working, but it turned out to be extremely close to the correct solution. I left the room thinking ``Man, I'm going to have to tell the rest of the team that I didn't solve number 1.''

So talking with the others after day 1, it seemed initially that most of them had solved two problems: either 1 and 2 or 1 and 3. The exceptions were Allen, who solved only 1i and 2, and Sam, who solved only 1. After talking a bit more, however, Albert determined that his 1ii was completely wrong, and so he had only solved 1.5 problems as well. After day 2, we would find out that during coordination the coordinators had thought that Albert's solution had worked too, and Yi and Po-Shen had to tell them it was wrong to keep the spirit of the contest.

Allen and I both had essentially identical progress on 1ii, and since it was so close to the correct solution, we came out of coordination with 6s...somehow. The graders were apparently pretty lenient with scoring.

Day 1 Scores
IDNameP1P2P3Total
USA1Timothy Chu77014
USA2Vlad Firoiu73717
USA3Albert Gu30710
USA4Brian Hamrick67013
USA5Sam Keller7007
USA6Allen Yuan67316

After day 1, we just went back to our room to hang out, being exhausted from the competition. Nothing much interesting happened. We just watched the Olympics and played card games, mostly.

We woke up the next day for day 2 of the competition.

No geometry! Wooo!

So I read the day 2 problems and I thought ``YES! There's no geometry! Let's get a 21 on day 2! Oh wait, these problems look time consuming. 4.5 hours might not be enough...'' Anyway I looked at problem 4 and killed it in about 20 minutes. I start working on problem 5 and it dies in another 50 minutes or so. At this point it's about 1050 and I have two complete solutions written up and I'm starting to think maybe number 6 is really hard and they gave us two really easy problems to compensate (a la IOI day 1).

So I spend the next 3 hours trying various stuff on number 6, but I don't do the thing that actually leads to a solution because it looked stupidly messy. Oh well. I wrote up what I had (which wasn't exactly the cleanest thing in the first place), and then turned in the test. When I was leaving the room, I figured I probably had a pretty standard result on day 2.

However, when I talked to the rest of the team, I found out that I could hardly be more wrong. They had all solved problem 4 (except Albert, who got a 0 on day 2, unfortunately), but nobody else had solved problem 5. I was really surprised. Tim thought he solved problem 6, but none of us could really verify it since he was the only one who felt that he had made significant progress.

Later in the day, we found out (with our awesome Chinese-speaking skills) that CHN1 had been the only Chinese team member to solve either 5 or 6 (and he solved both (and CHN was really Shanghai, not all of China)). Apparently 5 was supposed to be very difficult. I still don't really see why.

After day 2, we went to the mall to play some laser tag! Except that the game was actually pretty lame. At first there was only like one person on the red team, so it was just walking around for a while until the person running the thing decided to restart it. Unfortunately, the respawn time was still around 3 seconds, so whenever you killed someone they could just follow you until they respawn and kill you immediately. It made for a pretty annoying game.

We got back to the complex pretty late, so we missed the normal dinner and had to order pizza, and our discussion of day 2 with Yi and Po-Shen was at around 2230, way later than we expected.

Day 2 Scores
IDNameP4P5P6Total
USA1Timothy Chu72514
USA2Vlad Firoiu7209
USA3Albert Gu0000
USA4Brian Hamrick77418
USA5Sam Keller7209
USA6Allen Yuan7209

The awards ceremony was the day right after day 2. But before that, coordination had to happen. So to get rid of us pesky contestants for a while, they sent us to the village museum: a collection of traditional Romanian houses. It would have been a really cool experience, but the ground was extremely muddy and it was simply unpleasant to walk around.

When we got back it was time for the awards ceremony. Well, almost. It was actually delayed for half an hour. Anyway, the awards ceremony, just like the opening ceremony, was very quick. The speakers knew that we didn't want to listen to a bunch of long speeches (and it was hard to understand some of their English anyway), so they went straight to the awards. Albert was the first USA competitor called up for honorable mention (solving at least one problem perfectly).

Next up was the bronze medals. There were a lot of bronzes, and Sam was among them. I was actually pretty nervous during the bronzes because I wasn't sure if I had screwed up something on day 2, in which case I would probably be in the low end of silver. As the bronzes ended, I breathed a sigh of relief.

The bronze medalists
Silvers started getting called now, and I was preparing to go up. They called the other three, and after a bit I handed my camera to Albert, expecting to be called up at any point. but the number of silver medals remaining was very clearly diminishing, and then they stopped. Stunned, I almost missed taking a picture of the silver medalists. At this point, I was just amazed.

The silver medalists
The gold medals started being announced, starting with the Chinese perfect scorer. Then the other gold medalists, and finally ending with me. The suspense was incredible. After going up to receive my gold medal, my hands were incredibly shaky. I could barely take pictures of the remainder of the ceremony, where China handed the trophy over to Russia (RMM has one trophy that the winning team keeps until another team ousts them), and then a few more short words.

After the award ceremony, Po-Shen informed us that the reason the awards ceremony was delayed was because they had to argue for my solution to #5 for about an hour. There was a step that I thought was obvious and Po-Shen thought was obvious, but the graders disagreed. Apparently they had to call in a third party to give an impartial opinion. Eventually, though, they agreed to give me a 7. Lesson from this: write more on combo problems because other people don't have the same idea of obvious as I do for combo.

Mathcamp pride!
Final USA Results
IDNameP1P2P3Day 1P4P5P6Day 2TotalAward
USA1Timothy Chu770147251428Silver Medal
USA2Vlad Firoiu73717720926Silver Medal
USA3Albert Gu30710000010Honorable Mention
USA4Brian Hamrick670137741831Gold Medal
USA5Sam Keller7007720916Bronze Medal
USA6Allen Yuan67316720925Silver Medal

The team with our lovely (and camera shy) guides