WEEKLY MATHEMATICS PROBLEM #100

A conduit under the Severn River contains 15 identical wires. Unfortunately, no one labeled the wires before the conduit was put in place. An electrician's job is to attach labels to each end of each of the 15 wires so that each wire has the same label at each end.

The electrician has only minimal equipment available; the electrician can connect any number of wires (or several groups of wires) together at one end of the conduit and then cross the Severn and test various pairs of wires at the other end of the conduit to see which connections would conduct electricity. What is the smallest number of river crossings necessary to complete the job?

(This problem is adapted from Macalester College Math Problem of the Week #778.)

All midshipmen submitting correct solutions to problem #99 by 3:30 pm on Tuesday, October 19, win a cookie. The best solution will be posted on the problem bulletin board.

A solution is "correct" if it gives a correct solution and explains why it works; a solution is "best" if it includes the clearest correct explanation. Submit solutions to Prof. Hanna at mathprob@usna.edu, or via the mailbox in Chauvenet 301.

Cookies for #99 to Midn. Carr, Conklin, Estes, Milev, Ortiz, and Privette.