I find combinatorial game problems really fun, especially Russian problems, but many of my favorites (all involving wizards, for some reason) take some degree of math background to understand.

Still, one night at the IOI in Kazakhstan, Chris gave us this puzzle I hadn’t heard of before. It’s quite simple although my intuition was initially wrong.

5 pirates of different ages have a treasure of 100 gold coins.

On their ship, they decide to split the coins using this scheme:

The oldest pirate proposes how to share the coins, and ALL pirates (including the oldest) vote for or against it.

If 50% or more of the pirates vote for it, then the coins will be shared that way. Otherwise, the pirate proposing the scheme will be thrown overboard, and the process is repeated with the pirates that remain.

As pirates tend to be a bloodthirsty bunch, if a pirate would get the same number of coins if he voted for or against a proposal, he will vote against so that the pirate who proposed the plan will be thrown overboard.

Assuming that all 5 pirates are intelligent, rational, greedy, and do not wish to die, (and are rather good at math for pirates) what will happen?

(puzzle copied from here)

I’m still up looking through photos from Kazakhstan. Missing all of you tonight!

Halfway up the mountains at Almaty. Photo taken by Mr Mark.

27.7.15: Practice session and opening ceremony

We wake up early in the morning to realize that we have over an hour before our guide comes to pick us up for breakfast. While trying to contact Allan, we engage in various activities, some of which involved the playground:

Breakfast involved some excellent milk, cakes and pastries. After that, we walked to the eventual contest hall, the Al-Farabi library, for the practice session. While playing cards, I inform the team about the IOI push-up challenge: pick a constant c, and for every point you fail to get at the IOI, you have to do c push-ups. I pick c = 0.2.

At the contest hall, we settle into our seats and take a look around. To our left sits Macau, to our right, Moldova, and others in the vicinity include France and Germany. The screen was locked on a cover page showing our details.

Someone in the contest hall counts down the seconds to the start of the practice session, and I get a glimpse of the tension that would be present tomorrow during Day 1. For now, I test out the keyboard, mouse and configure my system. I decide that the laptop keyboard is better, and I unplug the external one. The mouse works reasonably, so I won’t have to use my own. Then, I pull up Terminal and gEdit, and start to code out solutions to the practice tasks.

Although I had some time to think about them on the plane, I still only had partial solutions to divide and graph for 50 points each. Search was just trivial binary search. I code out all 3 solutions and submit, and they perform as expected. A small commotion at the entrance distracts me, and I notice that the leaders have arrived. Shien Jin and Mark come to my station a while later to make sure that my system is working fine.

After they leave, I suddenly solve Graph. It was pretty simple after all: run a BFS initially to find a path P from S to T. Then run a DFS from each vertex in P in turn to record, for each node v, the first vertex u in P such that there is a path from u to v. Then flip P working backwards, keeping a count of the first vertex of P that reaches each vertex of P, which is sufficient to find all points that disconnects S and T.

After the practice session, we head for lunch, then to the opening ceremony at the Palace of Students. This was the first time I had ever arrived early to an opening ceremony: so early, in fact, that we were waved away by a petulant man at the entrance, so we seek shelter under some trees to wait. This was the venue:

The opening ceremony was, in my opinion, bizarre. The performances were strange, including one where two dancers accompanied a man carrying just an unplugged guitar, synced to electronic music. Unlike the IMO, the IOI opening ceremonies just have the teams stand up in the hall instead of parading on the stage, which made for a speedy ceremony. It ended with the raising of the IOI flag, which failed on its first attempt. It was eventually raised, and the ceremony pronounced over.

Outside the hall, we started playing cards. A few Kazakh locals approached us and asked us where we were from, showed us a card trick, and then taught us how to play Durak (‘idiot’ in Russian), a card game widely played in Kazakhstan. Because they weren’t very proficient in English, this took some time, but we eventually got it. We would then play lots of this game over the week.

We then headed to an early dinner, before going back to the hostel for quarantine. This was when the leaders and deputies were translating the tasks for Contest Day 1 tomorrow, so wi-fi access was cut off on our side. We played cards and chatted, and went to bed at 10, all a little nervous for the contest the next day.

26.7.15: Flight to Almaty

