HMMT 十一月 2018 · 冲刺赛 · 第 18 题
HMMT November 2018 — Guts Round — Problem 18
题目详情
英文原题
- [ 10 ] An n × m maze is an n × m grid in which each cell is one of two things: a wall, or a blank. A mazeis solvable if there exists a sequence of adjacent blank cells from the top left cell to the bottom rightcell going through no walls. (In particular, the top left and bottom right cells must both be blank.)
Determine the number of solvable 2 × 5 mazes.
HMMT November 2018, November 10, 2018 — GUTS ROUND
Organization Team Team ID#
解析
英文解析
- [ 10 ] An n ⇥ m maze is an n ⇥ m grid in which each cell is one of two things: a wall, or a blank. A mazeis solvable if there exists a sequence of adjacent blank cells from the top left cell to the bottom rightcell going through no walls. (In particular, the top left and bottom right cells must both be blank.)
Determine the number of solvable 2 ⇥ 5 mazes.
Proposed by: John Michael Wu
Answer: 49
Solution 1: Replace 5 by an arbitrary n . Label the cells of the maze by ( x, y ) where 1 x n and
1 y 2. Let a denote the number of solvable 2 ⇥ n mazes, and let b denote the number of 2 ⇥ nn nmazes where there exists a sequence of adjacent blank cells from the (1 , 1) to ( n, 1). We observe therelationsa = 2 a + bn n 1 n 2
b = 2 b + a .
n n 1 n 2
The first relation follows from dividing into cases depending on if ( n 1 , 2 is blank. If this cell is blank,
then the maze is solvable if and only if there is a path to ( n 1 , 2) and the cell ( n, 2) is blank. The cell
( n, 1) is arbitrary so we get 2 a . If ( n 1 , 2) is a wall, then the maze is solvable if and only if theren 1
is a path to ( n 2 , 1) and each of the cells ( n 1 , 1) , ( n, 1) , ( n, 2) are blank. This gives the term b .
n 2
The second relation follows similarly dividing into cases based on whether the cell ( n 1 , 1) is blankor not.
The base cases are a = 1 , a = 3, b = 2 , b = 4. We thus obtain:
1 2 1 2
n a bn n
1 1 2
2 3 4
3 8 9
4 20 21
5 49 50
The answer is then 49.
Solution 2: Call a maze reachable if there exists a sequence of adjacent blank cells from (1 , 1) to anycell in column n . Let x denote the number of reachable 2 ⇥ n mazes where the rightmost columnhas a blank in the top cell and a wall in the bottom cell, let y denote the number of reachable 2 ⇥ nnnmazes where the rightmost column has a wall in the top cell and a blank in the bottom cell, and letz denote the number of reachable 2 ⇥ n mazes where the rightmost column has a blank in both of itscells. Then, observe the relationsnx = z + xn n 1 n 1
y = z + yn n 1 n 1
z = z + x + y ,
n n 1 n 1 n 1
as well as base cases x = 1 , y = 0 , z = 1. We thus obtain:
1 1 1
n x y zn n n
1 1 0 1
2 2 1 2
3 4 3 5
4 9 8 12
5 21 20 29
Note that the answer is y + z , which is 20 + 29 = 49.
5 5