IBM Research | Ponder This | March 2015 solutions
Skip to main content

March 2015

<<February March April>>

We recently saw this problem in Jack Kennedy's blog, but it actually originated more than 30 years ago (see Rivest/Shamir, 1982:

The answer is 7 bits. Using 26 of the 29 combinations with a Hamming weight of no more than 2, we can write the first letter and then solve the matching problem to assign letters to the other combinations, in such a way that we can write any letter beta after any letter alpha.

One such solution (by Motty Porat) contains the sentence "Seven bits can do the work":


Another (Chuck Carroll) has more than one sentence:


Update 28/6/2016: Bert Dobbelaere solved for coding 28 letters in 7 bits - solving a 34 years old open problem:


Update 19/4/2017: See Bert's paper about it.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: