[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

655.0. "Lattice-filling triangles: Two puzzles" by MODEL::YARBROUGH () Wed Jan 21 1987 16:51

Consider a rectangular lattice with horizontal, vertical, and 45 degree 
diagonals, something like this:

	|/|/|/|/|/|
	|/|/|/|/|/|
	|/|/|/|/|/|
	|/|/|/|/|/|

(I can't draw the horizontals very well, but they are there).

In this figure one can construct equilateral right triangles (either 
down = _| or up = |/ ) of many different sizes. Furthermore one can cover 
a rectangular region with several such triangles (without overlap and
without exceeding the bounds of the rectangle). 

Example:
	 _________
	|      /|/|
	|    /  |/|
	|  /    |/|
	|/______|/|

Here the 4 x 5  region is covered by 10 triangles.

========================================================================
Puzzle 1: Given a 20 x 21 -unit rectangular region, what is the smallest 
number of triangles, of the type above and wholly inside the rectangle,
that will cover it? 
========================================================================
Puzzle 2: Is there a general method for solving this problem for {m,m+1}-
sided rectangles? For {m,n}?   (I don't have a solution for this yet.)
========================================================================

Some number theory gets involved in the general case. For example, the
smallest number for {m,n} sides is the same as for {pm,pn} if m,n are
relatively prime. 
T.RTitleUserPersonal
Name
DateLines
655.1CLT::GILBERTeager like a childFri Jan 23 1987 14:4412
    Let F(m,n) be the smallest number of triangles to cover the m x n
    rectangle.  I'll conjecture that the 'greedy' approach gives the
    optimal result, so that we have the recurrence:

	F(m,n) = F(n,m)
	F(m,n) = 0				if m = 0
	F(m,n) = 2 [n/m] + F(n mod m, m)	if m < n, and m non-zero

    where [x] indicates the integer part of x.

    If the conjecture is true, then the problem reduces to an analysis
    of Euclid's algorithm for determining the greatest common divisor.
655.2Elegance, not greed!MODEL::YARBROUGHMon Jan 26 1987 12:5519
>    Let F(m,n) be the smallest number of triangles to cover the m x n
>    rectangle.  I'll conjecture that the 'greedy' approach gives the
>    optimal result, so that we have the recurrence:
>
>	F(m,n) = F(n,m)
>	F(m,n) = 0				if m = 0
>	F(m,n) = 2 [n/m] + F(n mod m, m)	if m < n, and m non-zero
>
>    where [x] indicates the integer part of x.

Don't think this fills the bill. The optimum for (4,5) is
	 _________
	|    /|  /|
	|  /__|/  |	8 triangles
	|/|  /    |
	|/|/______|

The optimum increases linearly for a while, then slows: for (14,15) it is 
<= 13, for (20,21) it is < 20.
655.3A solution - is it best?MODEL::YARBROUGHThu Mar 26 1987 15:5824
Here's a 14-piece solution for the 21x20 case. The solution is not unique,
and it's possible there may be a 13-piece solution, although I haven't 
found it.
	 _________________________________________
	|            /|                          /|
	|          /  |                        /  |
	|        /    |                      /    |
	|      /      |                    /      |
	|    /        |                  /        |
	|  /          |                /          |
	|/____________|              /            |
	|            /|            /              |
	|          /  |          /                |
	|        /    |        /__________________|
	|      /      |      /|                  /|
	|    /        |    /  |                /  |
	|  /          |  /    |              /    |
	|/____________|/      |            /      |
	|          /|/________|          /        |
	|        /  |        /|        /          |
	|      /    |      /  |      /            |
	|    /      |    /    |    /              |
	|  /        |  /      |  /                |
	|/__________|/________|/__________________|