## Thursday, January 10, 2013

### NPR Sunday Puzzle (Jan 6, 2013): Sam Loyd Puzzle (16 boxes, 10 markers)

NPR Sunday Puzzle (Jan 6, 2013): Sam Loyd Puzzle (16 boxes, 10 markers):
Q: This challenge appeared in a puzzle column in the Woman's Home Companion in January 1913, exactly 100 years ago. Draw a square that is four boxes by four boxes per side, containing altogether 16 small boxes and 18 lines (across, down and diagonal). There are 10 ways to have four boxes in a line — four horizontal rows, four vertical columns, plus the two long diagonals. There are also eight other shorter diagonals of two or three squares each. The object is to place markers in 10 of the boxes so that as many of the lines as possible have either two or four markers. What is the maximum number of lines that can have either two or four markers, and how do you do it?
Sorry, I needed my full 8 hours of sleep so wasn't able to post earlier, but I'm awake now. No doubt people are going to find this a tricky puzzle, so I added a diagram to help out. Apart from reflections or rotations, I've found a single solution that maximizes the number of lines. Please don't mention how many lines are involved until after the deadline. For those that are mathematically inclined, there are 8008 ways to place 10 markers into 16 squares and, accounting for symmetry, it shouldn't be too hard to brute force the answer. :)

Edit: My hints above were to the number of lines being 16. Being asleep for 8 hours leaves 16 waking hours. The group "No Doubt" has a song called "Sixteen" on their album "Tragic Kingdom". Also the reference to the number of possible arrangements (8008) hinted at 8 horizontal/vertical lines and 8 diagonal lines. Finally, in a post I mentioned the Beatles' song "Taxman" which was parodied by Weird Al as "Pac Man"... I think the answer looks like Pac Man eating a dot.
A: 16 lines in one of 4 symmetric arrangements:
Solution A: 1, 3, 7, 8, 9, 10, 11, 12, 14, 15
Solution B: 2, 3, 5, 6, 7, 8, 9, 10, 14, 16
Solution C: 2, 3, 5, 6, 7, 8, 11, 12, 13, 15
Solution D: 2, 4, 5, 6, 9, 10, 11, 12, 14, 15

#### 102 comments:

1. 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.

You may provide indirect hints to the answer to show you know it, but make sure they don't give the answer away. You can openly discuss your hints and the answer after the Thursday deadline. Thank you.

2. The winter snow always reminds me of this Tom Chapin song:

I said, "Hey daddy, daddy, daddy-o, let's build a snowman in the snow". He said, "No, we're shovelling. Now get to work". Shovelling, shovelling, shovelling all night long.

1. My musical clue: "Taxman" by the Beatles

2. Musical clue: Johann Sebastian Bach

3. Interesting that Will Shortz admitted to and then corrected one error from two weeks ago, but then went on to commit two more, one of which is egregious.

He said Peary, whose name he mispronounced, was the first to reach the North Pole, when research has proven this to be a huge hoax and lie by Peary. Roald Amundsen was the first to reach both poles, and there is no dispute over his achievement.

Hoaxes and lies and deceptions seem to always win out over truth. My favorite is the one about cold temperature causing the common cold, when it has long ago been proven to be completely false. It pops up everywhere and people seem to be willing to die defending this nonsense.

1. Alrighty then for our next contestant, SDB: Add an s to mundane. Anagram the result and it will give you the man credited to have discovered both poles. SDB?

2. Right, and I posted his full name above. His achievement was anything but munDane. Not even munNorwegian.

3. You right on SDB. You MUNey even on MUNday.

4. MUNdays used to be full of dread, but now they're happy times. :-)

4. I am fairly certain I have the correct answer, but it would be nice to know what the maximum number is in order to be sure and to not have to depend on luck.

1. Blow out the candles on your cake and St. Peter will make your wish come true.

2. Here are some related puzzles:
* How many markers (and in what arrangement) would be necessary to cover all 18 lines with 2 or 4 markers?
* What's the *minimum* number of lines (of 2 or 4) that could be created using 10 markers.

As for the answer to your question, it can't be smaller than 0 or bigger than 18. But beyond that, I'd like to keep it unstated.

