2
$\begingroup$

It seemed like a coincidence, but just as Mr. Hilbert finished the checkout procedures at the front desk of the Grand Hotel, the lights went out.

"What happened, Mr. Cantor?" Mr. Hilbert asked the concierge.

"It's probably the fuse boxes," said Mr. Cantor rather disgruntledly. "I heard our manager fell for a late-night TV ad and bought these cheap fuses for the lights." Mr. Hilbert followed Mr. Cantor to the electrical room. Right at the front of the endless array of metal cabinets was one labelled "LOBBY AND FIRST $N$ ROOMS". On the ground were boxes upon boxes of "KIRK'S ZWEET DEEL FUZEZ $(1 \space \Omega)$".

"It's weird why we didn't switch to circuit breakers yet," said Mr. Cantor as he picked up a multimeter lying on the side. He made a grumbly noise. "Hmpf, seems like the multimeter is almost out of battery. We might not able to measure that many fuses before it dies". He opened the cabinet and grumbled some more. "And what kind of idiot doesn't label the fuses in a fuse box!" Peering at the fuses, his annoyance exploded into incredulity. "AND you can't even see the fuse wire in these fuses!!"

"It's ok," said Mr. Hilbert while mustering with his most soothing voice possible. "If we take out all the fuses and measure them together, we can minimize the number of measurements needed. Here's what we can do..."

Can you figure out the minimum number of multimeter measurements needed to find a single blown fuse $(R = \infty \space \Omega)$ from $N+1$ fuses before Mr. Cantor goes crazy? Can you also prove that your solution is optimal and works for all $N > 2$ ?

Improve this question
$\endgroup$
4
  • $\begingroup$ You have lots of cheap fuses, why not replace all of them without measuring? ;) $\endgroup$
    – Sleafar
    Sep 3, 2015 at 7:02
  • $\begingroup$ Because one of these days you'll create infinite waste ;) $\endgroup$
    – Hackiisan
    Sep 3, 2015 at 7:17
  • $\begingroup$ From an economic point of view they should all be replaced. This will be considerably faster, reducing the staff time Mr. Cantor would waste and the reputational impact of the lights being off for longer! $\endgroup$
    – Gordon K
    Sep 3, 2015 at 7:23
  • 1
    $\begingroup$ @GordonK It's the Grand Hotel Mr. Hilbert is checking out of. Nothing is very economical there ;) $\endgroup$
    – Hackiisan
    Sep 3, 2015 at 7:37

3 Answers 3

Reset to default
2
$\begingroup$

Attempt for a 1 measurement solution

I post it as a separate answer because it makes even more assumptions than the first one. Maybe I should limit it to spherical fuses in vacuum?

Assumption 1: The multimeter is accurate enough for following measurements.

On the ground were boxes upon boxes of "KIRK'S ZWEET DEEL FUZEZ $(1 \space \Omega)$".

As I cannot use them to replace all fuses, let's use them for the measurements.

Assumption 2: Infinite supply of knowingly working fuses (they were all tested by Kirk himself).

Assumption 3: All fuses have a resistance of exactly $1\Omega$

Arrange all fuses that must be checked to following groups ordered in a series:

  • first fuse is alone in a group (total resistance $R_1 = 1\Omega$)
  • second fuse is with one working fuse from the supply in a group (total resistance $R_2 = 2\Omega$)
  • third fuse is with two working fuses from the supply in a group (total resistance $R_3 = 3\Omega$)
  • fourth fuse is with thress working fuses from the supply in a group (total resistance $R_4 = 4\Omega$)
  • and so on ....

For the measurement arrange all groups in parallel. The total resistance of this setup if all fuses are OK should be $R = \frac{1}{1/R_1 + 1/R_2 + 1/R_3 + ...}$. Based on the difference to the expected value the broken fuse can be determined in 1 measurement.

Example with 3 fuses

Measured value is:

  • $1.2\Omega$ => Broken fuse is in group $1$.
  • $0.75\Omega$ => Broken fuse is in group $2$.
  • $0.6666..\Omega$ => Broken fuse is in group $3$.
