19
$\begingroup$

The Question

(Some knowledge of potential difference, resistor combinations, etc. required)

You have 1000 boxes. Some (or none) of them are conductors (of negligible resistance). The rest are insulators (of infinite resistance). Your job is to tell how many of them are conductors. You don't need to identify them.

You have an unlimited supply of wire, cells and resistors. You also have special fuses that give information. You must design a circuit that gives you the answer based on the information from the fuses. (You have no other materials/devices/tools available.)

Each fuse can take upto 1 ampere. After this, it burns. Though theoretically not true, assume that it takes one second for a fuse to burn, irrespective of the current (above 1A) flowing through it. Each fuse emits a unique wireless signal when it burns. These signals are displayed on a computer.

On switching on all cell(s) simultaneously, you get information from the fuses. You cannot make any changes to the circuit and must keep it running forever (or until the fuses break the circuit). Using this information from the fuses (and knowing the circuit arrangement), you must be able to tell the number of conducting boxes.

How many fuses do you need?

Hints and notes

1. You can create a fuse of any load (not just 1A), by combining a fuse with one of two resistors in parallel. Current divides in ratios in resistors, so you know how much of the net current enters the fuse.

2.A fuse may burn because another fuse has already burnt.

3. Though I have not solved it, I suspect the answer could be as less as 8 or 9 fuses. For example, just 3 fuses can (possibly) test 25 boxes as there are so many possible outputs by the computer:

None, 1, 2, 3, 1 and 2, 2 and 3, 3 and 1, 1 then 2, 1 then 3, 2 then
3, 2 then 1, 3 then 1, 3 then 2, 1 and 2 then 3, 1 and 3 then 2, 2 and
3 then 1, 1 then 2 and 3, 2 then 3 and 1, 3 then 1 and 2, 1 and 2 and 3

4. @user3294068 says it can be done using just 5 fuses (mathematically, at least)

5. There was a clarification in one of the comments. You can connect many wires to a single box. You cannot cut a box apart, since I have not provided you a saw/machine to do so.

Update

Bounty awarded but question remains open.

$\endgroup$
  • $\begingroup$ Good thing you said info from the fuses I was going to set up a magnetic field and then move the stuff around and see what got hot. $\endgroup$ – Going hamateur Jul 29 '15 at 12:57
  • $\begingroup$ @Goinghamateur I never said you can use a magnetic field. $\endgroup$ – ghosts_in_the_code Jul 29 '15 at 14:54
  • 5
    $\begingroup$ Hence: "Good thing you said info from the fuses I was going to" also if I have current and wires I can make me some magnetic fields. $\endgroup$ – Going hamateur Jul 29 '15 at 14:58
  • $\begingroup$ Re hint 1: Is a fuse combined with a resistor really equivalent to a single fuse with some larger load? $\endgroup$ – Julian Rosen Jul 30 '15 at 2:11
  • 1
    $\begingroup$ @Rob like a wire that has been cut. $\endgroup$ – frodoskywalker Jul 30 '15 at 19:30
8
$\begingroup$

I can't draw a circuit diagram right now (see below), but I think I have a way for two fuses to test three boxes.

Connect each box in series with a 1 ohm resistor. Connect fuse 1 in series with a 1 ohm resistor. Connect fuse 2 in series with a 2 ohm resistor. Now connect all of the preceding parts together in parallel. Finally make a circuit with that, a 2 ohm resistor, and a 9 volt battery in series.

If all boxes are conductors, no fuses blow. If two are conductors, fuse 1 blows and fuse 2 doesn't. If one is a conductor, fuse 1 blows followed by fuse 2. If none are conductors, both fuses blow at the same time.

If this works, we can construct 333 copies of it and use one more fuse to test the last box, lowering the upper bound to 667.


5 boxes can be tested with 3 fuses with a similar setup. Each box gets a 3 ohm resistor and the fuses are connected to resistors of 2 ohms, 3 ohms, and 4 ohms. The circuit is completed with a 3 ohm resistor and an 18 volt battery. 200 of these can test all the boxes with 600 fuses.

It might be possible to extend this kind of circuit to test 1000 boxes with 501 fuses.


I've added a rough diagram (drawn in MSPaint) 3 boxes 2 fuses

$\endgroup$
  • $\begingroup$ Just ran through the numbers - I can confirm that it works with these numbers. $\endgroup$ – Rob Watts Jul 30 '15 at 20:02
8
+250
$\begingroup$

It can be done with 63 48 44 fuses (22 at top and bottom).

The basic idea is that there's a top and bottom circuit in parallel, and a fuse will blow in whichever circuit has lower resistance. This will increase the resistance of that circuit and the process will repeat. The bottom circuit therefore establishes roughly how many insulators there are, and the top one refines that estimate.

