Maths Olympiad Prep

Library / /12 of 15

Combinatorics Difficulty 6.1 National olympiad Prove it Romania

An 8×88 \times 8 array is divided into 64 unit squares. In some of the unit squares a diagonal is drawn, such that no two diagonals share a common point – not even an endpoint. Find the maximum number of diagonals that can be drawn under these circumstances.

Solution

Look at two contiguous rows of a 2n×2n2n \times 2n array, containing kk diagonals in the cells of row AA and \ell diagonals in the cells of row BB. The ends of these diagonals on the separating line of the two rows have to be distinct points, and they can only occupy at most the 2n+12n + 1 available positions, therefore k+2n+1k + \ell \le 2n + 1. Since the 2n2n rows may be grouped in nn sets of pairwise contiguous rows, the total number of diagonals drawn in the array is at most n(2n+1)=(2n+12)n(2n + 1) = \binom{2n+1}{2}. A model is easily found – only use / type diagonals in the cells of coordinates (2i+1,j)(2i + 1, j) and (j,2i+1)(j, 2i + 1), with 12i+1j2n1 \le 2i + 1 \le j \le 2n. The answer for 2n=82n = 8 is therefore 3636.

Alternative Solution.

Colour the nodes of the array alternatively white and black by columns, starting with the left side. Any diagonal drawn will then have its ends of different colour. Since there are exactly n(2n+1)n(2n+1) black nodes (while there are (n+1)(2n+1)(n+1)(2n+1) white nodes), and all diagonals are disjoint, it follows the total number of diagonals drawn in the array is at most n(2n+1)=(2n+12)n(2n+1) = \binom{2n+1}{2}. At close inspection, it is virtually the same idea as above, in a more elegant setting.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.