Archive for the 'Puzzles' Category

Crossword puzzles

December 3, 2010

« The redundancy of a language is related to the existence of crossword puzzles. If the redundancy is zero any sequence of letters is a reasonable text in the language and any two-dimensional array of letters forms a crossword puzzle. If the redundancy is too high the language imposes too many constraints for large crossword puzzles to be possible. A more detailed analysis shows that if we assume the constraints imposed by the language are of a rather chaotic and random nature, large crossword puzzles are just possible when the redundancy is 50%. If the redundancy is 33%, three-dimensional crossword puzzles should be possible, etc. » ~ “A mathematical theory of communication”, C.E. Shannon.


Berry paradox

December 2, 2010

« [Natural] numbers can of course be interesting in a variety of ways. The number 30 was interesting to George Moore when he wrote his famous tribute to “the woman of 30”, the age at which he believed a married woman was most fascinating. To a number of theorists 30 is more likely to be exciting because it is the largest integer such that all smallest integers with which it has no common divisor are prime numbers… The question arises: are there any uninteresting numbers? We can prove that there are none by the following simple steps. If there are dull numbers, we can then divide all numbers into two sets — interesting and dull. In the set of dull numbers there will be only one number that is smallest. Since it is the smallest uninteresting number it becomes, ipso facto, an interesting number. » ~ “A collection of tantalizing fallacies of mathematics”, M. Gardner, Scientific American 1958.

Berry paradox. Let S be the set of all positive integers that cannot be described with less than 11 words. By the well-ordering principle, S must have a smallest element s. But s can be defined by the string “The smallest positive integer not definable in under 11 words”, which has less than 11 words, a contradiction.

November 21, 2010

Compressing before encrypting or encrypting before compressing?

November 20, 2010

Say you have one string of alphabetic characters, and say you have another, guaranteed smaller string of alphabetic characters. Algorithmically speaking, what’s the fastest way to find out if all the characters in the smaller string are in the larger string?

What if – given that we have a limited range of possible characters – I assigned each character of the alphabet to a prime number starting with 2 and going up from there. So A would be 2, and B would be 3, and C would be 5, etc. And then I went through the first string and ‘multiplied’ each character’s prime number together. You’d end up with some big number right? And then – what if I iterated through the 2nd string and ‘divided’ by every character in there. If any division gave a remainder – you knew you didn’t have a match. If there was no remainders through the whole process, you knew you had a subset.