mersenneforum.org March 2015
 Register FAQ Search Today's Posts Mark Forums Read

 2015-03-02, 19:03 #1 Xyzzy     "Mike" Aug 2002 22×32×223 Posts March 2015
 2015-03-03, 01:25 #2 TheMawn     May 2013 East. Always East. 11×157 Posts I have no idea what that question even means.
 2015-03-06, 00:42 #3 Ken_g6     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 re-use them once before throwing them away. You want to be able to use a punched card to store 26 characters (A-Z), 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 A-Z 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 non-holes 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.
 2015-03-06, 09:22 #4 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100100101010112 Posts One could consider for starters a toy example: A toy alphabet is {A, B, C}, and 2 bits are needed for one-time writing, but how many for the double-writing? X=3 bits; e.g. encode A=1, B=2, C=4 for writing once, and A[SUB]2[/SUB]=B|C=6, B[SUB]2[/SUB]=A|C=5, C[SUB]2[/SUB]=A|B=3 for re-writing => 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 full-size answer is 8 bits, but the satisfactory encoding string is elusive, so far.
 2015-03-07, 02:43 #5 LaurV Romulan Interpreter     Jun 2011 Thailand 22×2,341 Posts A codification with 8 is quite easy and straight away. For example: you encode the A-Z 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 re-punch, 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 re-punch first 3 LSB bits (you will only need 2 in fact) to re-encode (change the meaning) of common bits. A conflict will appear when you want to re-punch 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 2015-03-07 at 03:15
 2015-03-07, 04:30 #6 LaurV Romulan Interpreter     Jun 2011 Thailand 22×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 2015-03-07 at 04:32 Reason: spoiler, not strike, sorry....
 2015-03-09, 04:08 #7 LaurV Romulan Interpreter     Jun 2011 Thailand 22×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 3-4 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 2-3 letters, no matter how I combine them. This is, I can transform everything in everything, except two-three letters which can't be reached from other two-three letters. But in all cases I have 6-7 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 8-bit 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 2015-03-09 at 04:10
 2015-03-09, 04:53 #8 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 32·7·149 Posts I have the 8-er 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 7-er is possible after all.
 2015-03-09, 05:09 #9 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 10111111000012 Posts What about the state of nothing punched? There was no requirement stated to encode a space or anything outside of A-Z.
2015-03-09, 14:55   #10
Ken_g6

Jan 2005
Caught in a sieve

1100010112 Posts

Quote:
 Originally Posted by LaurV 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.
I was working on a similar approach to an 8-bit solution. Take up-to-2 of 7 bits for the initial encoding, requiring that mirrored solutions are excluded. (This appears to be short one character already now that I look at it!) Then add another bit to specify that a complement encoding is mirrored, so that a bit opposite an already used bit can be left unpunched. But the mirror of the central bit is still the central bit.

2015-03-10, 00:18   #11
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

32·7·149 Posts

Quote:
 Originally Posted by retina What about the state of nothing punched? There was no requirement stated to encode a space or anything outside of A-Z.
I am pretty sure that this doesn't contradict the problem, especially as restated on 3/04.

 Similar Threads Thread Thread Starter Forum Replies Last Post Xyzzy Puzzles 2 2018-04-08 13:45 R. Gerbicz Puzzles 1 2017-04-03 10:57 Xyzzy Puzzles 21 2016-06-09 20:26 Prime95 Lounge 20 2006-03-21 04:35 Mystwalker GMP-ECM 4 2006-02-01 12:00

All times are UTC. The time now is 16:03.

Sun Apr 11 16:03:04 UTC 2021 up 3 days, 10:43, 1 user, load averages: 1.38, 1.68, 1.81