HMMT 十一月 2009 · GEN2 赛 · 第 4 题

HMMT November 2009 — GEN2 Round — Problem 4

[ 6 ] You are given a 5 × 6 checkerboard with squares alternately shaded black and white. The bottom- left square is white. Each square has side length 1 unit. You can normally travel on this board at a speed of 2 units per second, but while you travel through the interior (not the boundary) of a black square, you are slowed down to 1 unit per second. What is the shortest time it takes to travel from the bottom-left corner to the top-right corner of the board?

解析

[ 6 ] You are given a 5 × 6 checkerboard with squares alternately shaded black and white. The bottom- left square is white. Each square has side length 1 unit. You can normally travel on this board at a speed of 2 units per second, but while you travel through the interior (not the boundary) of a black square, you are slowed down to 1 unit per second. What is the shortest time it takes to travel from the bottom-left corner to the top-right corner of the board? √ 1+5 2 Answer: It is always faster to take a path around a black square than through it, since the 2 length of the hypotenuse of any right triangle is greater than half the sum of the length of its legs. Therefore, an optimal path always stays on white squares or on boundaries, and the shortest such path √ has length 1 + 5 2.