MathDB

broken line of allowed routes between 2 lattice points, not touching y=x line

Source: Finland 2014, Problem 3

September 1, 2019

combinatoricscoordinateslattice pointsbroken line

Problem Statement

The points

P = (a, b)

and

Q = (c, d)

are in the first quadrant of the

xy

plane, and

a, b, c

and

d

are integers satisfying

a < b, a < c, b < d

and

c < d

. A route from point

P

to point

Q

is a broken line consisting of unit steps in the directions of the positive coordinate axes. An allowed route is a route not touching the line

x = y

. Tetermine the number of allowed routes.