The Logical Pattern behind Piracy

In this article, I will investigate and explain the Logical Pattern behind (in my opinion) one of the best questions in Computer Science: The Piracy Problem.

For all of you who hoped to find an article about downloading movies or software, I have to disappoint you. This is not about that kind of piracy. It's about one of the best algorithmic riddles that I have found so far. It's quite a read, but I hope you think it's worth it!

To start off, I'm going to send you here. This entire article is based upon that riddle.

Finished? Cool, isn't it? Logic and pattern recognition combined with a funny setting. There's a small extension to it on the same site here.

I thought about this riddle for a long time and decided to discover the logical pattern behind this problem. In the 6 pirates, 1 coin case, pirate number 5 dies if he would have to make the proposal, yet pirate number 6 lives, because he can count on 5's vote even if 5 gets no coins (because he would otherwise die). I was wondering, what other pirates would survive if there was only a single coin? Pirate 7, 8 and 9 would die again, since they can never convince resp. 4, 4 and 5 pirates to vote for them. Pirate 10 however, gets to live! Because 7, 8 and 9 would otherwise die, they vote for 10 even if they get nothing! Combined with 10's own vote and the vote of the pirate who gets the coin, 10 is able to secure 5 votes and gets to live another day.

Note that in this case, pirate 5 would not vote for pirate 10, because he knows he will get nothing anyway and if 10 walks the plank, so will 9, 8 and 7. 6 would then come to power and 5 would then vote for 6. He still gets nothing, but at least 4 other pirates have died. Him being a pirate, only his own life and getting gold pleases him more than seeing others die :-)

So, let's re-iterate the priorities that pirates use to vote, in order of importance:

• Priority 1: Stay alive
• Priority 2: Get as many gold coins as possible
• Priority 3: Get as many other pirates killed as possible (given priority 1 and 2 are equally satisfied)
• Priority 4: If a pirate is a senior and it doesn't matter to whom he gives a coin, he will give it to the LOWEST ranked pirate. So, if pirate number 6 can choose to give a coin to either 1 or 4, he will choose 1.

I added number 3 and 4 to make the problem deterministic in all cases.

I then started to make spreadsheets of the number of coins that each pirate would get, when there are c coins available. Below is the spreadsheet of the 1 coin case. The rows represent the situation where there are a certain number of pirates and the columns represent what each pirate would get in those situations. a value of -1 (and a red color) means that the pirate in question dies in that given situation. The green cells represent the pirates who would vote in favour of the proposal. Please click to enlarge.

The 1 coin case

And here are the spreadsheets for 2 and 3 coins:

The 2 coins case

The 3 coins case

A clear pattern emerges! I have defined so-called "life lines": lines on which the most senior pirate is able to survive by counting on the votes of the pirates who would otherwise die. I've marked those rows with a light green color. The patterns that emerge are as follows:

• A life line occurs when the number of pirates is equal to a number in this set: For c number of coins and x > 1: 2^x + 2c. So, for 1 coin, the life lines are 4, 6, 10, 18, 34...
  
  
• Before the first life line: If the most senior is even, all even pirates get a coin, all odd pirates get nothing. The most senior keeps what's left. When the most senior is odd, it's the odd pirates who get a share of the bounty. Note that the "first" life line fits this pattern as well. It's kind of a transitional line.
  
  
• After each life line, the most senior pirate dies and the others get the same as they got on the previous life line, until we get to the next life line.
  
  
• On each life line, the most senior pirate gives the coins to the most junior pirates who would otherwise get nothing. Note that these alternate on each subsequent life line, because otherwise, those juniors have no incentive to vote (because they would get the coins anyway).

Note that these patterns also apply when there are 0 coins!

The 0 coins case

Then, I created an algorithm (in Java). For a certain number of pirates and a certain number of coins, what does a certain pirate get? (Scrolling to the right is possible)

