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: http://www.google.com/patents/EP0108053A1).
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":
linuxcppjvmlsetoywglSEVENBITSCANDOTHEWORKxycnsxfrpparbydlhwjvimqwzaifjsmbcspndjkhmqbqvoxiqdrlyhwqenyehildmtvrubggnwsjtckxoefpauz
Another (Chuck Carroll) has more than one sentence:
bfurGOjsdkPONDERTHISqlnulfutpgwasaceekcbywzdqzgimhjltcypznhqbjfxvxwyzqxfxlnjgpqhxxpkjimzxdicmeobxfoWOMANPAYScultiaughwdrroemsykv
Update 28/6/2016: Bert Dobbelaere solved for coding 28 letters in 7 bits - solving a 34 years old open problem:
1WHTRLZREOPVQATMGBFIDOANJRAX2KYCIVCAUILY2URLDBXFAJTMR1EPIQNZWGVSKMKBYSGDXIQ2RPIWNARGIVJQSFB1ZELUSRIOCZQKVCGEAN1JCLUWFXB2PYKDMTOH
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: ponder@il.ibm.com