## Thursday, October 11, 2012

### NPR Sunday Puzzle (Oct 7, 2012): Hexagon Diagonals - Count the Triangles

NPR Sunday Puzzle (Oct 7, 2012): Hexagon Diagonals - Count the Triangles:

Q: Draw a regular hexagon, and connect every pair of vertices except one. The pair you don't connect are not on opposite sides of the hexagon, but along a shorter diagonal. How many triangles of any size are in this figure?
The diagram in the upper right should help. I've removed one diagonal. It looks like a cool cube, don't you think?

Edit: The words "cool cube" were a double hint. First, the diagram I drew reminded me of the isometric cubes in the Q*Bert video game which was released in 1982. Additionally, if you cube the answer (82^3) you get 551368. I think the result is cool because 55+13=68. As a final clue, in several of my comments, I used the word "lead" which happens to be 82 on the Periodic Table of Elements.
A: 82 Triangles - be sure to watch the video for an explanation of the answer.

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. So why the missing diagonal? Is this a line item veto?

1. At the end of last week's comments, you wrote: "Will someone go tell Jan she can now wake Blaine up from his stupor, whoops! I meant to say slumber, so he can clue us in on this new one?" And that was after AbqGuerrilla replied to RoRo with: "I hear dat, bro."

I know this is cyberspace, but let's get these pronouns straight: I'm a male, RoRo's a female.

2. Sorry Jan. I have also been pronouncing your name wrong too I will bet, unless you are a film actor who is now retired.

3. I believe I have now arrived at the correct answer, but have no idea how to give a clue that is not obvious.

1. Under 40???

2. benmar12001,
Dream on my friend, dream on.

4. I wonder how many people out there would agree with me that the number asked for in the puzzle can be expressed as the sum of two fourth powers?

And I wonder how many people out there would agree with me that if you add the line connecting vertix 2 with vertix 6 that the total number of new triangles added can be expressed as the sum of two cubes?

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

