Today I was leisurely wandering about the Internet as I am wont to do, and I came across a page full of logic problems and riddles. All of the solutions were recorded on other pages which were all conveniently broken. One problem in particular caught my attention. I'll paraphrase it here.

There are 1000 men and 1000 closed doors. The first man opens each door. The second man closes each even door. The third man closes door 3, opens door 6, closes door 9, etc., and so on down the line. After all 1000 men have opened or closed doors in this fashion which doors are open?

I only thought about this for 30 seconds when I decided I had solved the problem. I didn't know the answer, but I knew how to obtain it. Here is the solution I came up with. I chose C++ for the built-in boolean type.

#include <iostream>

int main() {
    bool doors[1001]={false};
    int i,j;

    for(i=1; i<1001; i++)
        for(j=1; j<1001; j++)
            if(!(j%i))
                doors[j]=!doors[j];

    for(i=1; i<1001; i++)
        std::cout<<"Door "<<i<<": "<<(doors[i]?"open":"closed")<<"\n";
    std::cout.flush();

    return 0;
}

I'm glad that I understand how to solve problems with the computer because it's more valuable to understand how to solve problems than to know the solution to only one problem, but it saddens me that these puzzles don't hold the same magic that they did when I was eight years old.

ANSWER: Only the perfect square numbered doors will be open after all 1000 iterations (1, 4, 9, 16, etc.).


In response to the writeup below:
This was simply the first solution I came up with. This was not meant to imply that computers are a replacement for critical thinking, only that learning to program has forever changed the way I look at problem solving.

Melvil Dewey was making an assertion about the world when he lumped all books about non-Christian religions into a single category, listed last among books about religion.

~ Clay Shirky

We have just witnessed the first hammer blow to the Tower of Babel.

Amazingly, it was followed by a sledgehammer philosophical treatise that captured not only the teleology of human evolution but succinctly summed up the whole concept behind a story problem as it stands.

I am half-inspired to compose a manifesto.

At first, it appears the previous two writeups are at odds. jclast has created a programming algorithm that inelegantly answers the direct question at hand. eien_meru has countered with some insights into the mental processes required to answer the problem without a computer. The triumph of the mind over machine, as it were.

And yet ...

What we really see is that the cornerstone for our analytic mind is logic. We could, iteratively, repeat jclast's algorithm in our head (better get started now!) and store a mental array of all the doors left open. Yet instead we focus on what properties an open door would have - in this case, an odd number of factors - and deduce what kind of numbers have this property - perfect squares.

A computer, too, has the cornerstone of logic to preface it. Its only flaw in this problem is that jclast did not provide his algorithm with the same sense of mathematical logic that we possess. I propose an alternative algorithm, which satisfies eien_meru's call for "analytic reduction" of algorithmic timing:

for (NUM=1;NUM<=1000;NUM++) {
  if (isInteger(sqrt(NUM)) {
    DOOR[NUM] = 'open';
}

Or, the much faster algorithm:

NUM = 1;
while (N<1000) {
 N = NUM * NUM;
 DOOR[N] = 'open';
 NUM++; 
}

The question then becomes how do we get the computer to evolve itself from jclast's brute-force into this sleeker, more knowledgable algorithm. Such is the very essence of artificial intelligence studies.

But beyond the technical aspects of the problem and its solutions, what I see here is really that we are all speaking the same language now, the language of math and logic and bits and bytes. This is appropriate - we're talking about a math problem after all - but what we are really talking about is how we process information versus how computers process information.

In the new Semantic Web, there is a major attempt being made to bridge the gap between these processes. We want a computer to be able to take our information about something, process it via a known system of interpretation, and provide us with output relevant to our input. Programming, search engines, shopping, maps, games, academia, media content, and any other types of information that rely on an I/O model of interface will benefit from this bridging.

But, as I quoted Clay Shirky earlier, the problem is the "known system of interpretation." The great librarian Mr. Dewey was singularly (and perhaps unconsciously) biased against non-Christian religions. Yet his system became the law of the bibliotecque, and here we are today.

eien_meru has pointed out not a flaw in jclast's results, but in his approach to the problem. The problem with the problem, as it were, is that a computer cannot interpret it in any meaningful way. If we were to define the general rules behind the problem in a machine-readable way, and then simply asked the computer to solve which doors were open, how would it go about doing that?

Well, we'd define men as 1000 and doors as 1000. We'd have to come up with some sort of function to explain that each man opens the doors that are a multiple of his number. And then we'd say we want to know which doors are open.

Uhh ... yeah. That sounds an awful lot like jclast's algorithm above. How do we implement eien_meru's line of thinking into our program? Let's suppose we gave the computer the answers first, and then asked it to explain why it was so. In fact, our only assumption, based on the idea of the story problem, is that somehow the open doors will be related to each other in a meaningful, nonrandom way.

So we define the various mathematical operations: adding, subtracting, multiplying, dividing, and exponents. We then hand it a list of numbers saying "1, 4, 9, 16, 25" and ask for the rule that explains this list of numbers, and to predict the next 2 numbers. (Remember doing this in school?)

Now the computer must also come to the simple (but abstract) logical point that open doors will have been touched an odd number of times. So we must explain to it the difference between odd and even (n % 2). It is easy for us to look at "337, 109, 5, 2199" and say what is in common between them. For a computer, it is much more difficult. But it could be taught to compare numbers for evenness and oddness first, as a stepping stone to further computation.

Finally, the computer must connect these two ideas (the open doors have all been touched an odd number of times, the open doors are all perfect squares) to form the final idea (All perfect squares have an odd number of factors) which is at the heart of the problem. Here, basic logic takes us the final step: for all A, doors are open. For all B, doors are open. Therefore, if doors are open, A & B.

Here, the computer's worldview is not based on some arbitrary sense of interpretation, a simple brute-force tool that calculates a predetermined (but unknown) output unrelated to the problem, but instead comes to life, drawing on the basic mathematical connections and ideas we have provided it and then logically "steps through the looking glass" to arrive at the same critical thinking solution the original story problem offers.

The Tower of Babel comes crashing down when we can begin to explain our critical thinking concepts in terms of computer processing. The future language is binary. We can create associations, identities, truths, and proofs in a virtual world. What we are witnessing is not the clash of civilization, but the interpolation of man's intelligence and machine's power.

We must make our robots smarter.

We must bring our children together.

We can engineer our own future.

Welcome to the new math.

Log in or registerto write something here or to contact authors.