Noncongruent isosceles triangles... - October 1994

Winning Solution

Students: Jovan Milosevic, Daniel Kim, Felix Chang

School: Burnaby South Secondary High School
Address: 5455 Rumble Street, Burnaby, BC, Canada.
Teacher: Mr. Swift

OUTPUT FOR A 11X11 CHECKER BOARD (36 triangles)

THE SIDES GIVEN BELOW NEED TO BE SQUARED ROOTED FOR CORRECT 
ANSWER.
THE POINTS GIVEN BELOW ARE ONLY ONE EXAMPLE OF EACH TRIANGLE.

TRIANGLE #   1 SIDES :   5   5  10 THE POINTS : (0,0)  (1,2)  (3,1)
TRIANGLE #   2 SIDES :  10  10  20 THE POINTS : (0,0)  (1,3)  (4,2)
TRIANGLE #   3 SIDES :  10  25  25 THE POINTS : (0,0)  (0,5)  (3,1)
TRIANGLE #   4 SIDES :  10  65  65 THE POINTS : (0,0)  (1,8)  (4,7)
TRIANGLE #   5 SIDES :  13  13  26 THE POINTS : (0,0)  (1,5)  (3,2)
TRIANGLE #   6 SIDES :  17  17  34 THE POINTS : (0,0)  (1,4)  (5,3)
TRIANGLE #   7 SIDES :  20  20  40 THE POINTS : (0,0)  (2,4)  (6,2)
TRIANGLE #   8 SIDES :  20  25  25 THE POINTS : (0,0)  (0,5)  (4,2)
TRIANGLE #   9 SIDES :  20  50  50 THE POINTS : (0,0)  (1,7)  (5,5)
TRIANGLE #  10 SIDES :  20  85  85 THE POINTS : (0,0)  (2,9)  (6,7)
TRIANGLE #  11 SIDES :  25  25  50 THE POINTS : (0,0)  (1,7)  (4,3)
TRIANGLE #  12 SIDES :  25  25  80 THE POINTS : (0,0)  (0,5)  (4,8)
TRIANGLE #  13 SIDES :  25  25  90 THE POINTS : (0,0)  (0,5)  (3,9)
TRIANGLE #  14 SIDES :  26  26  52 THE POINTS : (0,0)  (1,5)  (6,4)
TRIANGLE #  15 SIDES :  26  65  65 THE POINTS : (0,0)  (1,5)  (8,1)
TRIANGLE #  16 SIDES :  29  29  58 THE POINTS : (0,0)  (2,5)  (7,3)
TRIANGLE #  17 SIDES :  34  34  68 THE POINTS : (0,0)  (2,8)  (5,3)
TRIANGLE #  18 SIDES :  34  85  85 THE POINTS : (0,0)  (2,9)  (7,6)
TRIANGLE #  19 SIDES :  37  37  74 THE POINTS : (0,0)  (1,6)  (7,5)
TRIANGLE #  20 SIDES :  40  40  80 THE POINTS : (0,0)  (2,6)  (8,4)
TRIANGLE #  21 SIDES :  40  50  50 THE POINTS : (0,0)  (1,7)  (6,2)
TRIANGLE #  22 SIDES :  40 100 100 THE POINTS : (0,0)  (0,10) (6,2)
TRIANGLE #  23 SIDES :  41  41  82 THE POINTS : (0,0)  (1,9)  (5,4)
TRIANGLE #  24 SIDES :  45  45  90 THE POINTS : (0,0)  (3,6)  (9,3)
TRIANGLE #  25 SIDES :  50  50 100 THE POINTS : (0,0)  (1,7)  (8,6)
TRIANGLE #  26 SIDES :  52  52 104 THE POINTS : (0,0)  (2,10) (6,4)
TRIANGLE #  27 SIDES :  52  65  65 THE POINTS : (0,0)  (1,8)  (7,4)
TRIANGLE #  28 SIDES :  53  53 106 THE POINTS : (0,0)  (2,7)  (9,5)
TRIANGLE #  29 SIDES :  58  58 116 THE POINTS : (0,0)  (3,7)  (10,4)
TRIANGLE #  30 SIDES :  65  65  80 THE POINTS : (0,0)  (1,8)  (8,4)
TRIANGLE #  31 SIDES :  65  65 130 THE POINTS : (0,0)  (1,8)  (9,7)
TRIANGLE #  32 SIDES :  68  68 136 THE POINTS : (0,0)  (2,8)  (10,6)
TRIANGLE #  33 SIDES :  68  85  85 THE POINTS : (0,0)  (2,8)  (9,2)
TRIANGLE #  34 SIDES :  80 100 100 THE POINTS : (0,0)  (0,10) (8,4)
TRIANGLE #  35 SIDES :  82  82 164 THE POINTS : (0,0)  (1,9)  (10,8)
TRIANGLE #  36 SIDES :  85  85  90 THE POINTS : (0,0)  (2,9)  (9,3)