1. E&WAf - Are you sure you want to give this much of a hint? There are precious few such numbers that could possibly be the answer to this puzzle. (BTW,I hope your observation is wrong, because I really don't want to recount the triangles!)

2. E&WAf - Now I agree.

3. E&WAf, while the clue you provided may not lead directly to an answer, it does limit the possibilities and provides a clear way to check an answer. For that reason (and since we seem to agree on the actual answer) I have to delete your post.

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

5. E&WAf, I'd rather not get that specifc. First it might give somebody a clue directly to a triangle they missed. Additionally, it narrows the locations they might have to search to find a missing triangle.

As for the labeling, feel free to use the revised labeling you've come up with. My method of counting really doesn't rely on labeling the interior vertices, just the 6 on the outside, but I'll switch to letters if you like.

6. Yes, I'd like.

7. Done, I'm using letters on my outside vertices, matching with your diagram.

8. Also, I found it helpful to use the numbers 0 - 9 for the inside vertices.

9. At 2 this afternoon I read Blaine's post that he'd just posted above in this thread and it almost made me give up, but now I'm glad I didn't.

6. I haven't finished counting yet, but I think it's easier if you label the vertices with letters, rather than numbers, to avoid 2-character labels. The task is to count all the valid 3-tuples. I.e., if we replace Blaine's vertices 1-6 with A-F, and label the interior intersections G-P (starting, say, with the one nearest B, continuing clockwise, and ending with P at the center), the valid triangles are ABC, ABD, ABE, ABG, etc., but not ABF.

1. I've made a revised .png file where I've taken Blaine's diagram and replaced his labels and added new labels your way.

It can be accessed at http://users.az.com/~jwaters/Puzzles/2012-10-07_files/HexagonDiagonals_Jans.png

2. Jan:
Good advice, but I felt I needed a more stimulating challenge, which is why I labeled all mine with Roman Numerals.

3. I tried that, SkyDiver. Still not stimulating enough. So I connected the vertices with little cattle prods. Worked like a charm!

4. Careful there, GBoy. I'm an old frustrated cowboy and I long for the old days when a roundup was still called a roundup and not a steering committee.

5. That's a great one, SDB. The first time I heard Garrison Keillor deliver that line, I laughed so damn hard, I nearly kicked the slats out of my baby crib!

6. AbqGuerrilla:
Now you won't believe me when I tell you I came up with that joke myself years ago. I have never heard (no pun intended) it used by anyone else, but am not at all surprised as it is a formula joke. I have not used it that much, but when I have no one seems to have heard it by the way they laugh.

As to Privy Home Companion, GK uses old jokes in his monologue frequently. I seem to recall that I even sent this joke to him a few years back, along with a few others I coined. I have not heard him use any though, but I usually don't listen to his show.

Reminds me of in incident about 2 1/2 years ago when I told three jokes I made up myself to a few people visiting Seattle. After the last one, my Eliot Spitzer joke, I mentioned that I make up my own jokes, to which an older woman from New York indignantly said she had heard that same joke from a New York cabbie. I said, "Did you really?" to which she, again indignantly, replied, "Yes!" I then said, "Well, you just made my day!" This was not a formula joke and was not easy to make. I told it to many New Yorkers and none had heard it before, but all loved it and several insisted I tell it to their partner, spous, boss, etc. later. One guy remembered it a year later when he returned to Seattle and asked me to tell his colleague. I am not surprised that it got around that way, but am surprised I have never heard any of my other well received jokes come back at me. Humor is a funny business.

7. SDB: I totally get it. I write humor as well. Aside from the "polygamist in Provo" fun stuff, I am actually a public radio host and prefer/need to remain anonymous. Since I use a lot of my gag lines on the air, they get "lifted/borrowed" quite a bit, and I too, am flattered by the validation when that happens. And of course, from time to time, I have been known to borrow a line here and there (I'll be using your "steering committee" gag line on next week's show -- but I am fairly sure GK used it in one of his dusty cowboy bits last year. Unlike, GK, I will give you contributor credit at the end of the show. Seriously. And, just for the record, I enjoy our banter and hope the feeling is mutual. OK, enough of the sweet talk. It's much more fun to cross pens with you!

8. AbqGuerrilla:
Thanks Rush. Maybe GK did decide to use it. I had looked via a search in my email to see if I had sent it that way, but no emails to him with that joke came up. I also sent him jokes via the NPR website, so that may be it. I sent it because I thought it would be perfect for Dusty and Left Knee to use.

I am really down on Garrison K. though, to tell the truth. After many years in therapy, and finally beginning to feel adequate, along comes GK to inform me that I'm so lacking in whatever it takes to be a real human that I don't even know my sleep number. Can you feel my pain?

Here is one I sent that I thought would be perfect for his show:

The major difference between George W. Bush and Bill Clinton is that Bush confers frequently with his generals, whereas Clinton paid more attention to his privates.

Now, getting back to your email. "Banter?" What banter? I did not have banter with that poster!

:)

9. The biggest laugh in your posting was actually the "Thanks Rush" intro. Had you ever caught my program on the airwaves...or perhaps I should say, if any of my listeners knew that someone addressed me as "Rush," well, let's just say they would find that very amusing to say the least.

10. Yes, I thought you might enjoy that and not Rush to judgment.

7. Thanks for the great graphic Blaine! Something tells me that we are going to get a great video, much like we did with the equilateral triangle/ quarter puzzle - http://vimeo.com/31789167

Until then, I may just wait this one out!

1. Indeed, I was again inspired to make a "count the triangles" video for this.

8. Please ignore my comment posted last night about the answer being a prime number. It isn't. Didn't mean to lead anyone astray.

9. This ol' right-brained farmer doesn't appreciate the math/geometry puzzles so much. Think I'll just finish harvesting my crop circles before the alien hex takes effect. Then I'll immerse myself in my little love triangle 'til next week. I have no doubt that a few retired computer squares from the Pentagon will come up with a program to figure this one out. Meanwhile, please forgive my obtuse posting. I was unable to think of acute one. Not only have I failed at reaching the apex of the math puzzle world, but I fear I have fallen short of scalene any great literary heights as well.

1. The Eskimos have an old saying:
If it gets any colder we'll all be number.

2. Yes, and it has been so cold here in Provo this week that our local exhibitionist has just been standing on the corner describing himself.

10. One belated note about last week’s puzzle – only 55 people sent in the correct answer. That’s the smallest number of answers I ever remember. The funny part is that a not insignificant chunk of them are from this very blog :) We now continue with our regularly scheduled programming...

