HN Explorer

17 comments

[ 5.2 ms ] story [ 52.7 ms ] thread
extra__tofu 

   n=1, A=2:
   h    b   #tri  #non-congruent tri
   1    4   b-1   roundup(#tri/2)
   2    2   b-1   roundup(#tri/2)

   .
   .
   .
   
   n=4, A=16:
   h    b      #tri  #non-congruent tri
   1    2A/h   b-1   roundup(#tri/2)
   2    2A/h   b-1   roundup(#tri/2)
   4    ...    ...
   8    ...
   16   ...          ...
summing up #non-congruent tris for each n I see

   n  tri
   1  3
   2  7
   3  15
   4  31
so I think that answer may be 2^(n+1) - 1.

Could be wrong because I forgot what congruent really means.

tylerhou
You're undercounting some triangles and missing the acute condition. For n = 4, there is more than one triangle with base 4 and height 4, for example: [(0, 0), (4, 0), (1, 4)]; [(0, 0), (4, 0), (2, 4)]; (and [(0, 0), (4, 0), (3, 4)] but it's congruent to the first so we don't count it). Furthermore, a triangle with base 16 and height 1 might be non-acute.
[deleted]
(comment deleted)
dilatedmind
for the first 8 im getting 1,3,6,14,28,60,120,248
yantrams
Just a hunch but I think you might be skipping isosceles triangles. And possibly adding right angled triangles because of floating-point arithmetic.
dilatedmind
how about 3,6,14,28,60,120,248,496?
yantrams
Nope :( The sequence starts with 1 because there is just one triangle with an area of 2 that satisfies the conditions. I ended up with a sequence similar to your previous one when I forgot to take the absolute value of area -- x1(y2-y3) + x2(y3-y1) + x3*(y1-y2))/2 . That could be a possibility in case you were using the same formula. In your first result - 1, 3, 6, 14.... , first two are right, third over-counted and rest are undercounted.
yantrams
Close enough but wrong :) I went the same route as you did and realized my mistake after a while. Base and altitude values can be fractional/irrational too.

PS : I bruteforced my way to the answer.

[deleted]
(comment deleted)