HMMT 十一月 2018 · 冲刺赛 · 第 3 题

HMMT November 2018 — Guts Round — Problem 3

[ 5 ] 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 × 2 mazes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2018, November 10, 2018 — GUTS ROUND Organization Team Team ID# a + b b + c c + a

解析

[ 5 ] 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 ⇥ 2 mazes. Proposed by: James Lin Answer: 3 We must have both top-left and bottom-right cells blank, and we cannot have both top-right and bottom-left cells with walls. As long as those conditions are satisfied, the maze is solvable, so the answer is 3. a + b b + c c + a