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

# Ponder This

## 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