3. And that is why I did not indicate the number I came up with.

4. This comment has been removed by the author.

5. @Zeke - Anything is possible, well, almost.
@Blaine - Nice related puzzler. The "minimum" one was a real poser.

6. As for the minimum I have the answer for you.

5. Another related question is how many markers do you need to use to get the same number of lines as the answer to today's puzzle. Can you do it with fewer than 10?

1. "Really? That would be a neat trick." -Victor Maitland

2. Using just 8 is pretty sweet.

6. Okay, this baffles me. Posting to this site with my Wordpress account sometimes allows me enter my name to appear on the post, other times, when I try to post, it forces me to be Anonymous. I'd much rather use my Wordpress account than my Google account, but it's becoming rather frustrating to not be able to control how my name appears.

- Curtis

1. Sorry, retract that comment. It appears to be an oddity in how the preview pane displays.

2. I don't mean to be curt, but it would appear your name has not achieved peerage.

3. Right you are, SDB.

4. I think I've got it figured out. Now, I just have to figure out why anyone would want to jump out of airplanes... ;-)

5. These 3 guys were not jumping at an airfield or a drop zone. They were using some clearing to land and take off from with the tiny 'copter.
Make one freefall and you will understand why people skydive.
The search was called of this afternoon and they said they may resume an air search later in better weather, but they figure he is dead. If he did not activate either parachute, nothing will be visable unless he is lying in an open place that is not grassy, etc. and that is not at all likely. I will be surprised if they find his body.

7. My eyes and ears glazed over when I heard Will describe the puzzle (not a fan of mazes or math). Perusing the hefty January 1913 Woman's Home Companion proved far more fascinating than figuring out this snoozer - the articles, illustrations, products and prices, and overall feel of that era provided a couple of hours of satisfying entertainment. Have fun!

8. Why did he not say lines of two, three or four markers?

1. Are you suggesting Will transcribed Sam Loyd's puzzle incorrectly? I'm pretty sure that Loyd intended for only lines with an even number of markers to count but then someone might argue that a line with zero markers would satisfy the puzzle, hence the statement about 2 or 4.

2. I have looked at the original statement of the puzzle
in the Jan., 1913 Woman's Home Companion, page 47. Will has transcribed it correctly.

9. Sorry, I misunderstood the puzzle. I was looking for continuos lines of at least 2.

10. This comment has been removed by the author.

11. SDB, what do you suppose the chances are that the people searching for that Florida skydiver in Washington might find D. B. Cooper instead?

1. Jan:
The chances are ZERO! The area where the missing skydiver jumped is only a few miles from where the FBI obtained the four parachutes for D. B. Cooper from the former Issaquah Parachute Center. Cooper and his flight headed from Seatac, located SW of there, South. Cooper had to have died on that jump or shortly after. This is a very heavily forrested state, and his body may never be found, but some of the money has been.
The missing jumper is also likely to be next to impossible to find in the area he jumped in. I could say a lot more, but not here.

12. Blaine –

In an earlier post you said, “Apart from reflections or rotations, I've found a single solution that maximizes the number of lines.” Did you mean that there is one and only one such solution, or that you’ve found one but there may be others as yet undiscovered?

The reason I’m asking is because I have found two distinct configurations that produce the highest number I’m able to find. Of course, I don’t know what the highest number is so both could be wrong...

Chuck

1. I've only found one configuration. I guess I'll have to see if I can find another.

2. I agree with Chuck.

3. Hint to blaine and Chuck: Leapfrog.

13. I only found one solution, which can rotate easily around the diagram. But, I can't say I have the definitive answer.

1. Depending on your definition of 'easily'....:)

14. On air, the puzzle was first stated as Blaine and WS wrote on the internet:

to place markers in 10 boxes.

But WS, on air, restated the puzzle:

to place 10 markers in boxes.

Utter confusion from the broadcast.

1. You have it backwards. The web site description is probably not written by WS, but by an intern. The on air description is NOT a restatement, but the original.

Anyway, you may NOT place more than one marker in any box in this puzzle.

2. Capital letters....always works....shows....something or other.

3. SDB: All I was saying was that the written internet versions by by Blaine and the intern were in agreement.

