5. The museum has 16 halls, arranged as shown in the diagram. In half of them, paintings are exhibited, and in the other half, sculptures. From any hall, you can go to any adjacent one (sharing a common wall). During any tour of the museum, the halls alternate: a hall with paintings - a hall with sculptures - a hall with paintings, and so on. The tour starts in hall A, where paintings are displayed, and ends in hall B.

a) Mark with crosses all the halls where paintings are exhibited. Solution. See the diagram.

b) A tourist wants to visit as many halls as possible (travel from hall A to hall B), but visit each hall no more than once. What is the maximum number of halls he can visit? Draw one of his longest routes and prove that he could not have visited more halls.