tag:blogger.com,1999:blog-5730391.post1163374646641702089..comments2024-03-28T16:39:55.561-07:00Comments on Blaine's Puzzle Blog: NPR Sunday Puzzle (Jun 12, 2011): Sam Loyd's Hat Rack PuzzleBlainehttp://www.blogger.com/profile/06379274325110866036noreply@blogger.comBlogger76125tag:blogger.com,1999:blog-5730391.post-46658798604769779242011-06-23T07:46:07.053-07:002011-06-23T07:46:07.053-07:00Alternatively, if you could prove that it is impos...Alternatively, if you could prove that it is impossible to have 19 or more distinct combinations that have those properties, then you'd be done (because you've already shown a witness for 18).Ted Pavlichttps://www.blogger.com/profile/15297790411942050417noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-26844484546344164542011-06-23T07:43:54.014-07:002011-06-23T07:43:54.014-07:00@Blaine: Okay, so that solution method (reducing t...@Blaine: Okay, so that solution method (reducing the size of the state space and then exploring the resulting smaller, but sufficient, space) is fine... but I can't imagine that's what Sam Loyd did circa 1899. Certainly there's a more elegant and/or mathematical solution.<br /><br />For example, I think the geometric layout is a red herring. If you just consider a set of numbers with certain relationships, there's less to worry about with symmetric solutions. You could imagine twenty numbers with the property that there exists 18 distinct combinations of 4 of them that have three different properties:<br /><br />1. "horizontal" lines: If all four are within two adjacent multiples of 7 (including 0) and they are adjacent (which you can ensure by checking that their sum is correct for four adjacent natural numbers).<br /><br />2. "vertical" lines: If the difference between any two of the four is a multiple of 7 (excluding zero).<br /><br />3. "diagonal" lines: If the difference between any two of the four is a multiple of 8 (excluding zero).<br /><br />You'd have to add something to exclude lines of 5 or more, but I have a feeling there's an elegant way to exclude them without anything special (e.g., there may be a way to show that no way you could lines of 4+ will give you more than 18 lines).<br /><br />I think there should be way to show that over all sets of 20-sized subsets of {1,...,49}, the maximum number of unique combinations that have those features is 18... and I bet the solution doesn't require a sufficiently exhaustive search of a space.Ted Pavlichttps://www.blogger.com/profile/15297790411942050417noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-71454269586817099072011-06-21T07:50:26.265-07:002011-06-21T07:50:26.265-07:00I added additional tests for bilaterally symmetric...I added additional tests for bilaterally symmetric layouts. It found pattern #1 again, but no others. Testing non-symmetric layouts is left as an exercise for the reader. :)Blainehttps://www.blogger.com/profile/06379274325110866036noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-74295525148815737732011-06-20T22:51:34.708-07:002011-06-20T22:51:34.708-07:00I first came up with patterns #1 and #2 by playing...I first came up with patterns #1 and #2 by playing with pencil and paper. I tried to maximize the reuse of hats by trying to take places where there were already 2 or 3 hats to make another line (or two). For example, diagram #2 started with 16 hats in a 4 x 4 array, turned 45° and that made 10 lines. Each hat I placed after that made two more lines for a total of 18 lines. I could not manually come up with any solution with more lines than that.<br /><br />It was at that point that I decided to focus on rotationally symmetric patterns. I wrote a program to generate all possible layouts of 10 hats within the first 24 pegs. Rather than testing 28 trillion options, I then only had to test 1.9 million which is a lot more manageable.<br /><br />The program rotated the hats and filled the other half of the diagram for a total of 20 hats placed. The program counted all the possible lines and returned any results that had 18 (or more) lines. It kicked out the 7 results I noted.<br /><br />So analytically I have proven these are the best (and only) rotationally symmetric patterns. If I get some more time I might test mirrored patterns. I don't know if I'll try the rest of the non-symmetric patterns.Blainehttps://www.blogger.com/profile/06379274325110866036noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-77553568855153905062011-06-20T10:27:15.425-07:002011-06-20T10:27:15.425-07:00I'm confused. There's no analytical way to...I'm confused. There's no analytical way to solve this puzzle and prove the result? Did you apply a model checker to exhaust all possible combinations (a comment you made implies you didn't use a brute force method, but your questions to readers make it sound like you just did a search). Can you prove analytically that it is impossible to have more than 18 lines?Ted Pavlichttps://www.blogger.com/profile/15297790411942050417noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-76271951559025993902011-06-20T10:18:17.340-07:002011-06-20T10:18:17.340-07:00It seems pretty lame that the outline of the puzzl...It seems pretty lame that the outline of the puzzle only gave the index of the top left corner and bottom right but no information about the pattern after that. Sure, going right-then-down is essentially identical to going down-then-right, but what about the diagonal ordering you would use to enumerate the rational numbers?<br /><br />This ambiguity/ignorance completely turned me off of this week's puzzle.Ted Pavlichttps://www.blogger.com/profile/15297790411942050417noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-36668442163841501862011-06-19T04:39:13.793-07:002011-06-19T04:39:13.793-07:00Ken, that is an excellent clue!Ken, that is an excellent clue!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-5730391.post-50524652964889530072011-06-18T18:08:30.517-07:002011-06-18T18:08:30.517-07:00Ken, I think you will not find the puzzle will get...Ken, I think you will not find the puzzle will get in the way of your party.skydiveboyhttps://www.blogger.com/profile/17174073226290431753noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-38067984157700182172011-06-18T17:56:16.798-07:002011-06-18T17:56:16.798-07:00Kudos, Blaine: the NPR Weekend Edition Sunday puz...Kudos, Blaine: the NPR Weekend Edition Sunday puzzle webpage points to your blog for the explanation of the answer to this puzzle.janhttps://www.blogger.com/profile/05927176621372532733noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-34953996743605992652011-06-18T17:53:27.992-07:002011-06-18T17:53:27.992-07:00Congrats to Blaine for Will's reference to the...Congrats to Blaine for Will's reference to the blog. Perhaps we'll see more traffic. Anyway, I'll work on the new puzzle while attending my reunion.kenhttps://www.blogger.com/profile/05882757881891590225noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-75461172870593656202011-06-18T17:53:26.371-07:002011-06-18T17:53:26.371-07:00Blaine: Congratulations for being the Blog of Reco...Blaine: Congratulations for being the Blog of Record for NPR :)Doctechnicalhttps://www.blogger.com/profile/06817162059249352531noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-792146016797520432011-06-18T16:52:29.395-07:002011-06-18T16:52:29.395-07:00I meant PDST. As in Pacific Daylight Saving Time.I meant PDST. As in Pacific Daylight Saving Time.skydiveboyhttps://www.blogger.com/profile/17174073226290431753noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-55135481869013196672011-06-18T16:50:20.271-07:002011-06-18T16:50:20.271-07:00New puzzle posted @ exactly 4:40 PM PSDLT. This is...New puzzle posted @ exactly 4:40 PM PSDLT. This is the first time I actually had the answer as I was reading the question. I have already sent it in. So this week we go from great to really simple and not just by chance either.skydiveboyhttps://www.blogger.com/profile/17174073226290431753noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-16341951125457543142011-06-17T11:23:38.094-07:002011-06-17T11:23:38.094-07:00You know, I think I am actually ok with my solutio...You know, I think I am actually ok with my solution (I suppose that is in "personal best category") because although I only have 14 possible rows, I don't have any hats of less than 4 (except for the four outstanding points which are really corner hats) hanging out there. So, while mine is safe and not outside the boxy I think it meets the best way to have neat 4s. But thanks to my fellow bloggers for ultimately taking me outside of my box.Robin Thomas Poponnehttps://www.blogger.com/profile/05703107344880425239noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-37149875023901504622011-06-17T09:44:56.050-07:002011-06-17T09:44:56.050-07:00I found Blaine's #1 solution, which I suspect ...I found Blaine's #1 solution, which I suspect is the expected solution because it doesn't raise questions with the wording of the puzzle. I lack RoRo's persistence and quit with this solution.<br /><br />Too(2) + Sweet(16) = 18 total lines.<br /><br />Hagar the Horrible: No! No! lines -- then hats.<br />Meant to show that finding the 12 obviously acceptable lines, which contain exactly 4 pegs each, (lines of the octagram and diamond), identify the 20 pegs of solution #1. This is a "no sweat solution". The remaining 6 lines with more than 4 pegs are gimmes. <br /><br />Blaine, Thanks for the info on Google.hughhttps://www.blogger.com/profile/16914509834442545746noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-62320928395755674492011-06-16T16:44:40.891-07:002011-06-16T16:44:40.891-07:00Reminds me of the time Marilyn Monroe was asked: &...Reminds me of the time Marilyn Monroe was asked: "Have you been wearing furlong?"skydiveboyhttps://www.blogger.com/profile/17174073226290431753noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-85264402116434799802011-06-16T16:34:50.405-07:002011-06-16T16:34:50.405-07:00In an earlier post I mentioned the conversion fact...In an earlier post I mentioned the conversion factor to transform Ft/Sec into Furlongs/Fortnight. "Fortnight" was meant to be a clue, as I thought at the time that the solution had 14 lines. Later I discovered a solution with 18 lines (Blaine's first solution). But my clue still works!<br /><br />Number of Inches in a Foot = 12<br />Number of Days in a Fortnight = 14<br />Number of Furlongs in a Mile = 16<br />Next number in the series = 18 --> the answer<br /><br />(OK, they're a little out of order -- don't quibble!)<br /><br />:-)Phil J.https://www.blogger.com/profile/01379207009607141221noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-3835772835020642902011-06-16T15:48:57.492-07:002011-06-16T15:48:57.492-07:00Paul:
No, I again did not win. So there will be no...Paul:<br />No, I again did not win. So there will be no celebration for me toKnight.skydiveboyhttps://www.blogger.com/profile/17174073226290431753noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-79532359940169326102011-06-16T14:47:29.249-07:002011-06-16T14:47:29.249-07:00Wow! This was tough for me. I had an answer clos...Wow! This was tough for me. I had an answer close to Blaine's first one except my corners weren't spread out enough. Blaine's 1,7, 43, and 49 were my 9, 13, 37, and 41 So I only saw 14 rows. I thought all the fortnight hints pointed to that. I thought mine looked like a baseball field thus the Abbott and Costello reference. I am happy I got an answer at all.Robin Thomas Poponnehttps://www.blogger.com/profile/05703107344880425239noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-31250433711074501702011-06-16T13:11:47.826-07:002011-06-16T13:11:47.826-07:00Blaine,
I only had your first solution.
I expecte...Blaine,<br /><br />I only had your first solution.<br />I expected you'd have something impressive, but.....yikes!.....gimme a fortnight or two......nah!...gimme a few kalpas.<br /><br /><br />When I first read Chuck's clue, and looked at my diagram, I thought "Starr/star OK, I get it", but later I thought "It's an EIGHT-pointed star".<br /><br />Hence the awkward paraphrase of a line from "Octopus's Garden".<br /><br />skydiveboy,<br /><br />Hope you win; if so,hope you reconsider pawning the prizes; if not, hope you don't get rooked.Paulhttps://www.blogger.com/profile/11114786604125384958noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-35441131219908590012011-06-16T12:37:52.929-07:002011-06-16T12:37:52.929-07:00I submitted the first answer. After I solved the p...I submitted the first answer. After I solved the puzzle I went searching to see if I could find it online in order to settle the question of five hats in a line being allowed or not. I did not find this exact puzzle, but one that is essentially the same, but with two more hats and it states the number of lines up front and goes on to say that no line may have more than 4 hats (trees, in this case). Here is the puzzle I found:<br /><br />A short time ago I received an interesting communication from the British chaplain at Meiktila, Upper Burma, in which my correspondent informed me that he had found some amusement on board ship on his way out in trying to solve this little poser.<br /><br />If he has a plantation of forty-nine trees, planted in the form of a square as shown in the accompanying illustration, he wishes to know how he may cut down twenty-seven of the trees so that the twenty-two left standing shall form as many rows as possible with four trees in every row.<br /><br />Of course there may not be more than four trees in any row.<br /><br />END<br /><br />I said if I won I would pawn my prizes. That was a hint that I used pawns and a chess board from two of my chess sets to solve the puzzle.<br /><br />Kudos to Blaine for getting the L clue.<br /><br />This was the best puzzle in some time now.skydiveboyhttps://www.blogger.com/profile/17174073226290431753noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-34486273363644589062011-06-16T12:06:00.036-07:002011-06-16T12:06:00.036-07:00Anyone have a solution that is not rotationally sy...Anyone have a solution that is not rotationally symmetric?Blainehttps://www.blogger.com/profile/06379274325110866036noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-65933520839215171672011-06-16T12:05:06.479-07:002011-06-16T12:05:06.479-07:00All of my solutions have 180° symmetry (also comme...All of my solutions have 180° symmetry (also commented on by others and hinted at numerous times by SDB with his L=50 hint.) Pairs of hats will add up to 50, like 1 and 49, 4 and 46, etc.Blainehttps://www.blogger.com/profile/06379274325110866036noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-73857428445869924672011-06-16T11:45:24.913-07:002011-06-16T11:45:24.913-07:00OK, Hugh;
If it's not "Let me not see th...OK, Hugh;<br /><br />If it's not "Let me not see the death of the child.", then it's one of Sammy's.<br /><br />Yes, no, maybe so?<br /><br />(It'll probably take me at least a fortnight to figure out any response.)Paulhttps://www.blogger.com/profile/11114786604125384958noreply@blogger.comtag:blogger.com,1999:blog-5730391.post-35090671905305726892011-06-16T06:36:54.349-07:002011-06-16T06:36:54.349-07:00Somehow one of Hagar's lines seems appropriate...Somehow one of Hagar's lines seems appropriate.<br /><br />No! No! Pillage -- then burn.hughhttps://www.blogger.com/profile/16914509834442545746noreply@blogger.com