PROOF

a. Possible Slopes

        First of all, assume m = slope of the axis of symmetry.
        That tells us that 0 < m < 1 (since it can't be 0, it can't be
        1, and anything beyond one, the triangle can be flipped; and
        anything negative, the triangle can also be flipped.)

        The slope of the third side (the non-equal side) must be -1 / m.

        Suppose we place the first point of the triangle at (0,0)

        Then in order to let the other two points fall on valid points,
        (integral coordinate), the slope must be able to be expressed
        in the form of a/b (where a and b are integers, and a & b can not 
        be factored.)

        Therefore, we limit the possible slopes of axis of symmetry to:
        (anything beyond, like 31/32, will definitely have the end points 
        outside the 11x11 board)

        1/2, 1/3, 1/4, 1/5, 1/6, 1/7, 1/8, 1/9
        2/3, 2/5, 2/7, 2/9, 3/4, 3/5, 3/7, 3/8...
        All the way up to 8/9.

b. Possible Points

        Here, we discuss using only slope=1/3; all other slopes
        can be discussed in the same procedures.

        Here, the slope of axis of symmetry is 1/3.
        So the slope of the third line must be -3.
        So, in order to let the points fall on the valid points,
        the mininum possible length of the third line is root of 10.
        And all the other possible lengths are multiples of that:

        X=root of 10,  the possible lengths are x, 2x, 3x, 4x...

        So for the slope 1/3, we first get a grid paper, and plotted
        (0,0) as one of the point. Then we draw a line through (0,0)
        with a slope of 1/3.

        First, on the line, we find point (3,1), (6,2), (9,3)...
        These are one set of possible point of intersection
        between the axis of symmetry and the third side.

        But they are not all, we divide the line segment in half to
        get the rest; that is because for (0,0)-(3,1), the third side
        is 2 times the minimum length; therefore, at half, it will be
        the minimum length.

        The only problem with half point is: will the two end points fall 
        on valid coordinates? The answer is: only for a/b where a and b
        are both non-factorable with each other, and are both odd numbers. 

        The proof is simple. Since a/b is simplest form, cutting it in half, 
        the coordinate will fall between the grid both vertically and 
        horizontally, if and only if, both a and b are odd numbers.
        Now, to achieve the minimum length, that means both upward and
        downward has to have 1/2 the minimum length; so both way, the
        displacement will have .5 more horizontal and .5 more vertically
        beyond the grid scale. So 1/2 + 1/2 = 1, so the end point fall
        exactly on the grid line.

        Therefore, we prove that for 1/3, simplest fraction, the points
        are (3,1), (6,2)..., and since both 1 and 3 are odd numbers,
        we also have (1.5, 0.5), (4.5, 1.5)...

        For every one of them, draw a line thru them with a slope of -3.
        And this line will intersect the grid at (1,2)-(2,-1), (0,5)-(3,-4) 
        .., and each of these corresponding set will be the two points other 
        than (0,0)

        So for slope 1/3, we find a sequence of possible third side,
        and from that, we find a sequence of possible 2nd and 3rd points. 
        Now, all we have to do is to eliminate those triangles that
        are too big to fit into 11x11 grid.

        And we can have every single possible triangle that has an axis
        of symmetry slope = 1/3.

c. Getting All Of Them

        Now, since we have the list of all possible slopes,
        and for each, we can get all possible triangles.
        Then we can get all the possible triangles.

        To ensure that we get them all, we program the computer
        (in QBasic from MS-DOS 5.0) to automatically check for
        all possibilities.

        In this program, in order to reduce the number of testing
        from 11^6 to 11^4, an important proof is needed.

d. Prove that anything triangle (isosclese or not), can always be 
flipped and shifted, to have one point (0,0), and the other points also
inside the 11X11 board:

        First of all, for any triangle, it must contain three points.
        Let's call them A, B, and C.

        Let's sort A B C so that Ax<=Bx, and Ax<=Cx, and Bx<=Cx.

        So now, let's find the point with lowest Y.
        If it's point B, then we look at the highest Y.
        One of the point must be lowest/highest Y, and most left/right X. 

        Now, we can always flip this triangle horizontally and vertically 
        to get this point on bottom left. So we can shift this triangle
        to the point (0,0). Since it's the bottom most and left most,
        the other two points MUST fall within this board.

        Proof is done.

Since I limit one point to (0,0), I only have to check 11^4 times. 
On my IBM-PC 386 SX, it took me about one hour to test through all 
results; totally there are 36 triangles (non-congruent). The list 
matches the total triangles we found by slope elimination.

