# Riddler Revisited

I’m taking a second crack at FiveThirtyEight’s Riddler problem. I thought I solved the problem two weeks ago, but my answer wasn’t quite right.

Here is this week’s problem:

There’s an airplane with 100 seats, and there are 100 ticketed passengers each with an assigned seat. They line up to board in some random order. However, the first person to board is the worst person alive, and just sits in a random seat, without even looking at his boarding pass. Each subsequent passenger sits in his or her own assigned seat if it’s empty, but sits in a random open seat if the assigned seat is occupied. What is the probability that you, the hundredth passenger to board, finds your seat unoccupied

I’m not even going to try and figure out the math for this puzzle. My statistics skills aren’t nearly strong enough. But my coding skills are. This is an easy problem to solve with a Monte Carlo simulation.

Here’s my python solution.

And the output charted.

The last passenger has a 50% chance of getting their assigned seat.

The number of passengers who get their assigned seats is distributed around 95, with a 1% chance of everyone getting their assigned seat (in the event the first passenger randomly chooses his/her own seat).

Interestingly, it doesn’t matter how many seats are on the plane. If there are 10 or 200 seats, the last passenger still has a 50% chance of getting their assigned seat. The second last passenger has  67% chance, and the 3rd last passenger has a 75% chance.

It’s easy to derive the equation for the Xth last passenger from this, even though I can’t figure out the math to prove it. The Xth last passenger has a X/X+1 chance of getting their assigned seat. So the 5th last passenger, has a 5/6 = 83.3% chance of getting their seat.

# Math Problems

I’ve noticed a few Grade 6 math problems on Facebook that I’m sure Einstein would be embarrassed to see his picture on. I’m not sure which is sadder, that people consider a problem given to 11-year olds genius-level, or that only 50% of adults got the answer right.

I’m much more interested in the problems that FiveThirtyEight has been posting for their Riddler series. This week the problem involves cars getting stuck in traffic. Thankfully, not something I normally have to deal with, but I think I figured out the answer.

The Problem:

There is a very long, straight highway with some number of cars (N) placed somewhere along it, randomly. The highway is only one lane, so the cars can’t pass each other. Each car is going in the same direction, and each driver has a distinct positive speed at which she prefers to travel. Each preferred speed is chosen at random. Each driver travels at her preferred speed unless she gets stuck behind a slower car, in which case she remains stuck behind the slower car. On average, how many groups of cars will eventually form? (A group is one or more cars travelling at the same speed.)

My solution:

f(N) <- average number of car groups if there are N cars
f(0) = 0
f(1) = 1

If we have 2 cars there is 50% chance of the first car being faster, which would create 2 groups; and 50% chance of the 2nd car being faster and merging into a single group.
f(2) = 0.5 * 2 + 0.5 * 1 = 1.5

More generally, if we just consider the first 2 cars. There’s a 50% chance of there being a solo lead car plus the groups that form behind it, and a 50% chance of the first car merging into the group behind it. We can define the average number of cars recursively, where:
f(N) = 0.5 * (1 + f(N-1)) + 0.5 * f(N-1)

that equation reduces to:
f(N) = 0.5 + f(N-1)

testing it out:
f(2) = 0.5 + f(1) = 1.5
f(3) = 0.5 + f(2) = 2
f(4) = 0.5 + f(3) = 2.5

Which is an arithmetic series that can be reduced to:
f(N) = 0.5 + 0.5 * N

or more succinctly:
f(N) = 0.5 * (N + 1) (for N >= 1)
f(N) = 0 (for N < 1)

# Loving the Cloud Money

One of my favourite tech discoveries this year has been nTrust – a mobile payment app made by a local Vancouver startup. I’ve been using it to transfer money between friends (like Interac e-transfers but without any fees) and purchase lunch from local food carts.

They’ve been pushing hard to increase their user base and running a lot of lucrative promotions. If you sign up using referral code ‘chr597’ you get \$10 for free. They’ve also been running deals with cloud money discounts at my favourite food carts – Arturo’s and Culver City Salads. Nothing like a free lunch.

