Problem 091

[elr]

i wrote a program that successfuly computer the right answer for the example ( 0 <=x,y <=2),however
with the 50 limit i reciving a wrong answer,can someone tell me the number of right triangles for lets say x,y <= 9

(Link to problem added by moderator: Problem 91 (View Problem))

[stijn263]

Problem 91 (View Problem)

I get 353 for x,y [le] 9

[elr]

thanks,its seems i counted the triangles double times

[cnffi]

Any suggestions if my program gets the right answers for the examples stated in the problem (14 right triangles in x,y's <= 2) and for the post above (353 triangles for x,y's <= 9), yet gives me wrong answer for the problem requirement of x,y's <= 50? My number is 13826.

(I went ahead and checked the number on either side of mine, just in case, but that's not it either.)

[rayfil]

My number is 13826.

I would guess that you will have to work a bit more on your algo. That answer is definitely wrong.

And don't ask how far or close you are, nor if it's lower or higher.

[darkid]

I have a specific issue with this problem, namely their number of solutions for 2x2. Imagine the triangle which starts at the bottom left corner, touches the top side in the middle, and the left side in the middle, thus {1,2,2,1}. This is not listed in the possible solutions in the problem. Along these lines, the sets {1,2,2,2} and {2,2,1,2} are also not listed. Could someone enlighten me as to why?

[darkid]

Sorry, right angle. Sheesh.

[mdean]

Crud. Apparently, I'm missing some triangles. My calculations by hand comes up with 323 triangles for 9.

Okay, I think I see why if not how to fix it yet.

[mdean]

Okay, another problem down, but I had to resort to code. I couldn't think of a formula to count up all the triangles I missed. Just curious if anyone was able to do this with pen and paper.

[hk]

Okay, another problem down, but I had to resort to code.

Anything wrong with coding?

[mdean]

If I can simplify the problem, that's less the program has to do and the quicker it runs. And if I can boil it down to just a few calculations, why write a program to do what I could do on a calculator?

I've currently run into a similar dilemma with problem 145. I managed to boil it down to a simple sum of a few products, but my answer isn't being accepted. So I'm faced with either finding the flaw in my argument or just mindlessly brute forcing it. Starting to look like I'll be brute forcing it and seeing what I missed.

Update: Just finished the brute force program. The flaw wasn't in my argument, it was in my counting. Miscalculated the number of 7 digit reversible numbers. And the program took 3 minutes, not nearly fast enough.

Back to problem 91. In the topic for people who'd solved this problem, I thought I remembered people saying that they felt like there should be a simple formula that they just weren't able to find. Maybe I'll see if I can figure it out some time myself, but for now I'm probably going to stick with working problems I haven't found a solution for yet.

[hk]

I understand that analysing a problem as far as possible before starting to code is very useful.
However, there often is a large gap between: solving with pencil and paper and analysing as far as possible.

[mdean]

Yep. With a lot of problems, it's obviously not feasible to do it by hand. This one is less obvious.

[drwhat]

I think idea is well under answer, it was for 9. I don't actually enumerate every triangle. I thinking of all the possible triangles there could be.. Calculating the ones for which an easy formula was available, then using a program to enumerate the rest. If any solver is willing, I'd like to PM my list of what possible triangles, and see either a) I correctly covered all possible triangles and my code must be wrong, or b) My ideas miss some possible triangles. (though if its b I don't want to know which ones, just that I did so i can go back).

[Oliver1978]

I've tried it with pen & paper. I get 38 plus 14 from the description. That's a total of 52 for x <= x1,2;y1,2 <= 3. I don't want to post all the coordinates, but could someone confirm or waste my finding?

[Georg]

You should find less triangles.

[Oliver1978]

Well, this is my list. I've checked for duplicates and in a different order. The number even got bigger to 43...
(Only triangles with a 3-coordinate in it.)

Code: Select all

0,0 - 3,0 - 3,1
0,0 - 3,0 - 3,2
0,0 - 3,0 - 3,3
0,0 - 3,0 - 0,3
0,0 - 3,0 - 2,1
0,0 - 3,0 - 2,2
0,0 - 3,0 - 2,3
0,0 - 3,0 - 1,1
0,0 - 3,0 - 1,2
0,0 - 3,0 - 1,3

0,0 - 2,0 - 3,1
0,0 - 2,0 - 3,2
0,0 - 2,0 - 3,3
0,0 - 2,0 - 0,3
0,0 - 2,0 - 1,3
0,0 - 2,0 - 2,3

0,0 - 1,0 - 3,1
0,0 - 1,0 - 3,2
0,0 - 1,0 - 3,3
0,0 - 1,0 - 0,3
0,0 - 1,0 - 1,3
0,0 - 1,0 - 2,3

0,0 - 1,1 - 3,2
0,0 - 1,1 - 3,1
0,0 - 1,1 - 0,3
0,0 - 1,1 - 1,3
0,0 - 1,1 - 2,3

0,0 - 1,2 - 1,3
0,0 - 1,2 - 2,3
0,0 - 1,2 - 3,3
0,0 - 1,2 - 0,3
0,0 - 1,2 - 3,1
0,0 - 1,2 - 3,2

0,0 - 2,2 - 2,3
0,0 - 2,2 - 1,3
0,0 - 2,2 - 0,3
0,0 - 2,2 - 3,2
0,0 - 2,2 - 3,1

0,0 - 2,1 - 3,1
0,0 - 2,1 - 3,2
0,0 - 2,1 - 3,3
0,0 - 2,1 - 0,3
0,0 - 2,1 - 1,3
0,0 - 2,1 - 2,3

[Georg]

I don't think that all of
0,0 - 3,0 - 2,1
0,0 - 3,0 - 2,2
0,0 - 3,0 - 2,3
contain a right angle.

[Oliver1978]

Maybe I should skip this for tonight. I totally missed that right-angled point.

Danke für die Hilfe!

[Oliver1978]

[update]

I've re-counted the triangles with my pen-and-paper-technique and counted 8 with 3-coordinates. So for a square of the dimension 3x3 I get a total of 3 + 11 + 8 = 22 right-angled triangles. I hope I'm not too far off...