e. Listing of the program (using QBasic from MS-DOS Version 5)

'
' MATH SOLVE PUZZLE #1
'
' QUESTION COMES FROM: pow@forum.swarthmore.edu (problem of the week)
' COMPUTER PROGRAMMER: FELIX SHENG-HO CHANG
'
' ON AN 11 BY 11 GEOBOARD, FIND ALL NON-CONGRUENT, ISOSCELES 
TRIANGLES
' WHOSE AXIS OF SYMMETRY IS NEITHER HORIZONTAL, NOR VERTICAL, 
NOR AT
' A 45 DEGREE ANGLE FROM HORIZONTAL. STATE YOUR SOLUTION BY 
GIVING THE
' LENGTH OF THE SIDES OF THE TRIANGLES YOU FIND. WHAT TECHNIQUES 
DID YOU
' USE TO FIND THE ANSWERS?
'

CONST MAXX = 10      'since it starts from zero to 10.
CONST MAXY = 10      'since it starts from zero to 10.

CONST MAXENTRY = 100
CONST OVERFLOW = 150
SCREEN 8
DEFINT A-Z

DIM SHARED ALLDATA(1 TO MAXENTRY) AS STRING
DIM SHARED ALLDATAS(1 TO MAXENTRY) AS STRING
DIM SHARED ALLDATANOW AS INTEGER

CLS
LINE (0, 30)-(330, 195), 0, BF
FOR P = 0 TO MAXX: LINE (P * 30, 30)-(P * 30, MAXY * 15 + 30): NEXT
FOR P = 0 TO MAXY: LINE (0, P * 15 + 30)-(MAXX * 30, P * 15 + 30): NEXT

ALLDATANOW = 0
RESMUCH& = 0  ' THREE SIDES ALL THE SAME

RESCORE& = 0  ' EXACTLY TWO SAME SIDES. TOTAL COUNT.
RESREGU& = 0  ' EXACTLY TWO SAME SIDES. VER/HOR/45 AXIS OF 
SYMMETRY.
RESCORR& = 0  ' EXACTLY TWO SAME SIDES. NON REGULAR AXIS. TOTAL 
COUNT.
RESYEAH& = 0  ' EXACTLY TWO SAME SIDES. NON REGULAR AXIS. NO 
REPEAT.

FOR P1X = 0 TO 0: FOR P1Y = 0 TO 0
FOR P2X = 0 TO MAXX: FOR P2Y = 0 TO MAXY
FOR P3X = 0 TO MAXX: FOR P3Y = 0 TO MAXY
LOCATE 1, 1: PRINT "("; P1X; ","; P1Y; ")"; " ("; P2X; ","; P2Y; ")"; " 
("; P3X; ","; P3Y; ")"; SPACE$(10); 
LOCATE 2, 1: PRINT "ALL :"; RESCORE&; " REG :"; RESREGU&; " NON-REG :"; 
RESCORR&; " Non-Repeat :"; RESYEAH&; SPACE$(20); 
KX1 = P1X - P2X: KY1 = P1Y - P2Y: K1 = KX1 ^ 2 + KY1 ^ 2
KX2 = P2X - P3X: KY2 = P2Y - P3Y: K2 = KX2 ^ 2 + KY2 ^ 2
KX3 = P1X - P3X: KY3 = P1Y - P3Y: K3 = KX3 ^ 2 + KY3 ^ 2

'RULE OUT EQUAL POINTS...
 IF P1X = P2X AND P1Y = P2Y THEN GOTO TRY
 IF P2X = P3X AND P2Y = P3Y THEN GOTO TRY
 IF P1X = P3X AND P1Y = P3Y THEN GOTO TRY

'RULE OUT EQUAL SLOPES (THAT IS, AREA OF TRIANGLE = 0)
 IF KY1 * KX2 = KX1 * KY2 THEN GOTO TRY
 IF KY1 * KX3 = KX1 * KY3 THEN GOTO TRY
 IF KY3 * KX2 = KX3 * KY2 THEN GOTO TRY

'RULE OUT ALL THREE EQUAL SIDES
 IF K1 = K2 AND K2 = K3 THEN RESMUCH& = RESMUCH& + 1: GOTO TRY

'RULE OUT TRIANGLES THAT HAVE NO EQUAL SIDES
 IF K1 <> K2 AND K2 <> K3 AND K1 <> K3 THEN GOTO TRY

