7

Part of 2014 Bulgaria JBMO TST

Problems(1)

Broken line in 9x1 rectangle

Source:

9\times 1

rectangle is divided into unit squares. A broken line, from the lower left to the upper right corner, goes through all

20

vertices of the unit squares and consists of

19

line segments. How many such lines are there?