| 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 |
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.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 655.1 | CLT::GILBERT | eager like a child | Fri Jan 23 1987 11:44 | 12 | |
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.2 | Elegance, not greed! | MODEL::YARBROUGH | Mon Jan 26 1987 09:55 | 19 | |
> 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.3 | A solution - is it best? | MODEL::YARBROUGH | Thu Mar 26 1987 12:58 | 24 | |
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. _________________________________________ | /| /| | / | / | | / | / | | / | / | | / | / | | / | / | |/____________| / | | /| / | | / | / | | / | /__________________| | / | /| /| | / | / | / | | / | / | / | |/____________|/ | / | | /|/________| / | | / | /| / | | / | / | / | | / | / | / | | / | / | / | |/__________|/________|/__________________| | |||||