Which is worse: to take the time to say goodbye to a person, to a place, or to an activity, or to notice much later than, somehow, you stopped at some point to meet that person, to visit that place, or to do that thing?

I often notice things which I used to do and don't do anymore, and realize that there must have been one time which was the last one, and which probably didn't feel like it had any specific importance. Now, whenever I do something I haven't done for a long time and used to do regularly, I find myself wondering, "is this one of those last times which could have gone unnoticed?"

A lot of effort has been put in the design of interfaces which are simple to use, and people who try to sell computer products or services to you will usually present that as one of their main selling points. However, when you think of it, there really aren't that many people who try to create interfaces which are efficient, and efficiency doesn't sell at all.

This seems quite surprising. Simplicity and efficiency are usually two contradictory aims. For instance, it is usually faster to hit a key than to click a button (hence keyboard shortcuts), but you have to learn which key is mapped to which command, whereas buttons have labels which allow you to find out which one to click; displaying help messages take up screen space which is wasted for those users who already know how things work.

I am not saying that efficiency should always be favoured over simplicity. For tasks that you don't do very often, it wouldn't be worthwhile to spend the time required to learn an efficient interface. However, for tasks which you often do and which you will keep doing for quite some time (in my case: writing text, answering email, coding, etc.), learning how to use efficient tools is a profitable investment.

It is tempting to say that it makes more sense commercially to favour simplicity over efficiency because your product or service will have more casual users than hardcore users. This may be true, but it's not the whole story. Expert users are usually willing to pay more, and tend to influence other people, which makes it profitable to try to seduce them. Furthermore, outside of the computing world, things aren't always done that way. Piano keys don't carry labels, even though this could be useful for beginners. Bicycles aren't sold with the little stabilizer wheels you sometimes see on bikes for young children. Yet, webmails, social networking websites, operating systems and mobile phones usually have an interface which is simple but crippled, and that doesn't seem to bother in the slightest the numerous people who use them several hours per week...

I think that in fact, while the number of people who should theoretically invest time to learn efficient solutions is large enough, the number of people who are conscious of that need is much smaller. That's probably because society hasn't realized yet the quantity of time that people tend to spend on their computers, as compared to the time where computers weren't ubiquitous and where very few people used them. It's probably also because people tend to act irrationally and are unwilling to spend some time learning and recoup their investment later. Or perhaps because they are unwilling to acknowledge the time they spend on their computer, because they think it was somehow wasted.

Did you ever notice that a sentence such as "John seeks a unicorn." can have two different meanings:

• John is looking for a specific unicorn which he has in mind.
• John is looking for any unicorn.

If this seems obscure, consider the following example, adapted straight from the Wikipedia article:

Jane wants to marry the richest man in California.

This can mean two different things:

• Jane already knows someone who happens to be the richest man in California, and would like to marry him; we just happen to refer to him as the richest man in California, but that's not its defining quality as far as Jane is concerned.
• Jane doesn't know who the richest man in California is, but would like to marry that man.

This amusing ambiguity is called the "de re and de dicto" distinction (in the two examples above, the first interpretation is "de re", the second is "de dicto").

Another example of this distinction is Diogenes's "ἄνθρωπον ζητῶ" ("I'm looking for a man"). It is understood as meaning that he would like to find any true man, but, taken out of context, it could also mean that he has a specific man in mind and is looking for him.

For French speakers, it is interesting to compare "Je cherche un homme qui a les yeux bleus." (indicative) to "Je cherche un homme qui ait les yeux bleus." (subjunctive). The first sentence is de re (I'm looking for someone specific who happens to have blue eyes) and the second is de dicto (I'm looking for anybody with blue eyes).

The problem presented here (of generating a random cyclic permutation) is also useful for Secret Santa. A simpler solution than the one presented here, with similar requirements, is presented in Section 5.1 of the paper Cryptographic Protocols with Everyday Objects by Heather, Schneider, and Teague, where it is called the "Father Cryptmas Protocol". Thanks to Ryan Lahfa for the pointer.

The killer game is played as follows: each player is given a "victim" (another player) which he has to "kill" in some way (which depends on the variant played). Whenever a player manages to kill his victim, he gets the victim's victim as his new victim, and the killed player is eliminated. The aim of the game is to kill without being killed; the winner is the last man standing.

The usual way to play the game is to ask some trusted third party to generate the list of killer-victim relations and to give each player a piece of paper indicating his victim. Of course, it would be quite natural to use a computer to generate the game instead, in order to avoid the need to ask someone to create the game and not be able to play. What I will present in this post is an even nicer system: a way for players to organize together a killer game by themselves, in such a way as to prevent anyone from getting any information about the generated game. No computer needed: you only need paper, a pen, and a deck of n cards (where you number the players from 1 to n).

