More Solutions

For those who are still around, it was recently pointed out to me that I'd forgotten to give the solutions to the last couple of unsolved problems from my Skeptic's Circle. Since it's been a while, I'll repeat the problems here to remind you before solving them:

Super-Scammer Secrets

Lord Runolfr recently got a couple of e-mails from scammers, raising my suspicions that something big was afoot behind the scenes. I called up a few contacts, did some research, hired a few James Bond-alikes, and here's what I've figured out:

There's some evil mastermind behind the whole plan, and he's about as supervillanous as they come. This of course means that he wants to capture one of my James Bond-alikes and subject him to an intricately detailed explanation of his evil plan before killing him in a creative way. Apparently, the way he's decided to go about this revelation is through an overhead transparencies with the key points of his evil plan (you'd think he'd have better technology than my high school, but he's out to make money, so he saves it where he can).

Now of course, he's wary of this transparency falling into the wrong hands, so he's come up with a plan to keep things safe. He's figured out some method to spread the information across multiple sheets, arranging it so that if we get a hold of any two, we'll still have no idea what he's planning. So, what we need to figure out now is some possible ways he might have done this, so if we manage to get our hands on more than two, we'll know how to read them (if it's not immediately obvious). What are some possible things he could do? Remember that he's out to save money, so splitting it up to have a single word on each slide or something huge like that doesn't seem too likely.

Solution

While it's possible to split up the information in a simple way over many slides, the trick to this problem is finding a way to divide it up so that absolutely zero information is transmitted in a single slide, or even in two slides. Splitting it up into words or letters (or fragments of a letter) never accomplishes this, as the remaining pieces still give some information. To illustrate a way of transmitting zero information in a simpler case, where any one slide can be lost, I gave the following sample solution:

Pixelate the presentation, and make sure the pixels are quite large and easily distinguishable. Generate one transparency that's completely random, with each pixel being randomly either transparent or 50% opaque. Then, for the second sheet, for the places where the message is spelled out, choose either transparent or 50% opaque as necessary to make the pixel result in 50% opaque. For places where the message isn't, match the pixel to the one on the other slide. The result will be the message appearing in gray text on a mixed black and white background.

Now the trick is moving up to a case where any two slides can be lost, and together they'll give zero information. Part of what makes this problem tricky is that everyone tries to find a solution that will use the absolute minimum number of slides at first (in this case, 3). However, such a solution doesn't exist (at least that I've seen, and I tend to suspect it doesn't at all). There is, however, a solution that uses 4 slides.

Here's how to construct the 4-slide solution: As before, pixelate the message. This time, however, instead of filling the pixels with either gray or white, we'll be filling them with one of three colors of ink. This ink will be designed to absorb one third of the visible light spectrum and let the rest pass through. For instance, we could have ink that absorbs red wavelengths, allowing blue and green light through (which appears as cyan I believe), plus ink to absorb blue (appears as yellow) and ink to absorb green (appears as magenta). If we stack the three different colors on top of each other, no light can get through, and we'll have a black spot on the image. If only two colors are in the stack, it will appear as the remaining color. If just one color, we'll get a mix of the other two.

Now, for each pixel of the image, first determine whether it's part of the message or not. If it is, we want it to appear black. So, through the four slides, we'll arrange it so all three colors show up somewhere, plus one of them appearing twice. We'll randomly choose between all possible permutations that do this. Now, for pixels that aren't part of the message, we want them to not appear black, so we randomly choose one of the permutations that uses only one or two colors. The net result is the message appearing in black on a multicolored (or gray, if the pixels are small enough) background.

To see that this works, image that two slides are stolen, and look at a single pixel on both of them. There are two possibilities here: 1) both slides have the same color for that pixel and 2) the slides have a different color in that pixel. In case 1, it's possible for the remaining two slides to have the other two colors, and it's also possible they might repeat this color. For case 2, it's possible the remaining color will be on one of the other slides, but it's also possible it won't be. In the end, we can't infer anything about whether or not this pixel is part of the message.