Improve this answer
$\endgroup$
6
  • $\begingroup$ I would like to point out that if the broken fuse is in group $1$, the measured resistance should be $\infty \space \Omega$. Otherwise, you got it! $\endgroup$
    – Hackiisan
    Sep 3, 2015 at 20:38
  • $\begingroup$ @Hackiisan If R1=infinity then 1/R1=0. The total resistance of the parallel setup is then 1/(1/R2+1/R3)=1/(1/2+1/3)=6/5. Maybe I didn't describe my setup clearly enough. I'll add a picture tomorrow. $\endgroup$
    – Sleafar
    Sep 3, 2015 at 20:53
  • $\begingroup$ The circuit is short-circuited if R1 is the fuse =) $\endgroup$
    – Hackiisan
    Sep 3, 2015 at 20:55
  • $\begingroup$ @Hackiisan I don't understand. A broken fuse has infinite resistence as stated in the question (open circuit). A short-circuit has almost 0 resistance. $\endgroup$
    – Sleafar
    Sep 3, 2015 at 21:03
  • $\begingroup$ Oops, I meant open circuit, sorry. But the point remains: you don't need to use the parallel formula for a single resistor. $\endgroup$
    – Hackiisan
    Sep 3, 2015 at 21:05
2
$\begingroup$

If we have only one measurement, we can't have any two fuses in parallel or in series, because it wouldn't be possible to distinguish them from the multimeter reading. Every circuit with more than one fuse will have two in parallel or in series, so we can only test one fuse, and have one fuse unused, for a total of two.

If we have two measurements, we can use the first one to narrow it down to two fuses. A circuit like this can test an arbitrary number of fuses (if there are an even number of fuses, add a fuse in series with the uppermost fuse): ]
We can interpret these fuses as being in two parallel sequences: one from the top fuse marked "233/144" to the one marked "inf", and one from the lower fuse marked "233/144" to the one marked "233/89". The readings for each of the fuses on the top line being broken increase strictly from left to right. The same happens for the fuses in the lower line, so no two fuses in the same sequence result in the same reading. This means that for any reading, there are at most two fuses (one in the top line and one in the bottom line) that result in that reading, and we can use the second test to determine which.

So we only need 2 measurements (with infinite precision) for any finite number of fuses!

In fact, every fuse results in a different reading when it is broken, except for the two at the top. This is guaranteed by the fact that if we alternate the two sequences of fuses as mentioned above, we get a single sequence that is also strictly increasing. Then, if we replace the top fuse in this system with a new one, we can determine which fuse is broken with only one measurement.

Improve this answer
$\endgroup$
4
  • $\begingroup$ +1 Once I remembered this I almost expected this kind of solution. ;) $\endgroup$
    – Sleafar
    Sep 3, 2015 at 13:52
  • $\begingroup$ This is a similar to the intended solution, but after I published the question, Mr. Hilbert was kind enough to alert me to another solution I was not aware of which can do better! $\endgroup$
    – Hackiisan
    Sep 3, 2015 at 18:42
  • $\begingroup$ @Hackiisan Are we allowed to use a fuse that is guaranteed to be intact? $\endgroup$
    – f''
    Sep 3, 2015 at 18:56
  • $\begingroup$ @f'' I don't see why not. You probably came to the same conclusion as I (and @Sleafar) did now. $\endgroup$
    – Hackiisan
    Sep 3, 2015 at 20:22
0
$\begingroup$

Here is how I would do it (assuming a multimeter which is accurate enough).

  • order the fuses to groups of $1, 2, 3, 4, ...$
  • the remaining fuses (last group) won't take part in the measurement
  • each group is ordered as a series of resistors, the total resistence of each group with $i$ fuses is $R_i = i * 1\Omega$
  • arange each group in parallel for the measurment, the total resistance of the setup if all fuses are OK should be $R = \frac{1}{1/R_1 + 1/R_2 + ...}$
  • if the total resistance is as defined above, then the broken fuse is in the group which wasn't measured
  • otherwise determine the group based on the result of the measurement
  • repeat the procedure with the smaller group

Max number of fuses $F$ for $j$ measurements:

  • $F_1 = 2$
  • $F_j = F_{j-1} + F_{j-1} + (F_{j-1} - 1) + (F_{j-1} - 2) + ... = F_{j-1} + \frac{F_{j-1} * (F_{j-1} + 1)}{2}$
Measuerements 1 2  3   4 ...
Fuses         2 5 20 230 ...

Example with 9 fuses:

  • 1 fuse with $R_1 = 1\Omega$
  • 2 fuses with $R_2 = 2\Omega$
  • 3 fuses with $R_3 = 3\Omega$
  • remaining 3 fuses not used

Measured value is:

  • $0.5454..\Omega$ => broken fuse is in not measured group
  • $0.6666..\Omega$ => broken fuse is in 3rd group
  • $0.75\Omega$ => broken fuse is in 2nd group
  • $1.2\Omega$ => broken fuse is in 1st group (with only 1 fuse, so we are done)
Improve this answer
$\endgroup$
1
  • $\begingroup$ With some optimizations (borrowing ideas from @f'' 's answer), you can slim your solution to 2 measurements... or less! $\endgroup$
    – Hackiisan
    Sep 3, 2015 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.