MathDB

Problem 3

Part of 1992 Bulgaria National Olympiad

Problems(1)

counting lattice point sequences

Source: Bulgaria 1992 P3

5/18/2021
Let mm and nn are fixed natural numbers and OxyOxy is a coordinate system in the plane. Find the total count of all possible situations of n+m−1n+m-1 points P1(x1,y1),P2(x2,y2),…,Pn+m−1(xn+m−1,yn+m−1)P_1(x_1,y_1),P_2(x_2,y_2),\ldots,P_{n+m-1}(x_{n+m-1},y_{n+m-1}) in the plane for which the following conditions are satisfied:
(i) The numbers xix_i and yi (i=1,2,…,n+m−1)y_i~(i=1,2,\ldots,n+m-1) are integers and 1≤xi≤n,1≤yi≤m1\le x_i\le n,1\le y_i\le m. (ii) Every one of the numbers 1,2,…,n1,2,\ldots,n can be found in the sequence x1,x2,…,xn+m−1x_1,x_2,\ldots,x_{n+m-1} and every one of the numbers 1,2,…,m1,2,\ldots,m can be found in the sequence y1,y2,…,yn+m−1y_1,y_2,\ldots,y_{n+m-1}. (iii) For every i=1,2,…,n+m−2i=1,2,\ldots,n+m-2 the line PiPi+1P_iP_{i+1} is parallel to one of the coordinate axes. (Ivan Gochev, Hristo Minchev)
combinatoricsnumber theorygeometryalgebraSequences