HMMT 十一月 2019 · GEN 赛 · 第 10 题
HMMT November 2019 — GEN Round — Problem 10
题目详情
英文原题
- An up-right path between two lattice points P and Q is a path from P to Q that takes steps of 1 uniteither up or to the right. A lattice point ( x, y ) with 0 ≤ x, y ≤ 5 is chosen uniformly at random. Computethe expected number of up-right paths from (0 , 0) to (5 , 5) not passing through ( x, y ).
解析
英文解析
- An up-right path between two lattice points P and Q is a path from P to Q that takes steps of 1 uniteither up or to the right. A lattice point ( x, y ) with 0 ≤ x, y ≤ 5 is chosen uniformly at random. Computethe expected number of up-right paths from (0 , 0) to (5 , 5) not passing through ( x, y ).
Proposed by: Mehtaab Sawnhey
Answer: 175
For a lattice point ( x, y ), let F ( x, y ) denote the number of up-right paths from (0 , 0) to (5 , 5) that don’tpass through ( x, y ), and let
∑ ∑
S = F ( x, y ) .
0 ≤ x ≤ 5 0 ≤ y ≤ 5
Our answer is , as there are 36 lattice points ( x, y ) with 0 ≤ x, y ≤ 5.S
( )36
Notice that the number of up-right paths from (0 , 0) to (5 , 5) is = 252 because each path consists of 10
10 steps, of which we can choose 5 to be to the right. Each of these paths passes through 11 lattice points 5
( x, y ) with 0 ≤ x, y ≤ 5, so each path contributes 36 − 11 = 25 to the quantity we are counting in S . Then
25 · 252
S = 25 · 252, so our answer is = 175.
336