mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2015-03-02, 19:03   #1
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

25×251 Posts
Default March 2015

http://domino.research.ibm.com/Comm/...March2015.html
Xyzzy is offline   Reply With Quote
Old 2015-03-03, 01:25   #2
TheMawn
 
TheMawn's Avatar
 
May 2013
East. Always East.

6BF16 Posts
Default

I have no idea what that question even means.
TheMawn is offline   Reply With Quote
Old 2015-03-06, 00:42   #3
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

5×79 Posts
Default

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.
Ken_g6 is offline   Reply With Quote
Old 2015-03-06, 09:22   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

41×229 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2015-03-07, 02:43   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

222318 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2015-03-07, 04:30   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

33×347 Posts
Default

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....
LaurV is offline   Reply With Quote
Old 2015-03-09, 04:08   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

249916 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2015-03-09, 04:53   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

222558 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2015-03-09, 05:09   #9
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

611510 Posts
Default

What about the state of nothing punched? There was no requirement stated to encode a space or anything outside of A-Z.
retina is online now   Reply With Quote
Old 2015-03-09, 14:55   #10
Ken_g6
 
Ken_g6's Avatar
 
Jan 2005
Caught in a sieve

6138 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
Ken_g6 is offline   Reply With Quote
Old 2015-03-10, 00:18   #11
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

41×229 Posts
Default

Quote:
Originally Posted by retina View Post
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.
Batalov is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 17:43.

Tue Apr 13 17:43:34 UTC 2021 up 5 days, 12:24, 1 user, load averages: 4.48, 4.71, 4.73

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.