-2
$\begingroup$

About 30 years ago, I bought a memory extension card. At first, I was hesitating: there were 8 dip switches and no manual. Then the owner recalled that 4 switches indicated the memory on the motherboard and 4 switches configured the card. In the worst case, how many switches had I to flip? (0000 0011 -> 0000 0100 means 3 flips)

Hint: I had to set one combination, if it did not boot, another one and so on.

Just for fun: the card was populated with 2MB, the cost was 1,000 USD, the weight something like 300g and I do not think it needed less than 20W. The SD card in my phone has 64GB. What would be the other parameters with that technology?

$\endgroup$
4
  • 5
    $\begingroup$ I think the question needs some clarification. How many switches had you to flip in order to achieve what goal? (To set the four that configure the card correctly? To set all of them correctly? Something else?) Did you know which four switches perform which functions? Did you know what settings the switches needed to be set to? If this is a puzzle about finding sequences of settings to try, could you assume that it was safe to get the settings wrong and that you'd be able to tell when you had them right? $\endgroup$
    – Gareth McCaughan
    Commented May 13 at 18:09
  • $\begingroup$ Agree all the questions of @Gareth McCaughan and add some. Is it rational to assume memory swithes are either left 4 or right 4? Is it acceptable if configuration is OK, but memory not optimal? If unsafe selection peformed which procedure is required to reset the state? $\endgroup$
    – z100
    Commented May 13 at 18:51
  • $\begingroup$ The goal is to find the correct combination of the dip switches, otherwise the system does not work.The bet is the four that configure the card are set correctly, but you cannot know whether that are the first four or the last four. "could you assume that it was safe to get the settings wrong" yes, the system does not pass the memory check and does not boot. "that you'd be able to tell when you had them right" yes, the system boots. "Is it rational to assume memory swithes are either left 4 or right 4?" Yes, there never is a mix. "Is it acceptable if configuration is OK...l?" ???? $\endgroup$
    – kaksi
    Commented May 13 at 19:31
  • $\begingroup$ I mean (and you confirmed) that four switches to configure card should be correct - what about the other four memory indicated? $\endgroup$
    – z100
    Commented May 13 at 21:37

2 Answers 2

2
$\begingroup$

If I'm correctly understanding the clarifications given by OP in comments, the situation is as follows:

  • We have to get all 8 switches set correctly.
  • Either the first 4 are already correct, or the last 4 are already correct, but we don't know which.
  • Any incorrect setting will make the machine fail to boot (but won't do permanent damage).
  • Our goal is to minimize the total number of switch-flippings in the worst case before we get the machine to boot.

So far as I can make out:

  • There is no advantage in trying to "interleave" cases where the first 4 bits are already right and cases where the last 4 bits are already right.
  • In the worst case, we will guess wrong about which four bits to try changing first, and then the correct switch configuration will be the last one we try.
  • We can loop through all 16 configurations of a set of 4 switches while only changing one switch at a time, using a Gray code.
  • So we will start by trying to use the card as is (which will fail); then we will cycle through 15 other configurations of the "wrong" four switches, changing one switch each time; then we will switch one switch, bringing us back to the starting configuration which we needn't try again; then, 15 times, we will change one of the "right" switches, and after the last of these we will succeed.
  • That's a total of 31 switch-changes. We rebooted the machine after each change except for one in the middle, but we also tried to boot it before changing any switches. So a total of 31 boots too.
  • If I were actually doing this, the boot time would exceed the switch-changing time by enough that I would prefer to keep it simple and just go through the switch configurations in the order 0000, 0001, 0010, etc.; the time wasted switching more switches than necessary would be repaid by the reduced chance of making a mistake.
$\endgroup$
1
  • $\begingroup$ Very well, the key was the Gray code and the catch that the switches have to be reset to the initial position after the first cycle. I still persist that all the necessary information is in the original wording. Real world problems are not "Calculate 5,000 divided by 850" but "How long it takes to fly from London to NY." Your last remark takes into account that the mathematical solution is not all. In principle, I agree. However, the switches are expected and probably designed to be set once or twice, so I opted for the Grey code. $\endgroup$
    – kaksi
    Commented May 15 at 11:11
1
$\begingroup$

In the worst case, there's only one working combination, and it is the last one (256th) you try. This means you have switch to a different combination 255 times. (You don't need to switch anything to test whichever setting that was already selected.)

Now the question is, can you always flip just one switch, or will you have to flip multiple ones between some combinations?

Turns out that

Regardless of the initial state, there's always a way to order the full set of all combinations so that there's only a single switch flip between any two consecutive states.

Proof:

N=1: For one switch, you only need to flip once, regardless of the initial position.
N=2: The second switch is initially in some position, so do N=1, flip the second switch, and do N=1 again, for a total of 3 flips, regardless of the initial position.
N=3: The third switch is initially in some position, so do N=2, flip the third switch, and do N=2 again, for a total of 7 flips, regardless of the initial position

So in the general case, we get

The Nth switch is initially in some position, so do N=N-1, flip the Nth switch, and do N=N-1 again, for a total of 2^N-1 flips, regardless of the initial position

For our particular case with 8 switches then, if you use the optimal method, you won't have to flip a switch more than

2^8-1 = 255 times.

$\endgroup$
1

Your Answer

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

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