Ponder This Challenge - March 2015 - Punched (twice) tape

Ponder This Challenge:

Punched tapes are roll of paper that can be written by punching holes.
All 26 letters of the English alphabet (A-Z) can be encoded using 5-bit wide tape.

How many bits do we need to be able to write twice?

Supply your answer as a 2**X long list of letters, such that using your encoding, one can punch some holes on a blank tape and encode any letter; and then add some more holes (one can not undo a punch) to write any other letter.

Bonus '*' for those who can fit an intelligible sentence into a correct answer.

Update (03/04): We have a translation function f from {0,1}^X to {A,B,...,Z} such that for every letter alpha (in A-Z) we can find X bits value x such that f(x)=alpha and for every other letter beta there exists another X bits value y_beta such that f(y_beta)=beta and y_beta>=x bitwise. I.e., every 1 (hole) in x remains a 1 in y_beta, while a 0 in x may be changed to 1 in y_beta ("adding hole"). Note that once you punch beta you are no longer required to remember alpha so y_beta encodes only beta.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

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

Solution

• Click here to view the solution

  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

Solvers

• Aviv Nisgav (03/03/2015 05:03 AM EDT)
• *Franciraldo Cavalcante (03/04/2015 03:01 AM EDT)
• Kang Jin Cho (03/05/2015 05:42 AM EDT)
• *James Dow Allen (03/06/2015 04:05 PM EDT)
• Graham Hemsley (03/08/2015 08:16 AM EDT)
• *Chuck Carroll (03/10/2015 08:43 AM EDT)
• *Andreas Stiller (03/10/2015 11:39 AM EDT)
• Radu-Alexandru Todor (03/10/2015 02:31 PM EDT)
• Emilio Del Tessandoro (03/12/2015 08:42 AM EDT)
• *Armin Krauss (03/12/2015 07:04 PM EDT)
• Alex Fleischer (03/14/2015 05:13 PM EDT)
• *Motty Porat (03/14/2015 06:44 PM EDT)
• Vladimir Sedach (03/15/2015 10:55 AM EDT)
• *David Dodson & Don Dodson (03/16/2015 05:01 PM EDT)
• *Serge Batalov (03/19/2015 03:11 AM EDT)
• Gyorgy Gyomai (03/22/2015 03:32 PM EDT)
• Antoine Comeau (03/23/2015 01:10 PM EDT)
• Mark Pervovskiy ( (03/24/2015 10:09 AM EDT))
• *Daniel Bitin (03/25/2015 12:21 PM EDT)
• Uoti Urpala (03/27/2015 11:40 PM EDT)
• Shirish Chinchalkar (03/28/2015 10:01 PM EDT)
• David Greer (03/30/2015 03:12 PM EDT)
• Gregory Giecold (03/30/2015 03:52 PM EDT)
• *Mark Pervovskiy (03/30/2015 06:21 PM EDT)
• *Maximilian Hasler (03/31/2015 10:44 AM EDT)
• Liubing Yu (03/31/2015 08:24 PM EDT)
• *Alex Wagner (03/31/2015 09:44 PM EDT)