Solution

The director can create a route as described above if and only if \(m;n \geq 2\), and at least one of the \(m\) or \(n\) is divisible by \(2\). We analyze three cases.

1. If \(m=2\) and \(n \geq 2\), rotate the rectangle so that \(m=2\) is the number of rows. Create a route like this: the first part leads from the bottom left corner to the bottom right corner (the entire bottom row), then it passes to the top right corner and then goes all the way left until it reaches the top left corner (the entire top row). It is evident that this route satisfies the requirements.
2. If the \(m>2\) is divisible by \(2\) and \(n>2\), rotate the rectangle so that \(m=2k\) (\(k \geq 2\)) is the number of rows. In order to create a route satisfying the requirements, introduce coordinates for the little squares (rooms), where \((m;n)\) denotes a square with \(m\) equal to the row number, and \(n\) equal to the column number; \((1;1)\) is the lower left corner.

Consider a route connecting the following squares consecutively staying inside the same row or the same column:

• From \((i;2)\) to \((i;n)\),
• From \((i;n)\) to \((i+1;n)\),
• From \((i+1;n)\) to \((i+1;2)\),
• From \((i+1;2)\) to \((i+2 ; 2)\),

where \(i\) takes all the values \(\{1;3;5;\ldots;m-1=2 k-1\}\). This route will end in the square \((m;2)\). Next, take the route to the \((m;1)\) and then go to \((1;1)\) while staying in the first column. Such route satisfies the requirements. An example of the route is shown in Fig.16 with values \(m=4\) and \(n=5\):

3. If both \(m\) and \(n\) are not divisible by \(2\) (\(m;n \neq 1\)), let us show that the required route cannot be completed. We color the squares within the \(m \times n\) rectangle in a chessboard pattern and note that adjacent squares always have different colors.

By contradiction, assume that the required route exists. As the route passes through all squares (and the total number of squares is odd), the transition from one square to another square occur an even number of times. Consequently, the route will end in a square of the same colour as the starting square. This is impossible, since both squares are next to each other and should have different colors. Consequently, there is no valid route in this case.

As the variables \(m\) and \(n\) are interchangeable, all cases are analyzed.

Atrisinājums

Muzeja vadītājs var izveidot aprakstīto maršrutu visām \(m;n \geq 2\) vērtībām, kurām vismaz viens no \(m\) vai \(n\) dalās ar 2. Aplūkojam trīs gadījumus.

1. Ja \(m=2\) un \(n \geq 2\), pagriezīsim taisnstūri tā, lai \(m=2\) būtu rindu skaits. Tātad maršruta pirmā daļa ved no apakšējā kreisā stūra uz apakšējo labo stūri (visa apakšējā rinda), tālāk uz augšējo labo stūri un pēc tam augšējo kreiso stūri (visa augšējā rinda). Redzams, ka maršruts apmierina uzdevuma nosacijumus.

2. Ja \(m>2\) dalās ar \(2\) un \(n>2\), pagriezīsim taisnstūri tā, lai \(m=2 k(k \geq 2)\) būtu rindu skaits. Lai konstruētu maršrutu, kas apmierina uzdevumu nosacijumus, ieviešam rūtiņu koordinātu sistēmu \((m;n)\), kur \(m\) - rindas numurs, \(n\)-kolonnas numurs un \((1;1)\) ir apakšējais kreisais stūris.

Aplūkojam maršrutu, kas secīgi vienas rindas vai vienas kolonnas ietvaros savieno šādas rūtiņas:

• \((i ; 2)\) ar \((i ; n)\)
• \((i ; n)\) ar \((i+1 ; n)\)
• \((i+1 ; n)\) ar \((i+1 ; 2)\);
• \((i+1 ; 2)\) ar \((i+2 ; 2)\)

kur \(i\) secīgi vienāds ar \(\{1;3;5;\ldots;m-1=2 k-1\}\).

Konstruētais maršruts noslēgsies rūtiņā \((m;2)\). Tālāk vedam maršrutu uz \((m;1)\) un attiecīgi \((1;1)\) pa pirmo kolonnu. Redzams, ka maršruts apmierina uzdevuma nosacījumu. Maršruta piemērs redzams 16. att. ar vērtībām \(m=4\) un \(n=5\).

1. Ja gan \(m\), gan \(n\) nedalās ar \(2\) (\(m;n \neq 1\)), pierādīsim, ka prasīto maršrutu nav iespējams izveidto. Iekrāsosim taisnstūra rūtiņas šaha galdiņa veidā un ievērosim, ka šādam krāsojumam izpildās īpašība: blakus esošām rūtiņām ir dažādas krāsas.

Pieņemsim pretējo, ka prasītais maršruts eksistē. Tā kā maršruts iziet cauri visām rūtinām, kuru ir nepāra skaits, tad pārejas no vienas rūtiņas uz otru notiek pāra skaitu reižu. Līdz ar to maršruts beigsies tādas pašas krāsas rūtiņā kā sākuma rūtiņa. Taču tā nevar būt, ja šī rūtiņas atrodas blakus, jo tām būtu jābūt dažādās krāsās. Līdz ar to iegūta pretruna un šāds maršruts neeksistē.

Tā kā mainīgos \(m\) un \(n\) uzdevumā kontekstā var mainīt vietām, tad ir aplūkoti visi iespējamie gadījumi.