However, in his own voice, WS over the air, made the contradictory statements. He typically states the puzzle twice, and he posed the two variations of the puzzle.

Listen to:

http://www.npr.org/player/v2/mediaPlayer.html?action=1&t=1&islist=false&id=168698679&m=168699082

Get off the internet once in a while and take a flying leap (into the great unknown outside).

4. Hugh,
I got a different meaning from your post than what you meant.

15. One marker per box.
Do I feel safe in asserting that?
That's a good question!

1. I saw more than one cat per box????

2. Excellent point, Zeke! I'll take it into consideration.

3. Never, ever, think outside the box.

cartoonbank.licensestream.com/LicenseStream/ContentStorage_CondeNast/1/UserComps/autuhtds.jpg

16. I mentioned in an earlier post that I found two solutions that produce the same number of lines which contain either 2 or 4 markers. (Of course, I still don’t know if this number is the highest number possible.) Anyway, I noticed an interesting thing about the two solutions – one of them is symmetrical around a bisecting axis. The other one is not. Go figure...

Chuck

17. For the on air versions of the puzzle listen to:

WS's 2 Puzzle Statement's

1. I don't see the confusion. His restatement is not a clarification, but his usual quick repeat.

18. A confession –

I was wrong concerning my previous answer – I had miscounted one of my configurations. I now know of one and only one correct answer. And BTW, it _is_ symmetrical around a bisecting axis. Sorry if I threw anyone here off the track :(

Chuck

19. Before I found what I believe to be Blaine's answer, I had found two solutions which I had thought at the time both reach the maximum, but whose count of lines falls short of Blaine's answer BY ONE.

What I believe to be Blaine's answer is indeed symmetrical around a bisecting axis which is horizontal (or vertical, depending on how you choose to orient it).

The two solutions I had found earlier, which both fall one shy of what I believe to be Blaine's answer, are also symmetric, except their symmetries are about one of the main diagonals.

20. The new puzzle is up and running. Remember the game "Operation"?

You can play here

21. Ask Mrs. Wiggs!

22. Well, I finally had my epiphany for a puzzle presented on Epiphany. Sweet!!

23. My answer is symetric around (only) one of the digonals.

1. Then move just two of your markers and then you'll have a solution with the same number of lines, but with symmetry about the other diagonal!

24. I find four answers related by symmetry. That's what you'd expect to happen when you have squares.

1. The two answers to which I refer are unique, barring rotations and/or reflections. While they are each symmetric about one of the diagonals, there is no way to rotate or reflect one of them into the other. I believe the four answers to which you refer are in fact the four different orientations of Blaine's solution.

Remember in my post above, I said that what I believe to be Blaine's solution has one axis of symmetry which is horizontal, but then I added the parenthetical "(or vertical, depending on how you chose to orient it)."

2. Four squared is 16, also a square...

25. This puzzle also goes by the name The Jolly Friar’s Puzzle [hereafter, The JFP]. It appeared on page 307 of Sam Loyd’s 1914 Cyclopedia of Puzzles, now in the public domain.

Solution to The JFP and related puzzles:

The maximum number of lines having either two or four markers is 16 out of 18. Unique solution diagram [up to symmetry].

On the other extreme, the minimum number of lines having either two or four markers is one out of 18. Unique solution diagram [up to symmetry].

Finally, all 18 lines can be made to satisfy the given conditions by using 12 markers placed around the four-by-four square’s border. Unique solution diagram.

Video of all 1,051 arrangements, sorted naÃ¯vely according to order of discovery when we mark the boxes starting in the upper left and working our way across and down from left-to-right and top-to-bottom. In this system, the maximum solution is the 1,039th arrangement, while the minimum solution is 933rd.

Above video, resorted according to number of lines satisfying the given conditions.

Bar graph showing the distribution of JFP over all 1,051 arrangements.

Although (16 choose 10) = 8,008, accounting for symmetry reduces the total number of layouts to 1,051. While one may be tempted at first to assume that the number of permutations will be (16 choose 10) divided by the eight symmetries of the square [i.e., 1,001], this assumption undercounts due to arrangements that themselves feature rotational symmetry and/or symmetry about an axis.

Indeed, as a check on my work I derived the formula

(n choose k) = 8(x − (y + z)) + 4y + 2z
→ (n choose k) = 8x − 4y − 6z
x = ((n choose k) + 4y + 6z)/8,

where n is the number of boxes in our square [in this case, 16], k is the number of markers we’re placing in those boxes [in this case, 10], (n choose k) is the binomial coefficient n!/(k!(nk!)), x is the number of unique arrangements up to symmetry that we’re solving for, y is the number of arrangements that are either rotationally symmetric or that have a single axis of symmetry, and z is the number of arrangements with two axes of symmetry.

In practice, I counted my y’s and z’s and then checked that the resultant x matched the total number of arrangements I’d found.

Rotationally symmetric (11).

Symmetric about one axis (80).

Symmetric about two axes (6).

References:

Donald Knuth’s index to puzzles of mathematical interest.

Wikipedia entries on the symmetries of the square and the binomial coefficient.

Colored artwork and problem statement for The JFP.

The JFP as it appeared on page 307 of Sam Loyd’s Cyclopedia of 5000 Puzzles, Tricks and Conundrums, and its corresponding solution.

The JFP as it appeared on page 109 of Martin Gardner’s More Mathematical Puzzles of Sam Loyd, Volume 2.

1. Addenda:

1,051 total arrangements (up to symmetry) of 10 markers on a 4x4 grid, encoded as
Binary;
Hexadecimal; and
ASCII.

26. THIRTEEN (13) LINES

Using Blaine's diagram, place counters in the top two rows, #1 thru #8 and either #15 & #16 or #14 & #15. You now have two lines of 4 and eleven rows of 2.

MY HINT:

"I am fairly certain I have the correct answer, but it would be nice to know what the maximum number is in order to be sure and to not have to depend on luck."

Luck refers to the number thirteen, which many believe to be unlucky.

1. Sorry, your answer wasn't as *sweet* as that of others.

2. Now I see where I went wrong. My understanding of the puzzle was that a line could not be broken.
Funny too, that I discovered the page with the diagram of the answer that is linked above, but discounted it as being the answer to this puzzle as I was counting by my incorrect understanding.

27. 16

Number the boxes from 1 to 16 starting with 1 in the upper left hand box and ending with 16 in the lower right hand box.

2, 3, 5, 6, 7, 8, 9, 10, 14, 16

Chuck

28. The total is sixteen rows using ten markers. This answer is given on page 84 of the March, 1913 Woman's Home Companion.

On Blaine's numbered grid, put markers on squares numbered
2,4,5,6,9,10,11,12,14 and 15. (2,6,10,14) is a vertical row of four markers,
(9,10,11,12) is a horizontal row of four markers, (5,9), (11,15), and (4,12)
are three vertical rows of two markers, (2,4), (5,6) and (14,15) are three horizontal rows of two markers, (9,14), (6,11) and (2,12) are three rows of two markers slanting from upper left to lower right, and (5,2), (9,6), (10,4), (14,11) and (15,12) are five rows of two markers slanting from lower left to upper right.

You can also get sixteen rows using eight markers, placed in the squares numbered 2, 3, 5, 8, 9, 12, 14, and 15. In this case each row has only two markers, which connect (2,3), (2,5), (2,12) , (2,14), (3,8), (3,9), (3,15), (5,8), (5,9), (5,15) , (8.12), (8,14), (9,12), (9,14), (12,15) and (14,15).

29. Oops, I only got 14. My Bach hint referred to reports that 14 is 'encoded' in much of his music. Bach may have considered this number a sort of signature, since given A = 1, B = 2, C = 3, etc., then B + A + C + H = 14.

30. I only had 14; markers at 1,2,3,5,8,9,12,13,14,15.
Until yesterday morning, I only had 12; as above, but with markers at 4 and 16 instead of 8 and 12.
I did find the 12-marker, 18-line configuration PlannedChaos mentions, but wasn't sure it was unique.
I'm glad my life doesn't depend on solving these puzzles.

31. With all this “sixteen” talk, I might as well mention the fun fact that 16 is the only number that can be written both as x^y and y^x for x, y ∈ integers. (I leave the values of x and y as an exercise for the reader.)

1. Dear PC,

Take the natural log of both sides of your equation, and it is equivalent to [ln(x)]/x =
[ln(y)]/y. The function f(x) = [ln(x)]/x is zero at x = 1, increases monotonically to f = 1/e at x = e, and then decreases monotonically to zero as x becomes large. So for any real x between 1 and e there is a real y > e such that your equation is satisfied. The only integer between 1 and e is 2, and 2^4 = 4 ^2 = 16 is the only integer solution to your equation.

2. I assume the original statement should include that x is not equal to y.

32. Epiphany occurs on January 6' or 1/6. That is the day the puzzle was announced. "Sweet" is a reference to Sweet Sixteen.

33. This comment has been removed by a blog administrator.

34. Okay, forget my above post. I now realize I had to at least have periods in the empty cells.

The first two solutions I came up with:

╔═══╤═══╤═══╤═══╗
║ ■ │ . │ ■ │ . ║ All 4 rows, all 4 columns,
╟───┼───┼───┼───╢ both main diagonals,
║ . │ ■ │ ■ │ . ║ 2 of the 3-length diagonals,
╟───┼───┼───┼───╢ & 1 of the 2-length diagonals.
║ ■ │ ■ │ ■ │ ■ ║
╟───┼───┼───┼───╢ 13 total lines with either
║ . │ . │ ■ │ ■ ║ two or four markers.
╚═══╧═══╧═══╧═══╝

╔═══╤═══╤═══╤═══╗
║ ■ │ ■ │ . │ . ║ All 4 rows, all 4 columns,
╟───┼───┼───┼───╢ both main diagonals,
║ . │ ■ │ ■ │ . ║ 2 of the 3-length diagaonals,
╟───┼───┼───┼───╢ & 1 of the 2-length diagonals.
║ ■ │ ■ │ ■ │ ■ ║
╟───┼───┼───┼───╢ 13 total lines with either
║ . │ ■ │ . │ ■ ║ two or four markers.
╚═══╧═══╧═══╧═══╝

Then the solution I *thought* Blaine had:
╔═══╤═══╤═══╤═══╗
║ ■ │ ■ │ ■ │ . ║ 2 rows, all 4 columns,
╟───┼───┼───┼───╢ no main diagonals,
║ ■ │ . │ . │ ■ ║ 4 of the 3-length diagaonals,
╟───┼───┼───┼───╢ & 4 of the 2-length diagonals.
║ ■ │ . │ . │ ■ ║
╟───┼───┼───┼───╢ 14 total lines with either
║ ■ │ ■ │ ■ │ . ║ two or four markers.
╚═══╧═══╧═══╧═══╝

And now what I realize was the correct solution:
╔═══╤═══╤═══╤═══╗
║ ■ │ . │ ■ │ . ║ All 4 rows, All 4 columns,
╟───┼───┼───┼───╢ both main diagonals,
║ . │ . │ ■ │ ■ ║ 3 of the 3-length diagaonals,
╟───┼───┼───┼───╢ & 3 of the 2-length diagonals.
║ ■ │ ■ │ ■ │ ■ ║
╟───┼───┼───┼───╢ 16 total lines with either
║ . │ ■ │ ■ │ . ║ two or four markers.
╚═══╧═══╧═══╧═══╝

And the minimum:
╔═══╤═══╤═══╤═══╗
║ ■ │ ■ │ . │ ■ ║ No rows, no columns,
╟───┼───┼───┼───╢ no main diagonals,
║ ■ │ ■ │ ■ │ . ║ 0 of the 3-length diagaonals,
╟───┼───┼───┼───╢ & 1 of the 2-length diagonals.
║ . │ . │ . │ ■ ║
╟───┼───┼───┼───╢ 1 total line with either
║ ■ │ ■ │ . │ ■ ║ two or four markers.
╚═══╧═══╧═══╧═══╝

To make this post look better, select it all, open a new text document in EditPad (EditPad Lite will do), Select Convert, Text Encoding, and then select Unicode UTF-8. THEN you can paste the text and get the diagram.

35. If we’re going to present our solutions via text, may I suggest…

Maximum 16 out of 18:
☐⃟☐☐⃟☐
☐☐☐⃟☐⃟
☐⃟☐⃟☐⃟☐⃟
☐☐⃟☐⃟☐

Minimum one out of 18:
☐⃟☐⃟☐☐⃟
☐⃟☐⃟☐⃟☐
☐☐☐☐⃟
☐⃟☐⃟☐☐⃟

(Et cetera.)

1. Maybe this works best:

The maximum:
■ □ ■ □
□ □ ■ ■
■ ■ ■ ■
□ ■ ■ □

And the minimum:
■ ■ □ ■
■ ■ ■ □
□ □ □ ■
■ ■ □ ■

36. Blaine:
Your clue Taxman, by the Beatles, confirmed for me that I had the correct answer.

Taxman Lyrics:

1,2,3,4,1,2

Let me tell you how it will be,
There’s one for you, nineteen for me,
‘Cause I’m the Taxman,
Yeah, I’m the Taxman.
Should five per cent appear too small,
Be thankful I don’t take it all.
‘Cause I’m the Taxman,
Yeah, I’m the Taxman.

END

1,2,3,4,1,2 adds up to 13. I should have read the puzzle description more carefully. Obviously my fault I got it wrong, as you guys understood it alright. :-)

