PUMaC 2019 · 团队赛 · 第 14 题

PUMaC 2019 — Team Round — Problem 14

Consider a grid of black and white squares with 3 rows and n columns. If there is a non-empty sequence of white squares s , ..., s such that s is in the top row and s is in the bottom row 1 m 1 m and consecutive squares in the sequence share an edge, then we say that the grid percolates. Let T be the number of grids which do not percolate. There exists constants a, b such that n √ T n approaches 1 as n approaches ∞ . Then b is expressible as ( x + y ) /z for squarefree y and n ab coprime x, z . Find x + y + z .

解析

Consider a grid of black and white squares with 3 rows and n columns. If there is a non-empty sequence of white squares s , ..., s such that s is in the top row and s is in the bottom row 1 m 1 m and consecutive squares in the sequence share an edge, then we say that the grid percolates. Let T be the number of grids which do not percolate. There exists constants a, b such that n √ T n → 1 as n → ∞ . Then b is expressible as ( x + y ) /z for squarefree y and coprime x, z . n ab Find x + y + z . Proposed by: Alan Yan Answer: 50 Let T be the number of non-percolating 3 by n grids, and let S be the number of nonper- n n colating 3 by n grids such that there is a sequence of white squares from the leftmost middle square (which must be white in S ) to either the top or the bottom. Then we have that n S = 2( T − S ) + 2 S = 2 T n n − 1 n − 1 n − 1 n − 1 by adding a column to the left, and T = 7( T − S ) + 6 S = 7 T − S = 7 T − 2 T n n − 1 n − 1 n − 1 n − 1 n − 1 n − 1 n − 2 √ 2 7+ 41 Thus we have that b = 7 b − 2, giving us . 2