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 maze is solvable if there exists a sequence of adjacent blank cells from the top left cell to the bottom right cell 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 maze is solvable if there exists a sequence of adjacent blank cells from the top left cell to the bottom right cell 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 ⇥ n n n mazes where there exists a sequence of adjacent blank cells from the (1 , 1) to ( n, 1). We observe the relations a = 2 a + b n 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 there n 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 blank or not. The base cases are a = 1 , a = 3, b = 2 , b = 4. We thus obtain: 1 2 1 2 n a b n 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 any cell in column n . Let x denote the number of reachable 2 ⇥ n mazes where the rightmost column n has a blank in the top cell and a wall in the bottom cell, let y denote the number of reachable 2 ⇥ n n mazes where the rightmost column has a wall in the top cell and a blank in the bottom cell, and let z denote the number of reachable 2 ⇥ n mazes where the rightmost column has a blank in both of its n cells. Then, observe the relations x = z + x n n 1 n 1 y = z + y n 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 z n 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