Overall circuit is show here (where $n$ is the number of boxes that insulate, and the circles are the fuses) Circuit to measure 1000 ohms

Box circuit that gives an equivalent resistance of $n\Omega$ where $n$ of the boxes are insulators Equivalent circuit There are three groupings:

  1. The 1000 boxes, which are each in parallel with a resistor of resistance $1\Omega$, and combined in series to give a total resistance of $n\Omega$.
  2. 22 fuses on the top: the first shorting the box resistor, and the other 21 with a $2\Omega$ resistor.
  3. 22 fuses on the bottom each with a $44\Omega$ resistor and a fuse

A 2A current source (easily made with a voltage source and a large resistor) supplies 2A to the circuit, which means that more than 1A will be going through one fuse or other at all times (or it will be balanced, and both will blow).

Since the fuses are short circuits, only one fuse from the top and one from the bottom could possibly burn out. The order will depend on the value of $n$. The bottom fuses go first until $44k<n<44(k+1)$ for some $k\in(0,1,\ldots,22)$.

Then the top fuses go subtracting $2\Omega$ at a time until the value of $n$ is reached (equality) or surpassed, from which the value can be deduced.

This basic idea scales as roughly $\sqrt{2N}$ where $N$ is the number of boxes. I've tested this with some simple python code, and it works in all 1001 cases.

$\endgroup$
  • $\begingroup$ Why make sure that the top and bottom are never equal? If they are equal, either both fuses burn out simultaneously, or both can carry the current without burning out. Then you know exactly what $n$ is! $\endgroup$ – f'' Oct 30 '15 at 1:18
  • $\begingroup$ Good point. I wonder then if you can make it a trinary set and reduce the number of measurements. I just did it to make the order entirely unambiguous $\endgroup$ – Dr Xorile Oct 30 '15 at 1:40
  • $\begingroup$ You can, but not by much. I would accept this answer if you can provide a single set of resistor values that supports all 1024 box states. My answer theoretically supports up to $n(n+1)/2$ states but only $2n$ of them ended up not being mutually exclusive. $\endgroup$ – Hackiisan Oct 30 '15 at 1:57
  • $\begingroup$ Allowing the top and bottom to match lets you eliminate the two $1\Omega$ resistors and their fuses, so you can do it with 18. $\endgroup$ – f'' Oct 30 '15 at 3:04
  • $\begingroup$ @DrXorile What I mean is, I think you might be overcounting on the number of different fuse combinations. I don't think all 1024 possibilities can be represented simultaneously in this configuration (but I could be wrong, so I asked instead if you could flesh out your solution a bit more in terms of the readout). $\endgroup$ – Hackiisan Oct 30 '15 at 7:27
4
$\begingroup$

