The Great Sultan of the Indies

The Great Sultan of the Indies was sent by one of his viziers 99 bags of gold, each containing exactly 50 coins. Hidden somewhere in those 99 bags is a hollowed coin (indistinguishable to the naked eye from the others) containing a secret message destined to His Most Excellent Majesty. Using a simple two-pan balance, in how many weighing can you find the bag containing the lighter coin? With how many further weighing can you find the coin within the bag?

The solution of the problem is not that complicated, but depends entirely on the assumptions you make on the balance. If one supposes that the balance is large enough to pile the 99 bags in either one of its pan, and that is locked while you’re loading it, giving its reading only once you’re done loading it, the solution that comes to mind is

Converting PDFs to Hard B+W

Nothing too this week: how to convert a Djvu or PDF to hard black and white PDF—not shades of gray. Why would you want to do that anyway? Well, you may, like me, have a printer that has no concept of color calibration and has dreadful half-toning algorithms, resulting in unreadable text and no contrast when you print a Djvu or a PDF of a scanned book.

Walk Count like an Egyptian (Part I)

The strangest aspect of the Ancient Egyptian’s limited mathematics is how they wrote fractions. For example, they could not write outright, they wrote

,

and this method of writing fractions lead to absurdly complicated solutions to trivial problems—at least, trivial when you can write a vulgar fraction such as . But how much more complicated is it to write rather than ?

Fractional Bits (Part II)

In a previous post, we started discussing the subject of encoding values using fractional bits. This is quite counter-intuitive as we usually think that encoding asks for whole bits, furthermore that we think of bits as being essentially atomic—unsplittable.

However, bits can be fractioned, helping us devising efficient encodings, something not unlike a primitive form of arithmetic coding, for a variety of data. Let’s consider a simple case that illustrates the principle: encoding the date.