Maths Olympiad Prep

Library / /9 of 13

Combinatorics Difficulty 6.8 National Olympiad Prove it Italy

On a lake there is a village of huts placed on stilts at the nodes of a rectangular m×nm \times n grid (see example in figure). From the platform of each hut exactly pp bridges depart, connecting it to one or more of the adjacent huts (with respect to the grid, hence not diagonally). For which positive integer values of m,nm, n and pp is it possible to place ii bridges so that from every hut one can reach any other hut? (Obviously between two adjacent huts several bridges can be placed.)

Figure 1

Solution

Solution:

If m=1m=1 or n=1n=1 a hut placed at one end has only one adjacent hut, which therefore cannot be connected to any other hut (the pp bridges departing from the first hut must necessarily reach the adjacent hut). Hence the only possibilities are (m,n)=(1,2)(m, n)=(1,2) or (m,n)=(2,1)(m, n)=(2,1) with pp arbitrary.

If mm and nn are both greater than 1, one cannot have p=1p=1, since from a hut only one other hut could be reached.

Let us now consider the case where m,nm, n and pp are all greater than 1. We show that it is possible to place the bridges if and only if mnm \cdot n is even (and pp can be any value). Coloring the huts white and black as on an ordinary chessboard, we have that every bridge has one white end and one black end. If mnm \cdot n is odd, that is mm and nn are both odd, it is not possible to have the same number of bridges depart from every hut, since the number of white huts differs by one (more or less) from that of the black huts.

On the other hand, if (for instance) mm is even, one can form 2×n2 \times n blocks in the following way:

Figure 2

The four half-bridges a,b,c,da, b, c, d serve to connect the blocks to one another (obviously in the case of the outermost blocks two of them are welded together to form a single bridge).

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 translated into English from it; metadata (topic, difficulty) added by this project.