The owner has identified nine potential locations where a motel might be located. However, some of these locations are within 30 miles of each other, and the owner prefers to separate motels in the chain by at least 30 miles to avoid cannibalizing demand.

The owner wants to build motels on as many sites as possible while adhering to the 30-mile requirement. Which sites should be selected?

Hint: we can build the table for the conflicts: the numbered rows and columns correspond to the various motel sites. An entry of 1 appears in row i and column j if sites i and j are within 30 miles of each other.

Please show excel file

\begin{tabular}{r|l} \hline Potential site & Potential sites within 30 miles \\ \hline 1 & 2 \\ 2 & 1,5,7 \\ 3 & 5,6,8,9 \\ 4 & 6,7 \\ 5 & 2,3,6,8 \\ 6 & 3,4,5,7 \\ 7 & 2,4,6 \\ 8 & 3,5 \\ 9 & 3 \\ \hline \end{tabular} \begin{tabular}{l|lllllllll} \hline & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 1 & 1 & 1 & & & & & & & \\ 2 & 1 & 1 & & & 1 & & 1 & & \\ 3 & & & 1 & & 1 & 1 & & 1 & 1 \\ 4 & & & & 1 & & 1 & 1 & & \\ 5 & & 1 & 1 & & 1 & 1 & & 1 & \\ 6 & & & 1 & 1 & 1 & 1 & 1 & & \\ 7 & & 1 & & 1 & & 1 & 1 & & \\ 8 & & & 1 & & 1 & & & 1 & \\ 9 & & & 1 & & & & & & 1 \\ \hline \end{tabular} \begin{tabular}{r|l} \hline Potential site & Potential sites within 30 miles \\ \hline 1 & 2 \\ 2 & 1,5,7 \\ 3 & 5,6,8,9 \\ 4 & 6,7 \\ 5 & 2,3,6,8 \\ 6 & 3,4,5,7 \\ 7 & 2,4,6 \\ 8 & 3,5 \\ 9 & 3 \\ \hline \end{tabular} \begin{tabular}{l|lllllllll} \hline & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 1 & 1 & 1 & & & & & & & \\ 2 & 1 & 1 & & & 1 & & 1 & & \\ 3 & & & 1 & & 1 & 1 & & 1 & 1 \\ 4 & & & & 1 & & 1 & 1 & & \\ 5 & & 1 & 1 & & 1 & 1 & & 1 & \\ 6 & & & 1 & 1 & 1 & 1 & 1 & & \\ 7 & & 1 & & 1 & & 1 & 1 & & \\ 8 & & & 1 & & 1 & & & 1 & \\ 9 & & & 1 & & & & & & 1 \\ \hline \end{tabular}