Antimail : Puzzles

Puzzle: create a Pentagon with rule and compass

AdiOltean — Thu, 27 Dec 2007 10:37:48 GMT

The title sums it all.

P.S. And, as a Christmas bonus, here is a nice chess puzzle.

In the above diagram you must add the two missing kings in such a way that White, who is on the move, can deliver immediate mate, i.e. mate in one move.

[source: ChessBase]

Puzzle solution: Xen voting algorithm

AdiOltean — Tue, 27 Nov 2007 00:19:38 GMT

I think that the problem stated in one of my earlier posts is one of the most fascinating puzzles I came across recently. Many people that got confronted with it said bluntly that the problem simply has no solution, otherwise it would contradict common sense, information theory, etc. But surprisingly, it does have a solution.

For X% strictly bigger than 50% the solution is known as the MJRTY algorithm, discovered a while back by R.S. Boyer and J.S. Moore (also called the Majority Vote algorithm). Although the algorithm is deceptively simple, its proof is not. the In the PDF cited above, the authors present a complete proof and also some interesting history around this non-trivial result.

The correct algorithm was also found by Lailin Chen - also presented in the post comments, but without a proof:

Well, Since we already knew there is one and only one who has more votes than any others, we can find him by letting the votes "fight" each other:
Picked the first one, say X1, count 1 for X1, then move on, if X1 repeats, add count to X1.
When X1 doesn't repeat, reduce the count by one, if it reaches 0, picked up the current one (say X2), and do the some counting to X2.
Keep doing this until the end. The last one left with a counting bigger than 0 is the leader:
X3 X1 X1 X2 X1 X3 X3 X3 X4
   ^
X3, 1
X3 X1 X1 X2 X1 X3 X3 X3 X4
         ^
       X3, 0
X3 X1 X1 X2 X1 X3 X3 X3 X4
               ^
            X1, 1
X3 X1 X1 X2 X1 X3 X3 X3 X4
                     ^
                   X1, 0
X3 X1 X1 X2 X1 X3 X3 X3 X4
                           ^
                          X1, 1
X3 X1 X1 X2 X1 X3 X3 X3 X4
                                 ^
                               X1, 0
X3 X1 X1 X2 X1 X3 X3 X3 X4
                                       ^
                                    X3, 1
X3 X1 X1 X2 X1 X3 X3 X3 X4
                                             ^
                                           X3, 2
X3 X1 X1 X2 X1 X3 X3 X3 X4
                                                    ^
                                                  X3, 1
So X3 is the winner.

Here is a more formal description of the algorithm:

- You have with two registers: an “candidate register” containing the name of some candidate (candidate), and a counter (counter).
- Candidate_register = NULL;
- Counter = 0
- For each new candidate:
     If (Candidate_register is NULL)
            Candidate_register = candidate
            Counter = 1
     Else If (candidate == candidate_register)
            Counter++;
     Else if (counter > 0)
            Counter --;
            If (counter == 0)
                Candidate_register == NULL
- At the end you have the correct candidate in the register.

For X < 50% we can adapt a more complex variation of the same algorithm which requires two passes instead of a single one. Instead of keeping a single register (keeping the last candidate) and its associated counter, we keep a number of K registers (with their associated counters) and run the same algorithm. The integer K is chosen such that 100/(K+1) < X. After this pass, we discovered K candidates but of course the candidate with the biggest counter might not be the real candidate. To find the top candidate we simply reset all counters to zero (but keep the candidates found) and re-run the same algorithm.

- Instead of maintaining one “element” register and one counter as in the main algorithm, you need to use K registers, each with K counters.
- First pass
     Initialize all candidate registers with NULL and counters with zero
     For each candidate in the log file
          If the candidate is in one of the K registers, increase its counter
          Else if there is one candidate register which is NULL, put it there and increase its counter with 1
          Else, reduce all counters by 1
               If some counters become zero, set their corresponding candidate registers to NULL
     At the end, each of the candidate registers contains every element with frequency > 100/(K+1). One of them is the winner
- Second pass
     Initialize all counters with zero, but keep the candidate registers filled with the values above.
     For each candidate in the log file
          If the candidate is in one of the K registers, increase its counter
     At the end, you have all the correct counters for all the candidate registers.
     Select the one that has the maximum count.

A variation of this second algorithm is briefly mentioned in this presentation although I could not find a formal article describing it.

What all these algorithms have in common? The fact that you know ahead of time that there is a winner, but you don't know which one. While the algorithms are simple to implement, this is a pretty strong condition that is not likely to be encountered in our real world. Maybe on a planet called Xen :-)

Puzzle: Xen voting algorithm

AdiOltean — Tue, 30 Oct 2007 07:52:00 GMT

There is a huge amount of aliens living on the Xen planet who want to elect their new leader (since their previous leader died a while back). They want to switch to a very democratic voting process, through the help of a very special communication field called the “vortessence”.

