Cut a \(7\times 7\) square into \(9\) rectangles, out of which you can construct any rectangle whose sidelengths are less than \(7\). Show how to construct the rectangles.
There are \(16\) cities in the kingdom. We would like to build roads between these cities so that one can get from any city to any other without passing through more than one city on the way. To save cost, we would like to have no more than four roads coming out of each city. Prove that such a system of roads is unfortunately impossible to build.
There are \(2^4\) cities in a kingdom. Show that it is possible to build a system of roads so that one can travel from any city to any other while passing through at most one intermediate city, and so that at most five roads leave each city.