A lake has six ports. Is it possible to arrange a series of routes that satisfy the following conditions?
Each route must include exactly three ports.
No two routes may contain the same three ports.
Any tourist who wants to visit two different arbitrary ports has a choice of exactly two routes.
Label the ports A-F. There are 6 * 5 / 2 = 15 unique pairs of ports, each of which must be contained in exactly two routes. Each route contains exactly three pairs of ports, so there must be exactly 10 routes. Each port appears in exactly 5 of them. Let’s just start building them from the ground up:
There must be exactly two routes that contain ports A and B. There must be an additional three routes that contain A and not B, and three routes that contain B and not A:
A B _
A B _
A _ _
A _ _
A _ _
B _ _
B _ _
B _ _
_ _ _
_ _ _
Since we’ve labeled these ports arbitrarily, without loss of generality we can add third destinations C and D to the first two routes. A must also visit C and D in another route, but if we combine them into the third route, then routes 4 and 5 would necessarily both be AEF which is prohibited. So instead split up C and D, and E and F, between the third and fourth routes, and fill in the fifth with the only pair remaining:
A B C
A B D
A C E
A D F
A E F
B _ _
B _ _
B _ _
_ _ _
_ _ _
Similarly B needs to be paired once more with C and D each, but they cannot be combined in route 6 or else routes 7 and 8 would both be BEF. Through the first 8 routes, then, we don’t have any that pair ports C and D, so the last two routes must contain this pair:
A B C
A B D
A C E
A D F
A E F
B C _
B D _
B _ _
C D _
C D _
From here it’s straightforward to fill in the rest of the blanks with Es and Fs to create the remaining required routes:
A B C
A B D
A C E
A D F
A E F
B C F
B D E
B E F
C D E
C D F
Edited on March 25, 2021, 8:00 am
|
|
Posted by tomarken
on 2021-03-25 07:42:53 |
Solution