At 3am, I dragged myself out of bed, gathered the final remaining things scattered around my room (toothbrush, retainer, laptop, phone, chargers), checked that my passport and wallet were with me, and set off for KLIA at 4am. Despite having to work at 9am, my father drove me straight to the airport, a 2.5 hours drive either way, while I slept snugly in the passenger seat.

I arrived at the airport, texted the group, and found out that Jen Khai was already there. I met up with him at a gate nearby, and said goodbye to my father. After a brief conversation, I suddenly remembered that I hadn’t yet had breakfast, so we head off to McDonald’s for a bite. After I get my food, Chris and Jia Jen arrive, and the team was thus assembled!

At 8am we meet up with Shien Jin and head to the counter for check-in. To our surprise, it was still not open, even though the flight was schedule to depart at 10:55 and it was already less than 3 hours before that happened. After some jokes about how this would be a precursor for Kazakhstan, we went to a dim sum place nearby for breakfast with Shien Jin’s parents, where the four of us spent the next hour trying to convince them that we’d already had breakfast and wouldn’t need much more food.

At 9am, we meet Mark and try the check-in counter again, and get our boarding passes. We were extremely disappointed that we didn’t get adjacent seats.😦

At the security checkpoint we took a group photo.

We made our way to the gate and note that the plane was pretty small.

Half an hour into the flight, Jen Khai comes over and tells me that there’s a vacant seat next to him, after which I promptly move. The flight to Almaty from Kuala Lumpur took 8 hours, but since it was a daytime flight, we didn’t get much sleep. Instead, we worked on the IOI practice tasks (divide and graph), discussed some IOI problems from 2014, watched a Russian movie, and looked at the pretty terrain as we flew past them.

When we arrived, we breezed through customs because Malaysia was (surprisingly) one of just ten countries for which a travel visa was waived! At the baggage carousel, we saw some other teams, but only knew the Singaporeans. Outside, we met a few other teams, Taiwan and Hong Kong, while waiting for the bus to depart.

Upon arrival at Al-Farabi Kazakh National University, our host for the week, we were very impressed by the playground facing the dormitories. Apparently, see-saws and slides are of some use to university students. We checked into our rooms, and then headed off for dinner. Here’s a view from our room:

Here was our first taste of Kazakh food. We had an interesting dinner trying to figure out what we were putting in our mouths, because this was also when we realized that there was a pretty substantial language barrier between us and the food servers. For instance, we didn’t know whether the meatloaf thing was chicken, beef, or…horsemeat? In any case, the food was better than I expected, and the same was true for the rest of the meals throughout the week. It was good.

During dinner, we were asked by multiple people about our guide, which we hadn’t met yet. This spurred a few industrious, official-looking people to go around trying to get us a guide, while trying to tell us to stay in the dining hall, which wasn’t a problem since we were still eating. After a while, we meet Allan, our guide for the week. Allan asks us if we want to go and dance, but we decide to return to our rooms. We then register and get our goodies:

When we first saw our rooms in the afternoon, we lamented the lack of air-conditioning and fans, but thought it would be OK because the weather was supposedly very cold at night. As it turns out, 20+ degrees Celcius isn’t actually very cold, and we go to bed in shorts and tees, sweating a little as our first day in Almaty drew to a close.

(Copied from Facebook. Remembered this fun story while taking a break from the past paper madness…)

In IMO final training last year we worked on this geometry problem, which seemed strangely familiar. After I found the solution I remembered that I’d solved it before on AoPS – Turkey’s problem 6 from 2012.

We then read the official solution from the booklet – hey, I used the same method! They even used Brokard’s theorem like I did. Wait…

Turns out, they printed the exact solution I posted on AoPS two years ago.😛

http://artofproblemsolving.com/community/c6h508906

I like this problem – the idea is similar to the geometry problem I wrote for the Junior Olympiad in 2013. Here it is, Turkey NMO 2012, Problem 6:

Let $B$ and $D$ be points on segments $[AE]$ and $[AF]$ respectively. Excircles of triangles $ABF$ and $ADE$ touching sides $BF$ and$DE$ is the same, and its center is $I$. $BF$ and $DE$ intersects at $C$. Let $P_1, P_2, P_3, P_4, Q_1, Q_2, Q_3, Q_4$ be the circumcenters of triangles $IAB, IBC, ICD, IDA, IAE, IEC, ICF, IFA$ respectively.

