20150302, 19:03  #1 
"Mike"
Aug 2002
2^{2}×3^{2}×223 Posts 
March 2015

20150303, 01:25  #2 
May 2013
East. Always East.
11×157 Posts 
I have no idea what that question even means.

20150306, 00:42  #3 
Jan 2005
Caught in a sieve
5·79 Posts 
This is a tough one. Suppose punched cards are expensive, and you want to be able to reuse them once before throwing them away. You want to be able to use a punched card to store 26 characters (AZ), then punch some more holes in it (you can't remove holes) and completely replace what was there before, with any of those 26 characters you want. Storing AZ once takes 5 bits per letter. How many bits per letter do you need to be able to overwrite each letter with any one other letter? (One would assume not more than 10, and probably less.) What kind of encoding do you use?
In CS terms, holes are "1"s, while nonholes are "0"s, so the goal is to have an encoding such that, for each encoded value, you can OR it with some number to produce every other encoded value. The last bit of the question is whether you can write an explanation for your scheme, which uses N bits, in 2^N letters or less. Hence the "Bonus '*' for those who can fit an intelligible sentence into a correct answer." I see an encoding that would work for 9 bits. If the 4 high bits are not set, take the low 5 bits. Skip over characters 15 and 16, so if the high bit is set subtract 2 to get the value you wanted. If any of the 4 high bits are set, take the high 5 bits instead and reverse them. If all 4 low bits are 1, invert the 5 high bits. I suspect 8 bits is possible but I haven't found a way yet. 
20150306, 09:22  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10010010101011_{2} Posts 
One could consider for starters a toy example: A toy alphabet is {A, B, C}, and 2 bits are needed for onetime writing, but how many for the doublewriting?
X=3 bits; e.g. encode A=1, B=2, C=4 for writing once, and A[SUB]2[/SUB]=BC=6, B[SUB]2[/SUB]=AC=5, C[SUB]2[/SUB]=AB=3 for rewriting => 3 bits. So the answer would be _ABCCBA*, where _ is space, and * is usused (or any letter can be put there). I suspect that the fullsize answer is 8 bits, but the satisfactory encoding string is elusive, so far. 
20150307, 02:43  #5 
Romulan Interpreter
Jun 2011
Thailand
2^{2}×2,341 Posts 
A codification with 8 is quite easy and straight away. For example: you encode the AZ in the usual way, with numbers from 1 to 26, except O (01111) and W (10111), see below, which will get 27 and 28. To repunch, you consider the most significant 2 bits (holes) and another 3 bits (totally 8). For the two common bits, you can have them either matching your desired holes, or being unpunched and then you can punch them, or they are 01, 10, 11 and they don't match your desired new holes, in this case you can use repunch first 3 LSB bits (you will only need 2 in fact) to reencode (change the meaning) of common bits. A conflict will appear when you want to repunch something into A, B and C, as you don't have holes in the last 3 MSB, so you don't know if the letter is still the original one, or it was repunched into A, B, or C. In this case, A[sub]2[/sub], B[sub]2[/sub], and C[sub]2[/sub], will have to have codes into (decimal) 27, 28, 29. Another conflict will appear to transform O (which is 01111), and W (which is 10111, so the 3 LSB are already punched) into something ending with 00 or 10 (respective 01), and you will need a different encoding for O and W. This method seems to be a bit (pun intended) inefficient. I suspect a codification with 7 exists, which is, to copy you, "elusive" for now...
Last fiddled with by LaurV on 20150307 at 03:15 
20150307, 04:30  #6 
Romulan Interpreter
Jun 2011
Thailand
2^{2}×2,341 Posts 
Well, after the morning coffee and putting it on paper (the first time I was trying to deal with it in my head, that is why I missed G, beside of O and W). There is a solution with 7, and is based exactly on Batalov's solution, with can be easily generalized. It uses codes of one and two holes, which are 7+comb(7,2)=28, for the first punch, and their complements, i.e. 5 and 6 holes,, for the second punch. The trick is to deal with the few exceptions (conflicts) that appear. Still working on it.
Last fiddled with by LaurV on 20150307 at 04:32 Reason: spoiler, not strike, sorry.... 
20150309, 04:08  #7 
Romulan Interpreter
Jun 2011
Thailand
2^{2}×2,341 Posts 
Now you are all guilty of putting it into my head. Have anyone find a solution with 7 bits? (screw the spoilers, I never liked the black, it would be better be all white or so... and I used them only because other people used them, but now, as I don't show any solution, and actually I don't have a solution , I don't see the utility of the spoiler).
We went out during the weekend, but last evening after returning and doing some chores around the house, before going to bed, I spent about 34 hours with paper and pencil, and even used Excel and Graphviz (to make a digraph of the 127 states, which is quite fast and only took me five minutes). I always run short of 23 letters, no matter how I combine them. This is, I can transform everything in everything, except twothree letters which can't be reached from other twothree letters. But in all cases I have 67 states left (which I can't use). So, in theory, the problem is still possible to be solved with 7 bits, as long as I couldn't prove it is not. I went to bed thinking to it, but it didn't happen like a hundred years ago when I was younger and used to go to sleep with a problem and wake up in the morning with a solution (don't think to stupid things!) Transforming my graph in an 8bit solution is trivial, I only need to add few states with 8 bits, but I "feel" that the solution is with 7, and not with 8. Now I am quite busy at job, but tonight I will begin to put it into a program, and let the computer deal with (part of the) permutations for few days. It is staying on my brain and I can't get rid of it! Your fault! Last fiddled with by LaurV on 20150309 at 04:10 
20150309, 04:53  #8 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3^{2}·7·149 Posts 
I have the 8er solution, which I also rhymed to the "the quick brown fox jumps..." phrase.
But then, I didn't submit it yet. Because I also think that maybe the 7er is possible after all. 
20150309, 05:09  #9 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
1011111100001_{2} Posts 
What about the state of nothing punched? There was no requirement stated to encode a space or anything outside of AZ.

20150309, 14:55  #10  
Jan 2005
Caught in a sieve
110001011_{2} Posts 
Quote:


20150310, 00:18  #11 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3^{2}·7·149 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
March 2018  Xyzzy  Puzzles  2  20180408 13:45 
March 2017  R. Gerbicz  Puzzles  1  20170403 10:57 
March 2016  Xyzzy  Puzzles  21  20160609 20:26 
March Madness 2006  Prime95  Lounge  20  20060321 04:35 
gmp 4.2 due in March  Mystwalker  GMPECM  4  20060201 12:00 