MathDB
Z-Shaped Polyline

Source: 2024 Japan MO P3

February 11, 2024
combinatorics

Problem Statement

In the xyxy-plane, points with integer coordinates ranging from 11 to 20002000 for both the xx and yy coordinates are called good points. Moreover, for any four points A(x1,y1),B(x2,y2),C(x3,y3),D(x4,y4)A(x_1, y_1), B(x_2, y_2), C(x_3, y_3), D(x_4, y_4) satisfying the following conditions, the polyline ABCDABCD is called a Z\mathbb{Z}-shaped polyline.
[*] All A,B,C,DA, B, C, D are good points. [*] x1<x2x_1<x_2, y1=y2y_1=y_2 [*] x2>x3x_2>x_3, y2−x2=y3−x3y_2-x_2=y_3-x_3 [*] x3<x4x_3<x_4, y3=y4y_3=y_4
Find the smallest possible positive integer nn such that Z\mathbb{Z}-shaped polylines Z1,Z2,…,ZnZ_1, Z_2,\dots, Z_n satisfy the following condition: for any good point PP, there exists an integer ii between 11 and nn inclusive such that PP lies on ZiZ_i.
Back to ProblemsView on AoPS