One interesting property of voting through vortessence is that it can tell them whether there is a certain unique leader which is guaranteed to meet a certain percentage of votes X% (which is a number chosen ahead of time and can be considered constant in this discussion). But the vortessence cannot be used to tell who is actually the winning leader.

So these aliens will also use the help of a computer to record the voting. The rules are simple:

The winner has to record at least X% votes (a unique leader is guaranteed to exist, as indicated by the vortessence)
Each alien votes exactly once, by indicating the name of the proposed leader.

After the voting season, the votes are recorded in a very large unsorted log file, containing the names of the voted aliens. Now, since there are a lot of aliens, they need to use an algorithm to figure out the leader, running in O(1) in space and O(N) in time (name comparisons can be considered constant).

In what conditions is this problem solvable, and if yes, what is the minimal number of log passes?

Simple probability problem

AdiOltean — Sat, 19 Aug 2006 09:20:25 GMT

I love probability puzzles. Here is one I liked:

There are a 100 people trying to get onto the same flight you are. The airplane has a 100 seats. You are all ready to board. You are the last one in the line of passengers at the gate. The first guy walks in to the flight and promptly realizes that he does not have his boarding pass on him and does not remember his seat number. So he picks one at random, hoping his charm will take care of the after effects. Every one else takes their assigned seat if it is available. If someone is already sitting on it they quietly look for an empty one and sit there. By the time you get in there is only 1 seat left. What is the probability that the seat which remains is indeed the one originally assigned to you?

Puzzle: prime numbers

AdiOltean — Wed, 08 Mar 2006 07:20:00 GMT

Show that (N^4 + 4^N) is a prime number if and only if N=1.

Puzzle: another probability problem

AdiOltean — Wed, 11 Jan 2006 05:45:00 GMT

If you have an urn who already contains either a black or white ball, and you add a white ball to it, and then you subtract a white ball from it, then what is the probability of having a white ball left?

[update: adding the fact that the original ball is either black or white]

Puzzle: probability problem

AdiOltean — Thu, 29 Dec 2005 00:56:00 GMT

Here is an interesting probability problem who recently generated long discussions in our team:

Say that you have an array of N boolean values, with all values initially set to FALSE. At each iteration step, you arbitrary pick an element in the array and set it to TRUE. What is the average number of elements set to TRUE after K iteration steps?

By the way, as an anecdotic fact, this problem came from analyzing paged pool memory consumption when you randomly access a large volume over time. I will not go in more details, but I just wanted to mention this problem as a particular application of theoretical statistics in the design of operating system components...

Math puzzle: minimum number?

AdiOltean — Wed, 30 Nov 2005 08:02:00 GMT

What is the minimum number that cannot be expressed with less than two english words? Also, how about less than thirteen english words?

Puzzle: all horses have the same color

AdiOltean — Wed, 14 Sep 2005 03:55:00 GMT

Several answers to my previous puzzle reminded me about an old result:

Theorem: All horses have the same color.

Proof: We demonstrate this by induction over N for all the sets of horses size of size N:
- N=1: The proof is true for N = 1 (any horse has the same color as itself, so the propery is valid for any set of size 1)
- (N-1) -> N: - Assuming that the property is true for any set of (N-1) horses, we need to proof that the property holds for any set of size N. Let's pick a random set of N horses and let's do the following trick. First, we take one horse out. There are (N-1) horses left which obviously have the same color, according to the induction. Now we put back the original horse and take another one out. We get again (N-1) horses, so the initial horse that we just added back must have the same color as the rest. In conclusion all the N horses have the same color. QED.

Now, why does this old puzzle come to my mind? Exercise left to the reader :-)

Two math puzzles

AdiOltean — Tue, 13 Sep 2005 01:10:00 GMT

What is the value of this expression?

If that was too easy, how about this one?

Puzzle Solution: a geometry problem

AdiOltean — Fri, 19 Aug 2005 06:35:00 GMT

The geometry problem from my previous math puzzle has a nice solution. I particularly like it because it is one of these problems that are pretty hard to solve traditionally - unless you perform the right geometric construction - and at that point, the solution becomes trivial.

We will perform the following trick. From the point D we will draw a segment DE (with E on the longer side - AC in our case). E is chosen such that the angle(ABD) = angle(ADE).

At this point, our puzzle solving strategy is this:
a) Derive as much equations as possible from our new construction, and
b) Eliminate from these euqations any segments involving the point "E".

First, we immediately observe that the triangle BAD is similar with the triangle DAE, therefore:

AD/AB = AE/AD = DE/BD (1)

From here we can extract AE without involving any other segments containing the point "E":

AE = AD^2 / BA (2)

Second, because angle(ADE) + angle(EDC) = angle(ADC) = angle(ABD) + angle(BAD) we obtain: angle(BAD) = angle(EDC) = angle(DAE). In conclusion, the triangle ADC is similar with the triangle DEC, so:

