Google Treasure Hunt Week 1 Problem/Solution

Google is hosting a puzzle contest called the Treasure Hunt, testing knowledge of computer science, networking, problem solving, etc. It is free and open to anybody, and there are prizes for the first person who can get all of the questions right.

Go to http://treasurehunt.appspot.com/ to see the questions and enter the contest.

Here is the robot in a grid question (week 1) http://treasurehunt.appspot.com/historic/robot/:

A robot is located at the top-left corner of a 58 x 48 grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Note: The grid below is 7x3, and is used to illustrate the problem. It is not drawn to scale.

How many possible unique paths are there?

Spoiler: to see the answer, click here.
To re-hide the answer, clear your browsing history and reload this page.


For question 2, you just have to think about the basic concepts of probability and combinatorics. Let's use the example with the 7 by 3 grid. In this case, the robot has to go 6 units to the right and 2 units down. This is a total of 6+2=8 steps the robot will end up taking. Using the counting principle/permutations, the number of ways of ordering these 8 steps is 8! (8 factorial, or 8*7*6*5*4*3*2*1). I thought about it like the permutations of this set of characters: R R R R R R D D (6 steps right and 2 steps down). But, we need to divide out the repetition here. Think of the option R R R R R R D D: this is one path the robot can take. But with 6 Rs that are all the same, it doesn't matter if we switch them around a little, like the first and last R switch places. So, we have to divide out the repetition: the number of ways of ordering all the right steps and all the down steps: this is 6!2!, so our final answer is 8!/(6!2!)=28 for the 7 by 3 grid example. I used the same method for the 58 by 48 problem.