2014-12-27

Two-In-One Encryption

Bengt is working on a little nuclear thing in his basement, and it's making him a bit paranoid. He's sure that shady government agents and whatnot are spying on him. For this reason, he needs a secure way to send messages to his "contacts", as he says. Now, there are various useful methods for encryption, so that should be doable, but Bengt is afraid the "agents" will capture him and force him to give them the key. So, what he needs is a way to encrypt two messages to the same cipher text - one real, and one innocuous, so that if he is questioned, he can give them the second key, and they will find the innocuous message.

We can assume that Bengt and his contact - let's call her Alice, shall we - are able to meet beforehand and exchange keys, if need be. After that, they need to be able to send several messages only using channels where the "enemy" can read. All the data has to be possible to interpret as an innocuous message.
  1. What methods can you think of for doing this?
  2.  What if they can't meet beforehand, and every message sent has to have this double-encryption quality?

2014-09-30

Maximum Enjoyment of the Cinema

Bengt has gone to see a film at the small local cinema. This particular cinema doesn't have seat reservations, so you go inside and pick a seat that's free. Bengt isn't a very sociable person, so he doesn't want to sit next to anyone. If the row is empty, he sits on one end, and if anyone sits in the row already, he sits as far from them as possible. If he ends up sitting next to someone, because there are no empty seats that aren't next to anyone, he will be grumpy and not enjoy the film.
  1. Imagine everyone thinks like Bengt. What numbers of seats per row would be the most suitable? We want to avoid people being grumpy, but we also want the density of people to be as high as possible, so as not to waste space. Ideally, thus, we want to make it so that for some number of guests, every second seat will be occupied. This is true for certain numbers of seats - three, for example, but not four. Which are these numbers?
  2. What if the seats would be in a circle, like... some sort of circus, or something?
  3. If you're up for it, try to extend the problem to two dimensions. Or more, why not.

2014-09-21

The Ultimate Board Game

Bengt's friends are playing board games. Bengt, however, is not. He got distracted, as he often does, by trying to improve on what he perceives as flaws in the games. Now he's trying to create a new, better game. As part of that, he needs to design the ultimate board. The board in ths case can be though of as a graph - that is, there are a finite number of "squares", each of which is connected to a finite number of other squares. Connections are symmetric, so if you can go from square P to square Q, you can also go from Q to P. A "region" of the board can be defined as a subset of connected squares, and all the connections between them (a connected induced subgraph, for those into graph theory).

Bengt figures that all regions of at least size k should be different. Otherwise the game gets... repetitive, or something. Given that constraint, he wants to make the board as large as possible.
  1. If we know that all regions of size k are unique, does it follow that all larger regions are also unique? Prove / disprove.
  2. How many possible size k regions (or boards) are there? Solve for, I don't know, a bunch of different k I guess, maybe find an upper bound of the sequence, or better yet, find the exact function.
  3. The real question at hand - how large a board can you make, given that all regions of size k have to be unique? Some k, upper bound, exact function?
  4. Boards defined like this can get pretty messy to draw, so we can add an extra rule, that the connections are not allowed to cross - a planar graph, for the graph-theoretically inclined. Again, as in b...
  5. ...and as in c.

2014-09-14

File Numbering

In some ways, Bengt is an old-fashioned fellow, and he has thus far kept all his "information", as he says, in little notebooks. Let's not even ask what that information is about. The notebooks are very pretty, but now he has started moving things to the computer. That means he has an ever-growing list of files, quite a few of them. Being the rational type, he gives each file a number as filename. The problem is, the computer lists the files alphabetically, not numerically. So 11 comes before 2, etc. Very annoying! One option is of course to use preceding zeros, something like "001", "002", etc. We could easily calculate how many zeros Bengt would need to guarantee the system working for the rest of his life, but we're not going to bother, because we know Bengt would never settle for such a compromise. He wants a system that lasts forever. We could solve that with something as simple as unary numbers - that is, "1", "11", "111"... But that would mean very quickly getting impractically long filenames, so we can't do that.

To summarise, what we need is a method that uses a finite number of symbols, to form an infinite non-repeating list of strings, where the strings are in alphabetical order. But we also need the length of the strings to be logarithmic, just like for ordinary numbers. How can that be done?