Probability

# Rectangular Grid Walk: Level 4 Challenges

A thief, standing by the gate (down left corner), is going to steal a diamond from a guarded building with square corridors. The guard stands in the middle at the moment when the thief starts approaching the diamond. He can walk one unit per minute in the grid, and the guard also walks one unit per minute around the diamond along the red arrows. If the guard and the thief ever meet at the same coordinate, the guard will catch the thief. The thief will also be caught if he isn't back to the gate in 12 minutes.

How many different routes the thief can take to steal the diamond and then return to the gate without getting caught?

A dog is standing at the bottom left corner of a grid of $46 \times 46$ streets. The dog is trying to get to the top right corner of the grid, where it knows there is some food. As the dog runs, between the corners, it will only ever run up and to the right. Any time the dog runs to the right, it runs at least $4$ consecutive blocks to the right, and any time it runs up, it runs at least $12$ consecutive blocks up. How many different intersections are unreachable for the dog by following these rules?

Details and assumptions

The last stretch that the dog runs must also satisfy the condition on the minimum number of consecutive blocks.

An intersection is reachable if the dog runs through it. It doesn't matter if the dog can change direction at that intersection. Remember that the dog needs to exit through the top right corner of the grid.

There are 10 people in line to get into a theatre. Admission costs 50 cents. Of the 10 people, half of them have a 50-cent piece and the other half have a $1 bill. Suppose that the box office has an empty cash register, how many ways can the people line up so that whenever a person with a$1 dollar bill buys a ticket, the box office has a 50-cent piece in order to make change? (After every one is admitted, there will be 5 \$1 dollar bills in the cash register.)

On a $9 \times 9$ point grid, insect A stands on the bottom-left corner and insect B stands on the top-right corner. They start moving towards each other at the same constant speed. A can move only to the right and up along the lines, while B can move only to the left and down along the lines of the board. Find the total number of ways the two insects can meet at the same point during their trip.

How many ways are there to get from the bottom left corner of a $10\times 10$ grid to the top right corner in 20 steps, if you must cross the main diagonal (in red) two times or more?

In the above example, the blue path crosses the red diagonal three times, so it is a valid path.

The paths are monotonic, i.e, only moves to the right and the top are allowed.

Start in the lower left corner of a 5x10 unit grid. You may only move to the right and upward along the edges to get to the top right corner. The area of a path between the corners is the amount of area beneath the line in square units. For example:

On a 5x10 grid, how many different paths from the lower left corner to the upper right corner have an area congruent to 1 mod 5?

Bonus: Choose any prime $p$ and positive integers $i, $j$ and $k$ and generalize this solution to the number of paths with an area congruent to $i$ mod $p$ on a $jp$ by $kp$ grid.

×