This Hat Rack Puzzle by Sam Loyd was published 100 years ago in Woman's Home Companion:
Q: A hat room contains a wall with 49 pegs, arranged in a 7-by-7 square. The hat clerk has 20 hats that are to be hung on 20 different pegs. How many lines, containing four hats in a straight line, is it possible to produce? A line can go in any direction: horizontally, vertically or obliquely. To explain your answer, number the pegs in order, from 1 in the upper left corner to 49 in the lower right corner; list which pegs you put the 20 hats on, and give the total number of lines containing four hats in a row.Liane has left, but it also seems like the NPR website editors are gone. Last week they had "goose" as a two word phrase (instead of "roast goose") and this week they misspelled Sam Loyd (as Sam Lloyd). Anyway, back to the puzzle; not counting rotations and reflections, I have 3 ways to get the answer.
Edit: If you re-read my post you'll see the phrase "are gone" at the end of the first sentence. This is a homophone of Argon with atomic number 18, a clue to there being 18 lines in the solution(s).
A: I found 3 main solutions (not counting reflections and rotations). Click each one to see a larger view with any rotated/reflected variants.
Here's my standard reminder... don't post the answer or any hints that could lead directly to the answer (e.g. via Google or Bing) before the deadline of Thursday at 3pm ET. If you know the answer, click the link and submit it to NPR, but don't give it away here.
ReplyDeleteYou may provide indirect hints to the answer to show you know it, but make sure they don't give the answer away. Thank you.
I know the puzzle asks for both the number and the layout so it would seem okay to reveal the number. I think if we confirm the number of lines, it will give away the layout, so please don't mention the number either.
ReplyDeleteA question for our Blogmeister (or anyone): How much peg overlap is acceptable? E.g., in two lines can 0, 1, 2, or 3 pegs be counted in both? Since there is no specific instruction to the contrary, I’m thinking anything up to 3 is fair game.
ReplyDeleteChuck
Blaine:
ReplyDeleteWell the NPR website editors may have gone to L but I do enjoy our temporary host.
I too have found three answers that work if I am not cheating. I wish Will had stated the puzzle more clearly.
ReplyDeleteSome of my assumptions.
ReplyDelete1) All pegs are perfectly aligned with a 7 x 7 grid, equidistant vertically and horizontally.
2) A hat on a peg can be part of multiple lines.
3) A line with 4 (or more hats) is only counted once.
4) Hats need not be equidistant in a line.
@Blaine -
ReplyDeleteWell, #4 gives me pause. Let me see if phrasing this in chess terms shakes anything loose...
Let's say I have four pawns on rank #2. Regardless of the files those pawns are on, that would count as a "line", correct?
If I had five pawns on that rank, I could count two lines on that rank, correct? Again, regardless of the files.
Your first statement matches my fourth. Your second statement contradicts my third. I would say that additional hats in a line still count as one line since they are colinear.
ReplyDeleteThanks, Blaine. This certainly is an interesting puzzle. Nice change :)
ReplyDeleteI am concerned about a gray area. The puzzle asks how many lines containing four hats, not at least four hats. IMO, a line with five or more hats cannot be counted at all.
ReplyDeleteTB: I have the same concern.
ReplyDeleteOne fix for that, don't put more than four hats in a line.
ReplyDeleteThat is what I thought too. I think we most likely have the same solutions, but it will be interesting to see.
ReplyDeleteToo sweet, tout de suite. I believe there is a single answer.
ReplyDeleteI had a problem posting via google which was acting up something fierce. It appears to have lost my screen name, and titled my post "by ananymous" but refused to post it. Everything ok after resubscribing.
ReplyDeleteAnother hint-Visualize yourself walking along the edge of a military cemetary.
I have been assuming that a line of four hats does not have any empty pegs in the middle. That is, 3 hats, a peg, then one more hat, would not be a line of four hats. Maybe that's not right?
ReplyDeleteAlso, does "obliquely" include "over 2 down 1" or just 45 degree slopes?
The rules seem too vague, but perhaps I'm over thinking it.
A couple of items –
ReplyDeleteLast week: I thought it was interesting that only 300 folks got last week’s puzzle. It seemed to me that most here had it nailed...
This week: I hear a famous drummer...
Chuck
I am now about to submit my answer. If it is not correct, but I am sure it is, I will forward it to Obama for a line item veto.
ReplyDeleteThis is the best puzzle I remember from Will. If I win I think I will pawn my prizes.
I was very surprised that LESS than 300 sent in answers to the previous puzzle as I do not watch TV and never saw the show, but I still got the answer in less than 10 minutes. I suspect I was the first to submit it as I sent it in right away and it was by accident that I saw the puzzle posted right away. I suspect less than 100 will get the correct answer this week.
ReplyDeleteThe misspelling of Sam Loyd's name has been corrected on the NPR website. The fix for last week's "goose" vs. "roast goose" has not.
ReplyDeleteThat should L evate things. So, how do we get Will to more clearly present his puzzles?
ReplyDeleteNow I must apologize for using "less" when I should have said "fewer" in an earlier post. But I think I was just parroting their error.
One of the guest host's comments while introducing the Roast Goose puzzle reminded me of a conversion table that one of my schoolmates had assembled (many years ago). One of the conversions was: Multiply Ft/Sec by (some factor) to get Furlongs/Fortnight.
ReplyDeleteBTW -- No one has commented about Will's numbering system. Is peg number two to the right of peg number one, or below it? Or, perhaps it doesn't matter...
Also, if we allowed, for example, a line with five hats to be counted as multiple lines (which I agree we shouldn’t), then that line would become five lines, e.g., 1, 2, 3, 4 and 1, 2, 3, 5 and 1, 2, 4, 5 and 1, 3, 4, 5 and 2, 3, 4, 5.
Thanks, I like the Furlongs/Fortnight aside.
ReplyDeleteWho is BTW? (Just kidding!) I noticed this right away too, but it does not matter.
As to the five hats issue: That is why I posted: So, how do we get Will to more clearly present his puzzles? Sam "One L" Loyd was clear about such issues.
@Phil J,
ReplyDeleteGiven that we read left to right, top to bottom, I would assume that peg 2 is to the right of peg 1. That's the numbering order for crosswords too, which would probably make sense to someone like Mr. Shortz. But as you noted, it really wouldn't matter, would it? Flip the numbers along the diagonal, or flip the hats along the diagonal and you still have a valid solution.
Regarding multiple hats on a line, it would get even worse if you placed all 7 hats on a line. Mathematicaly there are 7 choose 4 ways (35 ways) to pick the four hats that form a line.
@Chuck,
ReplyDeleteI just reread your question and think it gets back to the multiple hats in a single line and my "rule" #3.
To state it using your terms, two lines may not have more than 1 hat in common. And if two lines do share a hat, they shouldn't be at the same angle. (This makes it so 7 hats in a row wouldn't count as two lines sharing the middle hat).
This might make a good TV show. It could be called, "What's My Line?"
ReplyDeleteIn the past I've noticed that if Will does not state something, such as the direction of the numbering in this puzzle, then it probably does not affect the answer. These "omissions," by themselves, can be taken as clues. In this case, perhaps that the intended solution is symmetrical.
ReplyDeletePhilJ:
ReplyDeleteIt doesn't matter if the puzzle is symmetrical or not, it would still be the same numbering submitted. What does matter is if you are allowed more than 5 hats in a line. Sam Loyd would have so stated, but Will did not, and it does affect the answer here.
I think some might miss that it was a waste of type to indicate "from 1 in the upper left corner to 49 in the lower right corner." It does not matter what corner you start from or which direction (clockwise or counter clockwise) you go, even if the puzzle is not symmetrical. Will could not possibly tell. Perhaps this is a puzzle within a puzzle.
ReplyDeleteBlaine –
ReplyDeleteI have no problem with your assumptions concerning this puzzle – in other words, I believe it’s likely that your assumptions are the same as those of Sam Loyd. I sent my answer in on Sunday based on them.
At first I thought this puzzle was about combinations or permutations. I no longer believe this is true but in doing some research I found a very useful online calculator site I’d like to share with all here:
http://www.mathsisfun.com/combinatorics/combinations-permutations-calculator.html
I wonder how many here will get my clue. No reflection on Blaine’s bloggers, only a question about the aptness of my clue...
Chuck
With 49 pegs and 20 hats there are 28,277,527,346,376 ways to place the hats. Obviously a brute force approach isn't the best idea so hopefully people are applying some logic to this.
ReplyDeleteHi skydiveboy,
ReplyDeleteMy premise was that not specifying the numbering direction was itself a hint of sorts.
As Blaine pointed out, whether you start numbering across or down, you can easily map into the other numbering pattern by flipping the numbers around the 1-to-49 diagonal. If, indeed, there is only one set of numbers that will uniquely validate the correct answer, regardless of whether you number across or down, it seems to me that the intended solution must also be symmetrical about that same diagonal. No?
No.
ReplyDeleteIf the puzzle is asymmetrical then Will needs two sets of peg numbers, because the puzzle will work no matter which corner you start at and no matter which direction you go, and he would be unable to tell.
If the area were instead a rectangle, say 42 pegs and 6 X 7, then it would matter, but you could still begin from either top left corner or bottom right corner as long as you go clockwise and arrange the rows as directed.
Correction:
ReplyDeleteHe might need several sets of peg numbers depending.
Blaine:
ReplyDeleteIs that figure you posted assigning individuality to each hat? This puzzle does not do that.
@SDB Nope, that formula accounts for the hats being indistinguishable.
ReplyDeleteAmazing. I don't think there will be that many entries this week. My hat is off to you for figuring that out for us.
ReplyDelete@SDB The number I gave is linked to the Wolfram Alpha site that can be used to calculate "n choose r". You can also type "49 choose 20" into Google. Finally, you can replicate the results using Chuck's link. Just be sure to click "No" to order matters and repeats allowed.
ReplyDeleteYou guys are driving me nuts. The answer is simple. Not to belittle women, but the Woman's Home Companion - C'mon. No problem at all with the puzzle's wording. One question was asked which, if posed as a statement, should have been deleted by Blaine.
ReplyDeleteFolks from the pre-computer age would probably draw a nice, big diagram and figure it out without all the hoo-hah. I had more trouble counting lines than placing the hats.
If this is too close to a flame, I'm sorry.
Google forced me to re-resubscribed. Now I'm really ticked off.
RoRo says
ReplyDeleteHugh, I feel your pain. Wazzup with Google.
No hint here. Hats off to those who got it. Everytime I think I have it I have only used 19 hats. I love patterns yet math and logic are not my strong suit.
RoRo:
ReplyDeleteKeep at it, but you need to think inside the box.
Hugh:
I had a similar problem about 3 weeks ago. It became impossible for me to post. (BTW an anagraam for post is stop.)
@Hugh, I actually still have the problem of trying to post comments to my own blog. It works on one PC but not the other. It will ask me multiple times to logon on (even if I was already) and then tries to show as 'Anonymous' but then won't post.
ReplyDeleteThe workarounds noted on the Google Blogger Forums suggest the following:
1) Try clearing your cache, temporary files, cookies, etc. In IE, you type Alt-T to get the Tools menu then choose 'Delete Browsing History'. Check the items to clear.
2) During commenting, if prompted to login do so but uncheck the box that says 'Keep me logged in'.
So far the first workaround didn't help but the second has. Again it is a workaround, not a fix because now I have to login each time. But it is better than not being able to post comments.
This comment has been removed by a blog administrator.
ReplyDeleteEnya_and_Weird_Al_fan:
ReplyDeleteI would not place too much faith in my early post here that indicated I found 3 solutions. I was wrong and maybe I should go back and delete the post, but I forgot about it.
More importantly, you may NOT have more than 4 hats in a row. Today I sent Will an email re: this and another glitch.
I think Blaine is going to delete your post when he reads it because it mentions line numbers and he had asked us not to do that, so you might want to delete it yourself.
Hey Skydiveboy, I'M not as certain as you that the NPR website editors have gone to L. Then again, there is a new ambiguity with only four hats in a row.
ReplyDeleteWouldn't a line containing four out of the five hats in a certain row still be a line of four hats? We'll have to see.
- Other Ben
This comment has been removed by a blog administrator.
ReplyDeletePeople are spending too much time worrying about more than 4 hats in a line.
ReplyDeleteDon't be a mad hatter!
ReplyDeleteI've worked on this puzzle so long I con no longer see the hat rack through the pegs. Here's an arboreal puzzle to try.
ReplyDeleteA New Tree Puzzle
@SDB Thanks for the encouragement although being boxed in can sometimes be a good thing.
ReplyDeleteI thought this would take me days, even 2 weeks to solve but I finally have an answer I hope is right. Reminds me of a puzzle someone suggested to me on this blog weeks ago Abbott and Costello style.
Chuck,
ReplyDeleteI'm in awe of anyone who lets others in, knowing where they've been.
Somehow one of Hagar's lines seems appropriate.
ReplyDeleteNo! No! Pillage -- then burn.
OK, Hugh;
ReplyDeleteIf it's not "Let me not see the death of the child.", then it's one of Sammy's.
Yes, no, maybe so?
(It'll probably take me at least a fortnight to figure out any response.)
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.
ReplyDeleteAnyone have a solution that is not rotationally symmetric?
ReplyDeleteI 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:
ReplyDeleteA 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.
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.
Of course there may not be more than four trees in any row.
END
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.
Kudos to Blaine for getting the L clue.
This was the best puzzle in some time now.
Blaine,
ReplyDeleteI only had your first solution.
I expected you'd have something impressive, but.....yikes!.....gimme a fortnight or two......nah!...gimme a few kalpas.
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".
Hence the awkward paraphrase of a line from "Octopus's Garden".
skydiveboy,
Hope you win; if so,hope you reconsider pawning the prizes; if not, hope you don't get rooked.
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.
ReplyDeletePaul:
ReplyDeleteNo, I again did not win. So there will be no celebration for me toKnight.
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!
ReplyDeleteNumber of Inches in a Foot = 12
Number of Days in a Fortnight = 14
Number of Furlongs in a Mile = 16
Next number in the series = 18 --> the answer
(OK, they're a little out of order -- don't quibble!)
:-)
Reminds me of the time Marilyn Monroe was asked: "Have you been wearing furlong?"
ReplyDeleteI 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.
ReplyDeleteToo(2) + Sweet(16) = 18 total lines.
Hagar the Horrible: No! No! lines -- then hats.
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.
Blaine, Thanks for the info on Google.
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.
ReplyDeleteNew 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.
ReplyDeleteI meant PDST. As in Pacific Daylight Saving Time.
ReplyDeleteBlaine: Congratulations for being the Blog of Record for NPR :)
ReplyDeleteCongrats 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.
ReplyDeleteKudos, Blaine: the NPR Weekend Edition Sunday puzzle webpage points to your blog for the explanation of the answer to this puzzle.
ReplyDeleteKen, I think you will not find the puzzle will get in the way of your party.
ReplyDeleteKen, that is an excellent clue!
ReplyDeleteIt 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?
ReplyDeleteThis ambiguity/ignorance completely turned me off of this week's puzzle.
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?
ReplyDeleteI 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.
ReplyDeleteIt 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.
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.
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.
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. :)
ReplyDelete@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.
ReplyDeleteFor 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:
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).
2. "vertical" lines: If the difference between any two of the four is a multiple of 7 (excluding zero).
3. "diagonal" lines: If the difference between any two of the four is a multiple of 8 (excluding zero).
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).
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.
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).
ReplyDelete