/**
 * Avast, me hearties! This method returns me bounty, the number of dubloons me be gettin' when me be among these scurvy dogs! Yarr!
 *
 * @param numberOfCoins      The total number of dubloons me and me mateys will divide...
 * @param numberOfPirates    The total number of scallywags in this bung hole!
 * @param myIndex            Me index! Big guys above me, sprogs below...
 * @return
 */
public static int whatsMeBounty(int numberOfCoins, int numberOfPirates, int myIndex) {

    int firstLifeLine = 2 + numberOfCoins*2;
    if(numberOfPirates < firstLifeLine) { //We're under the first life line

        if(myIndex == numberOfPirates) { //Me be the most senior
            return numberOfCoins - (int) ((numberOfPirates-1)/2); //Integer division is floored, so me be gettin' what's left
        } else { //Me not be the most senior
            if(numberOfPirates % 2 == 0) { //The most senior is even
                if(myIndex % 2 == 0) { //Me be even
                    return 1;
                } else { //Me be odd
                    return 0;
                }
            } else { //The most senior is odd
                if(myIndex % 2 == 0) { //Me be even
                    return 0;
                } else { //Me be odd
                    return 1;
                }
            }
        }

    } else { //We're over or on the first life line

        double lifeLineIndex = Math.log(numberOfPirates - numberOfCoins*2) / Math.log(2);
        if(lifeLineIndex % 1 == 0) { //We're exactly on a life line

            //If me be more senior than the most senior pirate on the preceding lifeLine (and this isn't the first life line), me be votin' to live, not to get coins
            int precedingLifeLineSenior = (int) Math.pow(2, (lifeLineIndex-1) + numberOfCoins*2);
            if(myIndex > precedingLifeLineSenior && numberOfPirates != firstLifeLine) { //Me be votin' to escape Fiddler's Green!
                return 0;
            } else { //Me only be votin' if me be gettin' a coin!

                if(lifeLineIndex % 2 == 0) { //We're on an even life line, the first 'numberOfCoins' odd pirates get a coin
                    if(myIndex % 2 == 1 && myIndex <= numberOfCoins*2) {
                        return 1;
                    } else {
                        return 0;
                    }
                } else { //We're on an odd life line, the first 'numberOfCoins' even pirates get a coin
                    if(myIndex % 2 == 0 && myIndex <= numberOfCoins*2) {
                        return 1;
                    } else {
                        return 0;
                    }
                }
            }

        } else { //We're NOT on a life line
            if(myIndex == numberOfPirates) { //Me be the most senior
                return -1; //Shiver me timbers! Me be walkin' the plank!
            } else { //Me not be the most senior, let's see what me be gettin' once that scurvy dog has visited Davy Jones's locker!
                return whatsMeBounty(numberOfCoins, numberOfPirates-1, myIndex);
            }
        }
    }
}

And that's that: The Logical Pattern behind Piracy.

Thanks to:

• Yarr for the crash course on Pirate Talk
• WPClipart for the Pirate Image

---

Logic, universally true or not?

Many people, once including me, consider logic to be a universally true concept. This is because it is separated from the physical world and does not make any assumptions about the physical world. Hence, it is universally true, regardless of physical uncertainties such as relativity, the correctness of our observations, the existence of multiple realities and so on. But is this really the case? Lately, I've been having some doubts about this, that I'd like to share with you.

It all began with the realization that logic as we know it leads to many paradoxes. For example, let's apply logic to the concept of knowledge. Most people will agree that it is not possible to be absolutely certain about anything, because of the following reasons:

• First of all, we cannot trust our own observations, since they are linked to the physical world and are therefore possibly incorrect.
  
  
• Second, even if we do realize that something must be true, we can still not trust ourselves. After all, isn't it possible to realize something is true, even though it is not? In fact, it's not even difficult, a bottle of whisky should do the trick.

Unsurprisingly, someone figured this out long before me:

The only true wisdom is in knowing that you know nothing

- Socrates -

