Maths Olympiad Prep

Track / Stage 6 / 272 of 400 #1272 of 1964

Problem 1272

National olympiad, first round
Combinatorics Difficulty 6.5 Find the answer

A 9×19\times 1 rectangle is divided into unit squares. A broken line, from the lower left to the upper right corner, goes through
all 2020 vertices of the unit squares and consists of 1919 line segments. How many such lines are there?

A number or a short expression. Spacing and $ signs are ignored.

Official solution

1. Let's first understand the problem. We have a 9×19 \times 1 rectangle, which means it has 9 columns and 1 row. This rectangle is divided into unit squares, so there are 9 unit squares in total.
2. The problem states that a broken line goes from the lower left corner to the upper right corner, passing through all 20 vertices of the unit squares. This means the line will pass through each vertex of the grid formed by the unit squares.
3. The line consists of 19 line segments, which means it changes direction 19 times. Since the line starts at the lower left corner and ends at the upper right corner, it must move right 9 times and up 10 times.
4. To find the number of such lines, we need to count the number of ways to arrange 9 right moves (denoted as 0) and 10 up moves (denoted as 1) in a sequence of 19 moves.
5. The number of ways to arrange 9 right moves and 10 up moves in a sequence of 19 moves is given by the binomial coefficient (199)\binom{19}{9}.

(199)=19!9!(199)!=19!9!10! \binom{19}{9} = \frac{19!}{9!(19-9)!} = \frac{19!}{9!10!}

6. Calculating the factorials, we get:

19!=121645100408832000 19! = 121645100408832000
9!=362880 9! = 362880
10!=3628800 10! = 3628800

7. Substituting these values into the binomial coefficient formula, we get:

(199)=121645100408832000362880×3628800=92378 \binom{19}{9} = \frac{121645100408832000}{362880 \times 3628800} = 92378

The final answer is 92378\boxed{92378}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.