a) Show that points $P_1, P_2, P_3, P_4$ concylic and points $Q_1, Q_2, Q_3, Q_4$ concylic.
b) Denote centers of these circles as $O_1$ and $O_2$. Prove that $O_1, O_2$ and $I$ are collinear.

ephemeral / transient / fleeting / transitory / fugacious

It’s 45 minutes away from the end of January, and I’m here in my college dorm room, thinking about this past month. My fluorescent lamp is broken and my room is dark, but for the most part, it’s been a good month.

Of course, there was some turbulence along the way. I spent the first three weeks of January preparing for the SAT, and with it came a plethora of vulnerabilities: dealing with College Board customer service, the lingering moodiness after a bad practice test, and the nascent worry that would float sporadically to the front of my mind – am I ready for this?

Part of this strange uneasiness is the recognition of the fact that in half a year, I’ll be sending off postmarked applications to universities across the world, detailing my thoughts and dreams, my achievements and some of my failures. It seems very much like an exercise in efficient marketing: explain and describe your being in 4000 characters and a few pages of paper. Thus I think the most important aspect of this process is to understand who I truly am and what I want to become. It’s rather nerve-wracking. A year ago in January, I enthusiastically set off to live alone in Kuala Lumpur on a three-month internship as a software programmer, an experience that convinced me that computer science was not for me and left me again without direction. Fast forward a year and I find myself with a clearer head and compass. I think I now understand better who I am.

On the 24th I traveled down to Subang Jaya to take the SAT. I had arranged meetings with some of my friends studying in KL, and frankly I couldn’t wait for the test to end so that I could talk to them again. I met up with Chun Horng, Michelle, Anzo and Yi Kye, and it felt amazing to see them and talk about the past and portend about the future. Now that I’m in college in an isolated jungle, these are the people I find myself thinking about when it’s past 12am and I can’t sleep. I send messages to them and hope they reply. Occasionally I boot up my laptop and look through the photos from the past – pictures from the IMO, family trips, birthday celebrations. Some nights I miss them so much my body seems to ache!

As January draws to a close, I want to remind myself to put things in perspective. Living in a small boarding school has this tunneling effect, and I often find myself worrying and moping about tiny little issues that seem so gargantuan under the microscope of this college. As of this moment, many things are OK with the world and my life. In a few minutes I will flip my desk calendar to ‘February’ knowing that it will perhaps bring even more (unwarranted) tumult and worry than this month has brought. But I know that at the end of it all I’ll be here again, reflecting about what’s happened and what’s not happened, and realize that things are indeed…fine.

Have a happy February!

It’s been two months since we battled our battles and adventured our adventures in the beautiful, beautiful land of Cape Town, where we attended the 55th International Mathematical Olympiad.

Team Malaysia at the University of Cape Town.

It was one of the best times of my life, and I have so many memories that I want to relive. The camaraderie of pre-departure camp (and even more during the trip to South Africa). The intense two days of competition. Shivering together in the cold winter night. Watching penguins waddle up the beach as we looked out at the sea. Visiting the southernmost tip of South Africa and the Cape of Good Hope. Climbing up to the lighthouse at Cape Point where the six of us watched silently as the waves crashed into the cape. Bonding tightly with the team over food, long conversations and math.

Luckily, I can relive all that through the pictures we took at Cape Town! For the next few weeks, I’m planning to write our story, the IMO 2014 story, bit by bit, until the entire journey has been written down.

To start things off, I’ve written a math post for this year’s IMO, walking through the competition from a mathematical perspective – follow the link below to the pdf. Happy reading!

IMO 2014 – Justin’s math

Full results on imo-official: http://www.imo-official.org/team_r.aspx?code=MAS&year=2014

//////

We did it.

We:

– broke the Malaysian points record for the 5th straight year, 129 points

– broke the Malaysian rank record for the 5th straight year, rank 23

– won the second and third gold medals in Malaysian history

– won the youngest bronze medal in Malaysian history, Zi Song12 years

//////

Jetlagged, emotional, overwhelmed, surreal. I will write a complete series of posts chronicling the 2014 Malaysian IMO team in the coming weeks.