One of the best quotes ever, precisely because it is a paradox in itself! After all, how can you know that you know nothing? Logic, in all its greatness, has not just deprived us of all knowledge, but even the only thing we do know is a paradox in itself...

Let's continue with an xkcd comic, that most of you will probably have seen before (I love xkcd btw): xkcd.com/435. The author actually forgot the last link in the chain: logic. Math is applied logic. Like logic, it's disconnected from the physical world, but math is not the beginning, that is logic.

If you look at math, however, you will notice that it is far from perfect. The number i, for example, of which the square is -1, is nothing but a dirty hack. Yet it opens many possibilities and constructs in math that would otherwise be impossible. Apparently, math as we know it needs hacks to be able to express everything that can be expressed.

If we go further up the chain, to physics, we can see that it too, contains many inconsistencies. The speed of light, for example. Nothing can surpass it, yet scientists have found neutrinos that might have. And let's not even get started about time travel paradoxes.

And yet, despite its many flaws, logic has given us all of these scientific fields, which have given us technology, progress, wealth and, most importantly, the ability to think in a structured way and have discussions with one another. Take away the laws of logic and everything would collapse. We wouldn't even be able to talk to one another anymore. So, to summarize:

• Logic is the beginning of all scientific fields, the first link in the chain, the cradle of science
• Logic, and its derived fields, are far from perfect and contain paradoxes, inconsistencies and hacks
• Without logic, we would be nowhere

Then it struck me. Combining these 3 observations, it occurred to me that logic might not be something universally true. Instead, it might just be a formal model of the human thought process. Logic started to develop when humans started to think, hence its position as first link in the chain. And since humans are imperfect, so is logic. Finally, it makes perfect sense that we would be nowhere without logic, because logic captures the very essence of human thinking.

A couple of years back, I met this couple in a bar. The subject of discussion at the bar happened to be politics, an interesting subject, that perfectly lends itself for some logical reasoning. There were some leftish people there, some right wing people, and we had a good discussion about the various approaches to politics. But to my astonishment, when the couple joined in, the arguments and theories that they told us, made no sense at all. Not to me and not to any other person there, left or right. They were defending silly theories, such as "The people should just all sit together and talk about things and when they agree, they should take action." Questions from our side such as "What if they don't agree?" or "How do you get 15 million people to discuss something?" weren't answered, or were answered by statements that made no sense. At first, I thought that they were either very idealistic or very drunk, it was a bar, after all. But this wasn't the case. They weren't drunk and despite the fact that none of us understood them (agreeing with them wasn't even an option, since we didn't even comprehend their line of thought), they perfectly understood one another! It was as if their minds were wired differently, they had a different thought process, that did not match with the laws of logic.

Over the years, I've met more people, whose thoughts sometimes defy basic logic (and I'm not talking about stupid people, who I also meet). Yet they seem to be doing well in society and don't seem to be affected by having an illogical brain.

A final example is quantum mechanics. Quantum mechanics leads to paradoxes, such as electrons and photons being both particle and wave. When observed, they behave like a particle, but when not observed, they behave like a wave. Demonstrated in the Double-slit experiment, this is completely inexplicable by our physics. And as the famous physicist Richard Feynmann demonstrated, in order to perform mathematical calculations involving quantum mechanics, you can't escape the use of complex numbers. This is a perfect example of each link in the chain breaking down: logically, quantum mechanics leads to paradoxes, mathematically, it leads to the use of hacks (complex numbers) and physically, it just cannot be explained.

This is why I'm not very hopeful of us humans ever understanding quantum mechanics. Perhaps our brains just aren't good enough. It also made me think about the following: What if there are aliens, with better brains? That would lead to better logic, better math, better physics, etc. Maybe their math does not have hacks. Maybe their physics can perfectly explain time travel and light speed, without paradoxes. It would certainly be cool, but let's just hope that they are friendly whenever they find us, because I doubt we will stand a chance...

If this theory is true, it leads to another interesting observation: If logic really is a formal model of the human thought process, then it's really applied psychology!

---