37. 8 is sweet. 8 markers in boxes 2,3,5,8,9,12,14,& 15 yields a sweet sixteen lines.

38. 1 1 1 0 | 1 0 0 1 Both for a total of 14 lines.
1 0 0 1 | 1 1 0 0
1 0 0 1 | 1 0 1 0
1 1 1 0 | 1 1 1 1

This was a temptation:

2 1 1 0 For a total of 17 lines.
1 0 0 1
1 0 0 1
0 1 1 0

1. There it is, Paul! Hugh put two cats in box one.
I only came up with 3 configuations of 14, so 8 markers to match the 16 lines is a major victory. I really should get out more.

39. New puzzle is up already! The FIRST TIME IN WEEKS it's been put up before 9:30pm PST!!

Comments, anyone?

1. Excuse me, folks, but am I the only one who posts here after the new puzzle is up, and then checks out this thread to see if anyone has left any clues?

2. Please accept my apologies. I hope my tardiness hasn’t driven you cuckoo.

40. Next week's challenge: Think of two familiar, unhyphenated, eight-letter words that contain the letters A, B, C, D, E and F, plus two others, in any order. What words are these?

The clues for this week’s puzzle are gonna be too easy, so instead I give you a secondary challenge: Take the four added letters, plus another, and rearrange to name a slang term for a man. Choose a different letter and rearrange to name a slang term for country folk.