As for security, the main requirement isn't to prevent deliberate trickery but rather accidental remembering of information. In other words, we want to organize a game between people who are honest but who wouldn't like to remember things about the game inadvertently (ie. we don't want to depend on their having a bad memory). Hence, we assume that players don't really try to cheat or form coalitions to cheat together, but that they just want to generate the game without having to try to not remember what they have done.

The problem can be separated in two steps:

1. First, generate the permutation mapping each player to its victim. (It is a permutation since each player is the victim of exactly one player.) We can't accept any permutation: the permutation needs to have only one orbit. (Otherwise, the game will have multiple winners.)
2. Second, generate the papers giving to each player its victim. This isn't straightforward at all, because we can't just ask one player to write them down: the papers need to be written in a way which prevent anybody from knowing their contents.

The first step, in fact, is easy to solve. If you take a deck of n cards and shuffle it collaboratively (ie. every player gets a chance to shuffle the deck, to prevent cheating), the permutation mapping the i-th card of the deck to the i+1-th one (modulo n) is a permutation with only one orbit; moreover, if the order of cards is chosen uniformly at random, the resulting permutation is also chosen uniformly at random among all such permutations. Thus, the players have a way to create together securely a suitable permutation.

What remains is to generate pieces of paper mapping players to their victims. We will assume that, for each player, we have a blank piece of paper on which we will apply the following operations:

1. Write the number of the victim on the paper.
2. Fold the paper in such a way that the victim number cannot be read.
3. Write on the outside of the paper the number of the player which should kill the victim.
4. Fold the paper to make both numbers unreadable, and put the paper in an urn.

Now, the idea is that each player but the first one will apply the following procedure:

• Input: The deck of cards and a piece of paper folded once.
• Output: The deck of cards without the top card and another piece of paper folded once.
• Procedure:
  1. Draw the first card of the deck, secretly, memorize its value, and discard the card (in a discard pile which will not be examined).
  2. Write the value on the folded piece of paper, fold it a second time and put it in the bin.
  3. Take a new piece of paper, write the value on it, and fold it once.

What is supposed to happen is that the players pass the deck of cards (with a piece of paper) to each other, producing papers as we go. The order of players is determined at random collaboratively (ie. the players draw a random number together, for example by committing to a value and XORing the values). The question of the first and last card still needs to be settled, and it is the role of the first player. More precisely, the first player starts off the process and ends it in the following way:

• At the beginning, take the deck of cards, and follow the algorithm above without the last step to prepare the first piece of paper (folded once).
• At the end, take the empty deck of cards and the last piece of paper (folded once), and apply the last step with the value memorized for the initial step.

Of course, once we have run all that, all that we have to do is to empty the urn, unfold each paper once, and give each paper to the player indicated on it. Players then open their paper and find their target.

What remains is that we want to ensure that, by following this scheme, players don't get information about the game. But the beautiful thing is that players only see one player value, so they really can't have any information about any player's relation to other players. In fact, to put it in a nutshell, the idea is that the papers represent couples of a value and its image by the permutation, and that we generate them by asking each player to write down a given number twice: once as value, and once as image.

As for actually playing the game, what's really funny is that you don't have any information about the game's progress, because nobody knows what the players are up to. Players kill themselves in a decentralized way, and, at some point, a player should discover that the person he killed was his own killer, which means that he won the game.

This scheme was successfully implemented two years ago to play a game in my Math spé class. Of course, the protocol wasn't respected to the letter (we didn't have enough people to generate the game, so players got multiple turns writing numbers down, which we tried to space as much as possible), and we had to work our way around a few practical difficulties, but everything went smoothly. The generated permutation was correct (an entirely unexpected thing given the fact that the deck used was a standard deck with a conversion rule to match value and suit to player number and then to player name, with a lot of opportunities for mistakes), and the game was played up to its conclusion (which was once again very fortunate, given the fact that there wasn't anyone able to correct errors or to make things move should the game get stuck somewhere).

Of course, the best thing was that I was able to play the game even though I was the one who had made the whole scheme up.

I find it quite amazing that people, when they see the profile page of "John Doe" on Facebook, assume that the page is indeed controlled by John Doe and allows them to contact John Doe. (No, in fact, they wouldn't do that for someone called "John Doe", but let's assume that the name isn't "John Doe" but something sufficiently unique to ensure that there aren't multiple people with that name.)

If you think about it, this is absurd; what they are seeing is a page managed by Facebook, which pretends that they gave the control of the page to someone who claimed to be John Doe. Even if we assume that Facebook isn't interfering, at no point whatsoever did anybody check that the guy is indeed John Doe.

In practice, things work out quite well because there aren't that many people who are willing to take the time to impersonate someone else on Facebook. Nevertheless, I know that some people had to complain to Facebook because they had some sort of enemy who created an (insulting) Facebook profile with their name. This shows that there is a problem; theoretically, when confronted with such a page, nobody should assume that the page has anything to do with the person whose name appears on the page...

(Of course, this problem isn't restricted to Facebook, but extends to most of what you find online. Not everything, though (notable exceptions are the OpenPGP web of trust, and the HTTPS certificate authority system which is itself quite flawed).)