Chuck

1. Yeah, and did everyone catch Will's error when he casually dismissed DREARY/DREAMY as a correct response? He said that that transformation didn't require anagramming, but that's not true: the puzzle said to change the *2ND* letter from R to M, and if you do that do DREARY, you certainly do have to rearrange to get DREAMY.

2. Are we all going to sit here and let Will get away with not accepting DREARY & DREAMY?
Following his stated question there is no way to arrive at this answer without anagraming the result of replacing the R with an M. I resent it when someone makes up the rules after the game has ended.

3. I'm not sure Jan(however it's pronounced) and sdb correctly interpreted 'the funny thing', but I wonder if Mr.(I can only hope it's not Ms.) Duncan is chuckling about now.

That being said, if all or any of you want to 'Occupy Pleasantville', let me know, I might just be up for that.

Oh yeah, at the moment, I think Lorenzo and E&WAf are both wrong, but I'll keep counting, slowly..slowly, getting faster....when I start to counting, it's rreally hard to stop(unless, of course, someone pulls the plug on my Federal Funding, in which case, I'm screwed).

4. I agree with Jan, SDB, et al about Will's dismissing of DREARY and DREAMY; but what really pisses me off is he says the ONLY answer he accepted was his PROSE & POEMS.

He didn't even mention BROODLESS and BLOSSOMED, and who would deny that they're a much better pair of opposites than PROSE and POEMS?

5. Paul - I infer from your comment that your number is less than the one E&WAF, Blaine and I are referring to.

6. I've been going over it again and I think Paul may be correct and some others wrong, including my original conclusion.

7. I think that WA&Ef's test calculation (deleted) may be correct if you consider that zero to the fourth power is zero. Is that so WA&Ef?

8. Jim - It's true that 0^4 = 0, but I didn't have that in mind when I agreed with WA&Ef's (deleted) comment.

9. Jim - Lorenzo, Blaine & I agree that you, Paul, and SDB are just ONE triangle short. Count 'em again!

10. To Enya, etc.:
I must be missing something else because I had no trouble at all locating the triangle you refer to. Or perhaps you guys are over counting.

11. I nave a new triangle count. So now I am going to commence counting sheep!

12. Life is now back to normal. A very quick glance at a diagram of the puzzle while I was doing something else quickly solved everything for me. I made a very stupid error when I first began working on the puzzle yesterday and never went back to double check on this one part. I am now laughing at myself big time. So, we are now in complete agreement (you in the we group all know who you are) and I am sending in my answer.

I will wait until the deadline to reveal my goofy error so as not to give anything away to those who have yet to solve this puzzle.

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

1. Please save it for after the deadline. I appreciate the obfuscation, but if someone wanted to brute force it, there are a finite number of keys they'd have to try.

14. How is the E-C Line different from the F-B line? I thought Will's explanation was rather confusing. I don't know which line to omit. I sent in "Prose & Poems", along with "Dreary and Dreamy." Do you think he disqualified me for sending both? Only 55 right out of 145 submissions! I've never heard such a low number!

1. Any short diagonal (where the endpoints are two apart) would be fine. He's just trying to make sure you don't pick a bisecting diagonal (e.g. AD, BE or CF)

2. Thank you so much for clarifying that!

15. There is some helpful literature on this problem for the case
when all the diagonals are included. After I read the article
I was able to solve the puzzle as stated, and be confident that I have the correct answer. But I spent a fair amount of
time on it, and regard the problem as non-trivial.

16. I have a confession to make: I’m not very good at solving puzzles of this kind. However, after spending far too much of my time these last two days calculating the answer, I finally made my decision tonight and submitted my answer. I have about a 20% confidence level in the result but there it is – I must get on with my life. I assure everyone that I will _not_ be the first poster after the deadline this week :)

Chuck

17. Amazingly, this week’s puzzle was still on my mind when I awoke this morning and I realized without even getting out of bed that the number I sent in yesterday was wrong :( So I guess I won’t be a famous media star this week...

Chuck

18. Blaine used a word in his initial comment which I took to be a reasonable clue. My count is 10 greater than the number I inferred. Count and inference may be wrong, but i'll stick with them.

1. I saw that clue, too. The number I counted was slightly lower than the number I inferred from that clue. Based on this puzzle, and others like it, I believe counting is an ineffective way to solve such problems. As a non-mathmatician, I'd love to see the methodology others used in arriving at their answers (after the deadline, naturally).

Assuming the answer I submitted is correct, I'll refrain from some musical clues that come to mind, because they would be way to easy to Google.

19. The first answer I submitted, which I was sure was correct, was in fact wrong. I will post a discussion of the correct answer, with references,
tomorrow afternoon. I did submit my revised answer
with a note admitting it was a second try.

20. Just out of curiosity, I decided to count the triangles lost by removing that short diagonal, and using that number to check my answer against the published total of triangles when all diagonals are present. Drat! I missed a complete set of 8 right triangles.

1. Sdb and Abq - will you guys just get a room. What drivel - you are clogging Blaines website.

2. My Dear Unknown:
Thank you again for your warm and thoughtful post. You always have something interesting to say when you infrequently post, but don't stop now as we love your fine prose. Oh, and please do let us know when your next book comes out.

3. Unknown: We ain't cloggin', bruddah. We be bloggin!

Hey, SDB: Whaddya say? We could go Dutch this Saturday night. I know a place where checkout time is not until noon, so we could listen to the Puzzle Man over continental b'fast. I'll even take the foldout couch.

4. P.S. Can someone please sell Unknown an apostrophe for his last posting. I'm overly possessive and I used all mine.

5. AbqGkuerrilla:
And you didn't notice Unknown neglected to use a question mark at the end of his sentence? Yeah, like that one.

I don't know about the hook-up; my harem is upset with me for using their names as points on the hexagon puzzle and a few were left over and not recognized. Anyway it was a disaster of confusion and put a hex on my attempt to solve it that way.

6. I hava a P.S. too!
AbqGuerrilla, don't pay her too much mind, she's just a camp follower who sometimes gets her panties in a bunch over long posts. Maybe she just needs a long post to set her right.

21. The answer is 91 triangles. Of these, 16 have all three vertices at a vertex of the hexagon ("three diagonal endpoints") , 50 have one vertex inside the hexagon and two vertices at vertices of the hexagon ("four diagonal endpoints"), and 25 have two vertices inside the the hexagon and one vertex at a vertex of the hexagon ("five diagonal endpoints"). See Journal of Integer Sequences, Vol. 1 (1998), Article 98.1.5, The Number of Triangles Formed by Intersecting Diagonals of a Regular Polygon, by Sommars and Sommars. This paper shows that if all the diagonals are included there are 110 triangles formed (20, 60 and 30 of the above types). Removing one short interior diagonal of the hexagon removes 19 triangles, and leaves 91.

1. I agree on the 110 triangles in a fully filled hexagon (based on the following Waterloo Journal Article. There seems to be a discrepancy of 9 triangles in your count, so either you double-counted when adding triangles, or undercounted when counting triangles using the removed diagonal. It will be interesting to find out.

22. EIGHTY-TWO (82)

16 triangles of one
23 triangles of two shapes
10 triangles of three shapes
14 triangles of four shapes
6 triangles of five shapes
6 triangles of six shapes
2 triangles of seven shapes
4 triangles of eight shapes
1 triangle of 10 shapes
__
82 Total Triangles

My Hint:
"At 2 this afternoon I read Blaine's post that he'd just posted above in this thread and it almost made me give up, but now I'm glad I didn't."

At 2 = 82 phonetically.

My initial mistake with this puzzle was being hasty with counting the single triangles. I ended up counting 4 nonexistent triangles. What I did was to quickly count all the single enclosures thinking all of them were triangles and failing to notice that four had 4 sides. I was very careful with all the more complex triangles and even noticed the large one made up of ten smaller shapes. Later I happened to glance at the diagram and I realized my error. I wonder how many others made this same mistake.

23. Answer = 82 triangles:
A video explanation is now online and no longer password protected.

1. Good video. For demonstration purposes, there's any number of ways to sort the triangles; in the end, I chose to go with the (frenetic from a geometric perspective) ordering that results from an alphabetic sorting. But in practice, I counted the triangles by exhaustively listing all (14 choose 3) = 364 possible combinations of line segments AB, AC, … , EF, and then ruling out the degenerate cases. I also employed a few other sorting techniques as a check to make sure I hadn't missed any.

2. My first observation was that all triangles used at least one of the outside vertices. Picking 3, 4 or 5 vertices ends up enumerating all the cases and provides some logical grouping, I felt. But I also did what you did and went back and did an exhaustive listing.

3. I too wish to compliment your video.

I do have one suggestion. It's about how you name your 5-vertices star figures.

Instead of naming them ABCDF, ABCEF, ABDEF
and ABCDE, ACDEF, BCDEF; I would name them with the letters arranged in the order in which connecting lines would draw the figures.

Thus: ACFBD, ACFBE, ADFBE
and: ACEBD, ADFCE, BDFCE

I've tried to arrange my suggested names to exactly correspond to your listing.

4. I just realized...

since BF is removed, the drawing instructions in those cases should from start at one end of the disconnected line and end at the other end.

So replace ACFBD with BDACF, and ACFBE becomes BEACF, and lastly ADFBE becomes BEADF.

24. Clues explained: My comment: "Didn't mean to lead anyone astray" contained the metal whose atomic number is 82. (Similarly, my use of the word "precious" in an earlier post referred to my initial (incorrect) count of 79.)

25. 82 Total
Subtotals of sets in order of type and size from large to small:
10 Equilateral, 1, 6, 3
18 Isosceles, 4, 10, 4
54 Right, 10, 8, 8, 20, 8

My wrong hint:
Blaine used the word "cube". 4³ + 10 = 74. (off by 8)

The set of triangles I failed to see were the ones using 2 segments of the short diagonals as a hypotenuse.

26. Perhaps the best way to count is to first ignore the exception and count ALL, then count the triangles REMOVED as the exception applies.

Observation: Any triangle with all 3 of its vertices interior would require all 6 vertices of the hexagon; but that would result in the 3 opposing lines all crossing at the center, thus...

Any triangle can be described by either (1) initial vertix, vertix traveled to, 3rd vertix traveled to, and 4th vertix traveled to (possibly crossing 1st line),
or (2) vertix angle, defined by first 3 vertices above and a line crossing BOTH lines to and from the angle vertix.

Without loss of generality, let's move clockwise.

From ANY vertix:

1. Move 1, move 1, then ONLY possible triangle result ==> move 4, no double-cross triangles
2. Move 1, move 2, then ONLY possible triangle result ==> move 3, no double-cross triangles
3. Move 1, move 3, then ONLY possible triangle result ==> move 2, no double-cross triangles
4. Move 1, move 4, then ONLY possible triangle result ==> move 1, no double-cross triangles
5. Move 2, move 1, then TWO possible triangle results ==> move 3 OR move 4, no double-cross triangles
6. Move 2, move 2, then TWO possible triangle results ==> move 2 OR move 3, one double-cross triangle for 2 of the 3 vertices plus another double-cross for the would've-been triangle.
7. Move 2, move 3, then TWO possible triangle results ==> move 1 OR move 2, two double-crosses for each counted vertix, but one vertix lacks 1 of these counted double-crosses.
8. Move 3, move 1, then THREE possible triangle results ==> move 2, move 3, or move 4, no double-cross triangles
9. Move 3, move 2, then THREE possible triangle results ==> move 1, move 2, or move 3, double-cross count same as #7 above.
10. Move 4, move 1, then FOUR possible triangle results ==> move 1, move 2, move 3 or move 4, no double-cross triangles

(to be continued)

27. In all 10 possiblities, only the first option could've been begun by either of the three involved vertices.
So we may throw out possibility #4 (just a repeat of #1), as well as all first options for #5 and #s 7-10.
Every possibility with only a single "move 2" or a single "move 4" needs only to deduct 1 from the possible starting vertices.
Every possibility with two "move 2"'s or a "move 2" and a "move 4" or two "move 4"'s needs to deduct 2 from their possible starting vertices.
The first of possibility #6's options has a count of exactly 1.
The count of double-cross triangles in #6 can be explained as the top 3 little triangles of the would've-been Star of David within the hexagon but for the removed line.
I count triangles for the puzzle as stated, and also for the hexagon WITH the removed line.
I consider the hexagon oriented with single top and bottom vertices and the removed line joining the bottom's neighbors.
In the second column, I keep tallies of added triangles above and below the removed line.

So: Puzzle as stated:
5. adds 4 (a "move 2" AND a "move 4")
6. adds 1 & 4 (two "move 2"'s), then adds 3, so adds 8
7. adds 4 (two "move 2"'s), then adds (10-1 = 9), so adds 13
8. adds 6 & 5 (the "move 4"), so adds 11
9. adds 4 & 5, then also adds 9, so adds 18
10. adds 4, 5 & 4, so adds 13

So I come up with 82.
Without that removed line:
1. adds 6 (+ 1 lower)
2. adds 6 (+ 1 upper)
3. adds 6 (+ 1 upper)
5. adds 6 (+ 1 upper & + 1 lower)
6. adds 2 & 6, then adds 2*3, so adds 14 (1^ & 2^, then 2^+1v, so + 5 upper + 1 lower)
7. adds 6, then adds 2*6, so adds 18 (2^, then 2^+1v, so + 4 upper + 1 lower)
8. adds 6 & 6, so adds 12 (+ 1 lower)
9. adds 6 & 6, then also adds 12, so adds 24 (2^ & 1^, then 2^+1v, so + 5 upper + 1 lower)
10. adds 6, 6 & 6, so adds 18 (1^+1v, 1v & 2v, so + 1 upper + 4 lower)

Total here would be 110. (+ 18 upper + 10 lower)

28. I got the same list. Using the alpha labels, and keeping the triangle names alphabetically sorted helped avoid miscounting, I found.

29. Ok, this certainly isn't the classiest or most professional html file, but it displays the above mentioned diagram and then gives my list in a much better format.

http://users.az.com/~jwaters/Puzzles/2012-10-07.htm

Enjoy, everybody.

30. My only comment on this puzzle is a question: how many people submitted the correct answer? I say fewer than 50.

31. I think it will be many more than that. This puzzle really wasn't tricky; it was completely solvable by brute force, and counting to 82 isn't all that hard. You just needed a lack of anything better to do with your life this week.

32. After perhaps the earliest update of the NPR Weekend Sunday Puzzle page last week, this week we get another very late update. The NPR website had still not yet been updated as I was typing this.

1. It is up now and I solved it as I read the question. I am going back to bed though and will leave you all waiting until I get up in the morning for a clue, so please remain calm until then.

2. I've submitted an answer. I believe I figured out the property, but I had to admit that my 6th word was unknown.

33. This comment has been removed by the author.

For NPR puzzle posts, don't post the answer or any hints that could lead to the answer before the deadline (usually Thursday at 3pm ET). If you know the answer, 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 assist with solving. You can openly discuss your hints and the answer after the deadline. Thank you.