DC/AC = EC/DC = DE/AD (3)

From here, we extract EC, again without involving any other segments containing the point "E":

EC = DC^2 / AC (4)

Third, if we divide the other "unused" parts from equalities from (1) and (3) involving DE (but not involving any other segments containing "E") we obtain: (AD/AB) / (DC/AC) = (DE/BD) / (DE/AD). AD simplifies, and we obtain:

AB/AC = DB/DC (5)

So, we have now three inequalities (2), (4) and (5), where the first two one involve the segments AE and EC.

Now, how we can get rid of "E" in AE and EC? We observe that AC = AE + EC, and by substituting AE and EC from the equations (2) and (4) above, we finally obtain something that doesn't contain any "E"s anymore:

AC = AD^2 / AB + DC^2 / AC. (6)

From here, we extract AD^2:

AD^2 = AC * AB - AB/AC * DC^2 = AC * AB - DB/DC * DC^2 = AC * AB - DB/DC * DC^2. (7)

In conclusion, after everyting simplifies nicely, we obtain our initial equality:

AD^2 = AC * AB - DB * DC

P.S. Feeedback summary on the puzzles:
1) MovGP0 posted another possible solution to the geometry problem at http://de.wikipedia.org/wiki/Benutzer:MovGP0/Dreieck but it looks like the proof is apparently incomplete (although I might be wrong).
2) Many readers correctly pointed out that the other sequence puzzle is a classic one, called the Convay sequence (also named the "Look and Say" sequence). As an anecdotic fact, I heard that it was initially done as a scientific study where people with mathematic abilities were tested along with people with literary/linguistic abilities. Interestingly, the persons with linguistic abilities found the solution much quicker than the ones with math abilities.

Puzzle: a little geometry problem, and a sequence question

AdiOltean — Sat, 06 Aug 2005 10:44:00 GMT

This is not really a puzzle, but a real geometry problem. Let's take a random triangle (ABC), and let's assume that the angle bisector from A intersects BC in the point D. Proof that:

AD ^ 2 = AB * AC - BD * CD

Here is the figure, drawn in MSPAINT.EXE as you can see :-)

And now, a real math puzzle. Here is a sequence of sequences of numbers.

     1
    1,1
    2,1
  1,2,1,1
1,1,1,2,2,1
3,1,2,2,1,1
...

What comes next?

Puzzle: When everything goes wrong

AdiOltean — Sat, 02 Jul 2005 01:30:00 GMT

During war, two spies (Jack and Arnold) are being parachuted in a hostile country. But during their landing, their plane gets intercepted by the special forces. Things started to go out of control: they both lose all their equipment, and Ann, the person that is waiting for them on the ground, is killed. They both land far from the original location (and far from each other) in a completely unknown area. Eventually, each of them reaches a pay phone, but when they call Ann's phone number they obviously get no response.

The first thing that they have to do is get in touch with each other. They obviously can't call 911 or any random number, or do anything that will draw attention (like putting announcements in a newspaper), because all special forces are looking for them. In fact there is no TV, radio or newspapers in that area that would allow one of them to get information about another. Of course, they have no cell phones, walkie-talkies or anything that would allow them to communicate.

What would be their strategy to get in touch?

Puzzle: two cubes

AdiOltean — Tue, 28 Jun 2005 03:24:00 GMT

You are given two white cubes. You are asked to draw a digit (from 0..9) on every square of these cubes, such that you will be able to represent evert day in a month using these cubes in certain position. For example, "13" would require that a face on one cube will contain "1" and another face on the other cube will contain "3".

Puzzle: How do you get out of the prison (Part II)

AdiOltean — Sat, 25 Jun 2005 08:09:00 GMT

The previous puzzle was solved correctly in the comments. So I thought to present with another prison-style puzzle:

A warden meets with 23 new prisoners when they arrive. He tells them, "You may meet today and plan a strategy. But after today, you will be in isolated cells and will have no communication with one another.

"In the prison is a switch room, which contains two light switches labeled A and B, each of which can be in either the 'On' or the 'Off' position. I am not telling you their present positions. The switches are not connected to anything.

"After today, from time to time whenever I feel so inclined, I will select one prisoner at random and escort him to the switch room. This prisoner will select one of the two switches and reverse its position. He must move one, but only one of the switches. He can't move both but he can't move none, either. Then he'll be led back to his cell.

"No one else will enter the switch room until I lead the next prisoner there, and he'll be instructed to do the same thing. I'm going to choose prisoners at random. I may choose the same guy three times in a row, or I may jump around and come back.

"But, given enough time, everyone will eventually visit the switch room as many times as everyone else. At any time anyone of you may declare to me, 'We have all visited the switch room.'

"If it is true, then you will all be set free. If it is false, and somebody has not yet visited the switch room, you will be fed to the alligators."