I think this is how we can construct a solution with 501 fuses 32 fuses. (Previous 45-fuse solution turned out to be incorrect... sorry =( ...)


501 fuses

This is the general diagram:

Circuit diagram for N boxes, N/2 fuses

Let $N = 1000$ be the number of boxes, $0 \leq m \leq N$ be the number of conductor boxes, $ s = N - m$ be the number of insulator boxes, and define $A = \sum_{i=1}^{F}{a_i}$.

Then, from the above circuit diagram, it can be shown that the current across each fuse before the switch is turned on is: $$I_j = \frac{V_0}{R(mk+A)+1}a_j$$

To find the 501-fuse solution, we want:

  • no fuses blown: no insulators
  • 1 fuse only blown after 1 s: 1 insulator
  • 1 fuse blown, another fuse blows 1s later: 2 insulators
  • 2 fuses only simultaneously blown after 1s: 3 insulators
  • 2 fuses blown, another fuse blows 1s later: 4 insulators
  • 3 fuses only simultaneously blown after 1s: 5 insulators

... and so on. This means we need $F = N/2+1 = 501$ fuses to distinguish $N=1000$ fuses.

For simplicity, set $R = 1 \ \Omega$ and $k = 2 \ \Omega$. To not blow any fuses when there are $s= 0$ insulators, but blow the first fuse when there are $s=1$ insulators, we have the following inequality for $a_1$: $$\frac{2N+A-1}{V_0} < a_1 < \frac{2N+A+1}{V_0}$$

Here, we can set $a_1 = 1$ and $V_0 = (2N+A) \text{ volts}$. We can similarly find inequalities for any $a_j, j \in (0,N/2+1)$ as:

$$ \frac{2N+A-(\sum_{i=1}^{j-1}{a_i}+2(j-1)+1)}{V_0} < a_j < \frac{2N+A-(\sum_{i=1}^{j-1}{a_i}+2(j-1)-1)}{V_0}\\ \Rightarrow \ a_j = 1-\frac{\sum_{i=1}^{j-1}{a_i}+2(j-1)}{V_0} \pm \frac{1}{V_0} \ \cdots\cdots\cdots \ (*)$$

Therefore, if we pick the midpoint of each inequality as the value of $a_j$, then we have: $$a_j - a_{j+1} = \frac{a_j+2}{V_0}$$

Solving this recurrence relation gives us the explicit solution of $a_j$ in terms of $V_0$ as: $$ a_j = 3\left(1-\frac{1}{V_0}\right)^{j-1}-2 \ \cdots\cdots\cdots \ (**)$$

Using equation $(*)$, we can obtain $a_{N/2+1}=\frac{N}{V_0-1}$, which we can now substitute $a_{N/2+1}$ into equation $(**)$ and solve for $V_0$.

Since $A = \sum_{i=1}^{F}{a_i} < N/2+1$, I numerically searched for a root of equation $(**)$ in the range of $(2N, 2N+A) \approx (2000,2500)$ and found $V_0 \approx 2352.96438 \text{ volts}$ as a unique solution (as long as the voltage is accurate up to $\frac{1}{V_0} \approx 4\times10^{-3} \text{ volts}^{-1}$ it should be fine).

Substituting this value of $V_0$ into equation $(**)$ to solve for $\{a_j\}$ gives us the construction.


32 fuses

To get a 32-fuse solution, we generalize our solution by adding new $G$ new fuses $\{b_k\}$ into the circuit.

This is the general diagram:

Circuit diagram for N boxes, sqrt(N)/2 fuses

Let $N = 1000$ be the number of boxes, $0 \leq m \leq N$ be the number of conductor boxes, $ s = N - m$ be the number of insulator boxes, and define $A_j = \sum_{i=j}^{F}{a_i}$ and $B = \sum_{i=1}^{G}{b_i}$.

Then, from the above circuit diagram, it can be shown that the current across each pf the top $F$ fuses before the switch is turned on is: $$I_j = V_A a_j = \frac{V_0}{R(\frac{mkB}{mk+B}+A_1)+1} a_j$$ $$I_\ell = \frac{V_A mk}{mk + B}b_\ell = \frac{V_0}{\frac{(RA_1+1)B}{mk}+B+RA_1+1} b_\ell$$

Consider the regime where the total resistance of the $G$ lower fuses, $1/B$, is perturbational, i.e. $B \gg Nk$. In this case, we can approximate the above two current equations as:

$$I_j \approx \frac{V_0}{R(mk+A_1)+1} a_j$$ $$I_\ell \approx \frac{V_0}{R(mk+A_1)+1} \frac{mkb_\ell}{B}$$

Under this approximation, $I_j$ is as before, and $I_\ell$ scales linearly with the fraction $mkb_\ell/B$. This is suggestive of a nested readout.

Let $(p_a q_b|r_a s_b,...)_a$ denote the scenario where $p$ fuses from group $a$ blow simultaneously after 1 sec, then $y$ fuses from group $b$ blow simultaneously after 2 sec, etc., until no more fuses blow. The pipe denotes the current time point, e.g. $(x|y,z)$ means the time is now between 1 and 2 sec, i.e. after $x$ fuses have blown simultaneously, but before $y$ fuses will blow simultaneously.

Now consider the following readout scheme:
$(0_a 0_b, 0_a 0_b): 0$ insulators
$(0_a 1_b, 0_a 0_b): 1$ insulators
$(0_a 1_b, 0_a 1_b): 2$ insulators
$(0_a 2_b, 0_a 0_b): 3$ insulators
$\cdots$
$(0_a 15_b, 0_a 1_b): 30$ insulators
$(0_a 16_b, 0_a 0_b): 31$ insulators
$(1_a 0_b, 0_a 0_b): 32$ insulators
$(1_a 1_b, 0_a 0_b): 33$ insulators
$...$
$(16_a 16_b, 0_a 0_b): 1023$ insulators

Thus, $F = G = \sqrt{N}/2$, and $F + G = 32$ fuses can be used to distinguish $N = 1000$ fuses. For simplicity, set $R = 1 \ \Omega$. Similarly as above, we have the following inequality for $a_1$: $$(N+1-F)k+A_1 < a_1 V_0 + 1 < Nk+A_1$$

Correspondingly, we have the following inequalities for any $a_{j \geq 2}$ as:

$$(N+1-jF)k+A_{j-1} < a_j V_0 -1 < (N+1-(j-1)F)k+A_j$$ $$\text{subject to } 2(N-F) > a_1 > a_2 > ..., \forall a_j$$

To determine $b_\ell$, since $\{b_\ell\}$ is decoupled from $\{I_j\}$ in the perturbation approximation, we can always set $b_\ell = \ell B_0/G$ (where $B_0$ is a constant sufficiently large such that $\frac{B_0}{k} \gg N$) and choose $k$ and $\{a_j\}$ such that:

$$N+1-jF < \frac{a_j}{k} < N+1-(j-1)F$$

The final set of inequalities can then be solved to obtain an approximate solution, as demonstrated above for the case of 501 fuses. Since $k$ and $B_0$ are unconstrained, a solution for when the approximation is not applied must also exist.

$\endgroup$
  • $\begingroup$ Do you have a way to reduce this to 32 fuses? I got the impression that you did from your comment in the OP $\endgroup$ – Dr Xorile Oct 31 '15 at 4:34
  • $\begingroup$ Let me post my solution for 45 fuses first. The 32-fuse answer builds on it (if it works... intuitively the 32-fuse answer does work but writing it out is a pain so I'm not sure as of now). I originally thought no-one would challenge my 501-fuse answer so I didn't work on it =) $\endgroup$ – Hackiisan Nov 3 '15 at 5:58
  • $\begingroup$ @DrXorile Ok, added. I like how our answers are dual to each other right now (mine being a top-down approach, and yours being a bottom-up approach). $\endgroup$ – Hackiisan Nov 3 '15 at 7:21
  • $\begingroup$ Wouldn't (16,16,0,0) be 543 insulators? It looks like (n,0,0,0) - >32n insulators, and you're adding 31 more to that. $\endgroup$ – Dr Xorile Nov 5 '15 at 13:41
  • $\begingroup$ @DrXorile You can also split the top 16 fuses over 32 states (pairs of $(n-1,1)$ and $(n,0)$), similar to what I have for the 501-fuse solution. Although each state pair gives the same total resistance (for the top fuses) after 2 seconds, we can still distinguish between them at the readout. $\endgroup$ – Hackiisan Nov 5 '15 at 18:23
2
$\begingroup$

I don't have an answer, but I can provide limits.

Obviously, the upper limit for the problem is 1000 fuses. Just wire 1000 simple circuits, each with a 10V cell, a fuse, a $5 \Omega$ resistor, and a box.

Surprisingly, the lower limit is $5$. This represents the minimum number of fuses that can blow in at least $1001$ different orderings.

The constraints of the problem are: construct the circuit with all cells disconnected, then flip a switch that simultaneously connects all cells, then observe which fuses blow in which order. The number of possible variations (taking into account that some fuses may not blow at all and that some groups of fuses may all blow at once) is, for $n$ fuses:

$$ F(n) = 2 \sum_{i=1}^n P(n,i) i!$$

Here, $i$ represents the number of groups of fuses that blow simultaneously (or do not blow at all), and $P(n,i)$ is the number of ways of partitioning $n$ distinct elements into $i$ groups. The factor of 2 is due to the fact that the last group might not blow, yielding $i-1$ events, with some fuses unblown.

This crosses $1001$ at $F(5) = 1082$.

  • 240: 5 groups: each fuse blows at a different time (at most one fuse unblown).
  • 480: 4 groups: 1 group of 2, and 3 groups of 1.
  • 300: 3 groups: 1 group of 3, 2 groups of 1, or 2 groups of 2 and 1 group of 1.
  • 60: 2 groups: 1 group of 4, 1 group of 1, or 1 group of 3, 1 group of 2.
  • 2: 1 group: all fuses blow simultaneously, or no fuses blow.

For further clarity, I'll break out the 3 group case:

For 1 group of 3, 2 groups of 1, there are ${5\choose 3} = 10$ arrangements of which fuses are in the group of 3. For 2 groups of 2, 1 group of 1, there are ${5\choose 2}=10$ choices for the first group of 2, ${3\choose 2}=3$ choices for the second group of 2, but the groups are interchangeable, so we need to divide by $2$, yielding $15$ arrangements. Thus, $P(5,3) = 25$.

The 3 groups could blow in any order, so there are $3!=6$ orderings of groups blowing. Plus, there is the distinction that the last group might never blow, so that adds an extra factor of $2$. Thus, the total number of ways 5 fuses can blow (or not blow) in 3 groups is $25\times6\times2 = 300$.

So we have a lower limit of $5$ and an upper limit of $1000$.

What I find fascinating is that I have yet to come up with any circuit that solves the problem with fewer than $1000$ fuses. Any circuit I come up with that has some fuses blow first and others later ends up using as many fuses as a circuit that wires the fuses independently.

Can anyone come up with a better upper limit?

$\endgroup$
  • $\begingroup$ Thanks! I was guessing 7 or 8 to be the lower limit. $\endgroup$ – ghosts_in_the_code Jul 31 '15 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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