Now, why won't this work for only three sheets? Well, let's go back to case 1 if two slides are recovered. If both slides have the same color, there's only one slide left to block more light. This third slide couldn't have both colors, so this pixel cannot be part of the message. We can't infer anything from the cases where the two slides have different colors in a pixel, but we can still gain some information by picking out some pixels we know can't be part of the message (we'll catch 1/3 of them on average, and if the pixels are small enough, we might be able to glean some of the actual message).

What Wifi Woo?

Sandy Shwarc reports that there's been some scare over the ill effects of all the elctromagnetic radiation going through the air, but I'm not buying it. Personally, I think this is all just an excuse to avoid having to work. Confused? Let me explain.

Take the new Ultra-Mega-Awesome Wifi tower built the other day. It had 1000 power cords going from the bottom to the top, and not one of them was initially hooked up to anything. Worse, they're all tangled in the middle so it's impossible to figure out which bottoms of wires correspond to which tops.

Now, some poor shmuck has to go and sort them all out, and the only tools he's given are a battery and a lightbulb. They somehow expect him to to hook up the battery at the bottom to a couple of wires, then go to the top and see which wires he can connect the lightbulb to to sort them out. Maybe he could pull a few tricks like tying some wires together at the bottom or top to make long wires, but it's still going to take him quite some time.

With that job ahead of him, you can see why he'd want to believe it shouldn't be done. Maybe if we could help him out and figure out the most efficient way to solve this problem, he'll be a bit more likely to accept Wifi. The tower's pretty tall and the only way up is by stairs, so he'd probably appreciate most if we could help minimize the number of trips he has to take, regardless of how much work he has to do at the top or bottom. How can we do this, and what is the minimum number of ascents and descents required?

Solution

The solution to this is pretty complicated, but it helps to look at a simpler case. Let's say we only have 3 wires. In this case, here's how you do it with just one ascent and descent: Start at the bottom. Tie two of the wires together. Mark both of these “2-_”. Mark the loose wire “1-_” (a group of 2 and a group of 1). Now ascend to the top. Hook the battery and lightbulb together, and connect one wire to one end of this assembly. Test each other wire on the other end, and count how many wires will allow the lightbulb to light up. If one wire will cause it to light up, then mark the test wire with “2-_”. If no wires will light it up, mark it with “1-_”. Repeat for all the wires.

Now, at the top you'll have two groups of wires, one of just one wire, and one of two wires. You know that these correspond to the groups you made at the bottom (and the one-wire group has the single wire properly identified). To sort between the wires in the 2-wire group, we need another step. Now, take the wire in the 1-wire group and tie it to one of the wires in the 2-wire group. Mark both of these “X-2” (where X is whatever mark was in the first digit). Mark the other wire “X-1” and leave it unconnected to anything.

Descend to the ground, and repeat what you did when you first got to the top, except this time, fill in the second digit (if it connects to zero, mark 1, if it connects to 1, mark 2). Now, at the top and bottom you'll have wires marked “1-1”, “2-1”, and “2-2”. These IDs match them all up to each other. It says nothing in your job description about untying the wires at either end, so you're done, with one ascent and one descent.

This solution type can be extended simply to any number which is a perfect triangle (1,3,6,10,15...). For instance, with 6 wires, you'd tie up one group of 3 at the bottom, one group of 2, and one group of 1. You can then identify these groups at the top. Then, you can tie up a group of 3 taking one from each bottom group, a group of 2 taking one from the 2 and 3 bottom groups, and a group of 1 from the 3 bottom group. Go back to the bottom to sort out these groups and you've identified them all.

The problem gets trickier, however, when the number you have isn't a perfect triangle. Since 1000 isn't one of these, we'll have to face this. But, it is possible to extend this solution to most non-triangular numbers. The trick is dump the extra wires into the group where the wires aren't connected to any others. Let's look at the 8-wire case to see this.

At the bottom, set up three groups. The first group (1-_) has three wires not connected to each other, and not connected to any others. The second group (2-_) has two wires connected together. The third group (3-_) has three wires all connected together. Go up to the top and identify all of these groups. Now, to set up the top groups. Set up one group which takes one wire from each of the bottom groups, and tie all of these together (X-3). Set up a second group which takes one wire from each of the bottom groups, and leave all of these tied to nothing (X-1). You'll be left with one wire from the 1-bottom group and one wire from the 3-bottom group. Tie these together in the final group (X-2). Go back to the bottom and identify these groups. You'll then have eight wires, all uniquely identified.

However, it turns out there's a problem for some numbers of wires, such as 5 and 9. If you try to do it this way, you'll have too many wires in the group where they aren't connected to anything. I won't go into all the details here, but your best solution with this method is to have the extra wires in the unconnected group on both trips. You'll end up with two wires marked 1-1. Then, connect one of those to another wire when you're at the bottom (1-1a) and leave the other unconnected (1-1b). Go back to the top, and figure out which of the wires is 1-1a by testing its circuit with the one you tied the bottom end to, and the other is then 1-1b. You'll then have figured them all out with just one extra ascent (you also have to descent to go home, but that's just a technicality).

It turns out that this particular problem comes into play when the number of wires is one less than some triangular number. So, you get problems with 2, 5, 9, 14, and so on. The 2-wire case allows a special solution with only one ascent (attach both wires to the battery at the bottom, marking them with the pole they're attached to. Then go to the top and see which way you have to orient the lightbulb so it'll go on, and match up the poles), but the others will all require 2 ascents and 1 descent with this method to figure it out. Any other number can be done in 1 ascent and 1 descent with this method (3 wires can actually be done in a single ascent with a simple extrapolation from the 2-wire case). Since 1001 isn't a triangular number, our 1000-wire case can be done in just one ascent and one descent using our method.

Side note: There is another, much more complicated method which will allow you to solve this problem in just one ascent and one descent regardless of the number of wires. However, the average time this method takes is proportional to the number of wires to the fourth power; while the method I've given takes time simply proportional to the number of wires squared. For large numbers of wires, the extra time the other method takes at the top or bottom would easily outweigh the time of a single ascent of descent. However, for 5 or 9 wires, it might be worth it. I won't go into it here, though.