'DETERMINE WHETHER IT'S VER/HOR/45 (K=4) OR NOT (K=1)
IF K1 = K2 THEN Z1X = P2X * 2: Z1Y = P2Y * 2: Z2X = P1X + P3X: Z2Y = P1Y
+ P3Y 
IF K2 = K3 THEN Z1X = P3X * 2: Z1Y = P3Y * 2: Z2X = P1X + P2X: Z2Y = P1Y
+ P2Y 
IF K1 = K3 THEN Z1X = P1X * 2: Z1Y = P1Y * 2: Z2X = P2X + P3X: Z2Y = P2Y
+ P3Y 
IF Z1Y = Z2Y OR Z1X = Z2X OR ABS(Z1X - Z2X) = ABS(Z1Y - Z2Y) THEN K = 4 
ELSE K = 1 
 RESCORE& = RESCORE& + 1

 IF K = 4 THEN RESREGU& = RESREGU& + 1: GOTO TRY

'DRAW IT
 LINE (0, 30)-(330, 195), 0, BF
 FOR P = 0 TO MAXX: LINE (P * 30, 30)-(P * 30, MAXY * 15 + 30): NEXT
 FOR P = 0 TO MAXY: LINE (0, P * 15 + 30)-(MAXX * 30, P * 15 + 30): NEXT
 LINE (P1X * 30, P1Y * 15 + 30)-(P2X * 30, P2Y * 15 + 30), K
 LINE (P2X * 30, P2Y * 15 + 30)-(P3X * 30, P3Y * 15 + 30), K
 LINE (P1X * 30, P1Y * 15 + 30)-(P3X * 30, P3Y * 15 + 30), K

 PLAY "L64D"
 RESCORR& = RESCORR& + 1
 IF K3 >= K2 AND K3 >= K1 THEN
   PK1 = K3
   IF K2 >= K1 THEN PK2 = K2: PK3 = K1
   IF K1 >= K2 THEN PK2 = K1: PK3 = K2
 ELSEIF K2 >= K1 AND K2 >= K3 THEN
   PK1 = K2
   IF K1 >= K3 THEN PK2 = K1: PK3 = K3
   IF K3 >= K1 THEN PK2 = K3: PK3 = K1
 ELSEIF K1 >= K2 AND K1 >= K3 THEN
   PK1 = K1
   IF K2 >= K3 THEN PK2 = K2: PK3 = K3
   IF K3 >= K2 THEN PK2 = K3: PK3 = K2
 END IF
 Z$ = STR$(PK3) + STR$(PK2) + STR$(PK1)

 PP = 0: FOR P = 1 TO ALLDATANOW
 IF ALLDATA(P) = Z$ THEN PP = 1: P = OVERFLOW
 NEXT
 IF PP = 0 THEN
   PLAY "L16CDE": ALLDATANOW = ALLDATANOW + 1: RESYEAH& = 
RESYEAH& + 1
   ALLDATA(ALLDATANOW) = Z$
ALLDATAS(ALLDATANOW) = "(" + STR$(P1X) + "," + STR$(P1Y) + ") (" + 
STR$(P2X) + "," + STR$(P2Y) + ") (" + STR$(P3X) + "," + STR$(P3Y) + ")" 
 END IF
LOCATE 2, 1: PRINT "ALL :"; RESCORE&; " REG :"; RESREGU&; " NON-REG :"; 
RESCORR&; " Non-Repeat :"; RESYEAH&; SPACE$(20); 
 LOCATE 3, 1: PRINT K1; "   "; K2; "     "; K3; SPACE$(20);

 REM IF K = 1 THEN A$ = INPUT$(1)

TRY:

NEXT: NEXT
NEXT: NEXT
NEXT: NEXT

CLS : SCREEN 0, 0, 0
PRINT "THIS IS DONE!!!!!": PLAY "L4O3CDEFGABO4C"
ZZ = 0: FOR Z = 1 TO ALLDATANOW: ZZ = ZZ + 1
PRINT "TRIANGLE #"; : PRINT USING "####"; Z; : PRINT " SIDES : "; 
ALLDATA(Z); " THE POINTS : "; ALLDATAS(Z) 
IF ZZ = 20 THEN PRINT "--------------------PRESS----------------------":
A$ = INPUT$(1): ZZ = 0: CLS 
NEXT Z: PRINT :
PRINT "THE SOLUTION :"; RESYEAH&
A$ = INPUT$(1)

---

COMMENTS: These guys did a great job. They were very methodical and considered many possibilities. They also managed to define the problem well enough to write a computer program to find the answers. Their explanation goes through all the aspects of the problem they considered and what constraints there were on each option. Realizing that each triangle could just as well include the origin certainly helped narrow things down. In evaluating the solutions, I also found it very useful to have the points included, instead of just the lengths of the sides. Overall, excellent job, and well-written explanation.

Previous page || Next project || Table of Contents || Forum Home Page

3 July 1995