I’ve been using their app a lot and they asked if they could feature me on their blog. The post went up today – Keep on (taco) truckin’. Somehow I mislead them into believing I was a born in Vancouver, but other than that I’m happy with how it turned out.

# The pitfalls of 2 factor authentication

TL;DR: Don’t leave home without backup codes.

My cellphone is dead. It is stuck in a crashing boot loop. Factory reseting the phone hasn’t helped. It might be salvageable by flashing the ROM, but that’s not easy to accomplish while traveling (I did attempt it at an Internet cafe- epic fail).

So much for getting a local SIM card. The worst part is I’ve been locked out of many of my online accounts (Google, Dropbox, wordpress, and a few others) because they rely on Google Authenticator or the ability to receive a text message. Silly me, I didn’t print out any backup codes before I went travelling. Lesson learned.

So I can’t check my email on any machine. I can’t write blog posts either, but luckily Emily has authorship rights to this blog.

I’m now in the market for a new smartphone, but that might have to wait until we get into a bigger city. We’re traveling through small towns for the next 10 days.

In the meantime, I have 2 options for getting into my google account. Send my password to a someone in Canada that can access a trusted device (my work laptop). Or if that doesn’t work, start the process of unlocking my account with Google, which takes a week for security reasons.

I think 2-factor authentication is great under normal circumstances, but next time I go traveling I’ll likely disable it.

# Living Like the Jetsons – Rosie the Roomba

I’ve outsourced my duties as Official Floor Cleaner to Rosie, a Roomba 770 we named after the robotic maid on The Jetsons. With two cats, keeping the fur balls under control is a full-time job. Rosie is temperamental, but our floors are definitely cleaner now.

The Roomba does best with frequent, small cleaning jobs. Rosie is scheduled to clean everyday, usually when we’re out of the house. It has no problem handling hardwood floors and carpet, although it does a better job on the carpet, and excels at getting into tight spaces. It’s frightening how much dust and dirt it found under our bed.

I had hoped it would keep the floors clean when we were gone on vacation, but it needs daily attention. The dust bin is small and has to be emptied after almost every run. When we first ran the Roomba, it collected so much dust we had to empty it mid-run. Every week or two, I take it apart to remove all the hairs that become tangled in its rollers. Not a lot of work, but not fuss-free either.

I’m impressed with how well constructed and engineered the Roomba is. It feels like it’s designed to last and be easily repaired. I’m less impressed with the artificial intelligence. I thought it would slowly learn the layout of our apartment, but it seems to bump around in the same chaotic way today as it did on its first run. Our dining room table has become Rosie’s nemesis. She spends a lot of her time caught between between the chair legs, just wide enough for her to squeeze between before becoming trapped. She often bumps around for 10-15 minutes before frustration (or the robot equivalent) sets in and she goes back to her dock defeated.

We’ve gotten better at Roomba-prooofing the house before we leave in the morning. Often, we’ve come home to find Rosie impaled on a towel or entangled on a cord we left lying on the floor. The best was when she snagged the cord for the blinds and pulled herself a few inches off the floor. Luckily the Roomba is smart enough to know when its stuck and will shutdown before causing permanent damage.

Rosie has worked so well at cleaning up after the cats, we’ve experimented using robots to play with them too.

# Novus – Faster and Cheaper Internet

We finally ditched Shaw and moved to Novus for our internet provider – it’s faster and cheaper, and the customer service is better. What’s not to like?

Novus is a fibre optic internet provider and the only real alternative to the big telecoms (Shaw and Telus). They’ve been expanding out of downtown Vancouver, hooking up buildings to their fibre optic network. Our building was the last one in the Olympic Village to gain access, but it was worth the wait.

A quick comparison of our Shaw and Novus plans.
Shaw – High Speed 10
Cost: \$55 + taxes
Upload Speeds: Up to 0.5 Mbps

Novus – Internet 25
Cost: \$32.50 + taxes