1. Two observations about your secondary challenge:

1. The position#s of your extra letters in your respective 5-letter words are the same.

and

2. Measure the distance from your 1st added letter to one end of the alphabet, and it exactly equals the distance from your 2nd choice of added letter to the opposite end of the alphabet!

41. I am unsure if we have to find two words with the same eight letters, or if the added two letters can be different.

1. I believe the letters can be different.

2. Then I'm half way there.

3. Not only may the added two letters be different, but in one case one of the two added letters can be a repeat from the initial letter set of {A,B,C,D,E & F}.

4. If that is indeed true, then I solved this puzzle shortly after it was posted at 9:05 PM this evening West Coast Time.

42. Am I correct in assuming the added letters must be chosen from the last twenty letters of the alphabet? That's how I read the question.

1. Oh!! See the reply I just submitted above!

2. In that case, we're both all the way there....or maybe we're all only halfway there.

43. Has everyone who's posted here since 9pm PST when the new puzzle came up been able to solve PlannedChaos' secondary challenge?

Was anybody helped out by my hint?

1. To question #1: Couldn't say.
To question #2: Probably.

44. But nice confirmations.

In trying to solve Loyd's puzzle by trial and error I limited myself to combinations of 1 column of 4 marks and 3 columns of 2 marks, and wound up with 14 lines.
Yesterday, using the same limitation, I found that a spreadsheet of 432 lines did solve the puzzle - coming up with 2 of the winners.