Wednesday, February 16, 2011

Wires, Batteries and Lightbulbs

You are standing in a house in the middle of the countryside. There is a small hole in one of the interior walls of the house, through which 100 identical wires are protruding.

From this hole, the wires run underground all the way to a small shed exactly 1 mile away from the house, and are protruding from one of the shed's walls so that they are accessible from inside the shed.

The ends of the wires coming out of the house wall each have a small tag on them, labeled with each number from 1 to 100 (so one of the wires is labeled "1", one is labeled "2", and so on, all the way through "100"). Your task is to label the ends of the wires protruding from the shed wall with the same number as the other end of the wire from the house (so, for example, the wire with its end labeled "47" in the house should have its other end in the shed labeled "47" as well).

To help you label the ends of the wires in the shed, there are an unlimited supply of batteries in the house, and a single lightbulb in the shed. The way it works is that in the house, you can take any two wires and attach them to a single battery. If you then go to the shed and touch those two wires to the lightbulb, it will light up. The lightbulb will only light up if you touch it to two wires that are attached to the same battery. You can use as many of the batteries as you want, but you cannot attach any given wire to more than one battery at a time. Also, you cannot attach more than two wires to a given battery at one time. (Basically, each battery you use will have exactly two wires attached to it). Note that you don't have to attach all of the wires to batteries if you don't want to.

Your goal, starting in the house, is to travel as little distance as possible in order to label all of the wires in the shed.