Rectangular Floor: Newsletter Challenge (10/05/10)

I don't think you guys have a clue. How can a diagonal line from corner to corner cross 135 tiles when there are only 144 to begin with? Hello!

Please read some other parts of the thread, especially the early section. There is the possible interpretation of 16 x 9 tiles [(9 x 9 ) + (9 x 7)]. But by far the more commonly understood interpretation was 81 x 63 = 5103 tiles.

AH got it right in the first place (posts 1, 2), and Usbport nailed it with the picture in post 3. Anybody who can't look at this picture, count to 15, and multiply by 9... good grief!

The most likely AutoCAD problem probably consisted of duplicate squares in the selection set, namely the squares on both sides of the line when it perfectly intersects an internal corner of tiles. AutoCAD computes to something like the 10th decimal place or better, so line width should not be a factor.

the reason for this difference from the ideal line is the limited number of numbers in the CAD (here utoCAD-Software)!

every numerical solution is not better/exctlier than the number of numers/digits used in the numerical calculation!

read back. 81 x 63 = 5103 tiles Hello!

The answer is 135. While I agree with reply 1 and 2 by "anonymous hero" the explanantion in #2 is un-necessarily long and complicated.

The "15" comes about from: (no. rows + no. columns -1 ) = (9 + 7 - 1) =15

Simply put, the line must cross all 9 rows (on the long side) to get from one end to another. Similarly the line must cross all seven columns (short side) to get from side to side. However 1 tile is common to both the row and column count and will be counted twice leading to the "-1" component.

If other simple combinations of tiles are considered it will be quickly seen that this works. The only catch is that there must not be be a common multiple between the number of tiles on each side. When this occurs the line will cross perfectly through a corner.

A more generic formula is:

(no. rows + no. columns - GCF )

where GCF is greatest common factor. In the 9 x 7 case the GCF is 1 giving the answer 15.

In the case of 81 x 63 the GCF is 9 so the answer is 135.

The answer is actually zero. When you consider curvature of the earth a straight line would leave the first corner and head out to space.

I'd say it crosses 135 tiles. The line starts on one tile, and every time the line passes over any "cracks" between tiles it crosses a new tile, but there are 8 places it crosses over two "cracks" at once with only passing over one new tile (where the corners of 4 tiles meet), since both 81 and 63 are multiples of 9, and the floor can be divided into a 9x9 array of 9x7 tiled ares.

so the calculation looks like 1+(63-1)+(81-1)-8=135

You can also look at is as 9 separate tiled areas that have funny places where the line crosses 2 "cracks" at once, so the calculation is:

9X(1+(7-1)+(9-1))=135

Cheers,

135 tiles are crossed, not necessarily in the center, when the rectangle is drawn L=81 and W=63.

66 tiles

Pray tell how?

Simplify,

81/9 = 9

63/9 = 7

Grid 9x7

Diagonal through Rectangular

i.e Mirrorred - pass in through the 2 tiles in the same way diagonally opposite

simply the mirror:

9/2=4.5

7/2=3.5

Keep real numbers only

4 and 3

4+3 = 7

apply mirror

7x2=14

add remaining 0.5 + 0.5 =1

Sub TOTAL = 14+1=15 for 9 by 7 grid

TOTAL = 15x9=135 Tiles for the full grid 81 by 63

Keep it straight and simple, KISS!!!!

Richard

It will cross 144 tiles, (ie 81 + 63) because on its journey it will cross one tile per column and one tile per row.

So in a floor of one side 4 tiles and other side 10 tiles the diagonal will cross 14 tiles (ie 4 + 10)

Mike K, Joburg South Africa

May I add a further comment.

Assumptions

1. Floor is flat and planar

2. The diagonal is

a. a perfectly straight vector in the same plane

b. has thickness be it infinitessimal

Observations

1. If the sum of the number of rows and columns is even (ie even + even or odd + odd) the diagonal will touch (R + C) tiles

2. If the sum of the the number of rows and columns is odd (ie odd + even) the diagonal will touch (R + C -1) tiles

NOTE

Checking with draughting software such as Autocad does not confirm this

Drawing the grid and doing a mock delete using the diagonal as a fence, gives 143 not 144. Somewhere along the line the vector diagonal is just touching the corners of 2 tiles and only registering one.

Mike K

Joburg, South Africa

"It will cross 144 tiles, (ie 81 + 63) because on its journey it will cross one tile per column and one tile per row."

Consider this:

1. Tiles are perfect squares and butt against each other perfectly.

2. The grid is 63 tiles tall(Rows) by 81 tiles long (Columns).

3. First calculate the slope of the diagonal line, which is the rise over the run: 63/81 = .777...

That means the slope is less than 1 (one). If the slope were exactly one the line would intersect the corners of every tile at an angle of 45° and the tile grid would be itself a perfect square.

However, since the slope is less than 1, the diagonal line must cross more than 1 column tile before hitting the second row. In fact, with a slope of .777... it will hit at least two columns per row and sometimes three, but I digress.

My point is that your assumption that it will cross one tile per row and one tile per column is wrong and a simple check of the diagonal's slope would be proof of that.

in principle the these of crossing 1 tile per row and one tile per column is right - but there are some tiles crossed in their edges! This is because its necessary to find the smallest block of tiles crossed (largest common factor of the field) from edge to edge!

These smallest blockes of m*n tiles are crossed m+n-1 times by a line from edge to edge!

Huh? Just imagine the puzzle if it was 2 tiles high and 20 tiles long.

there are 4 areas of 1 tile by 10 tiles N=1,M=10; the total of crossed tiles is 2*(N+M-1) = 2*10 = 20; if the area is 10 by 10 tiles there are 10*(1+1-1) tiles crossed!

okay

I didn't actually mean it like that.

A recheck in autocad shows me that my 144 was wrong any way.The diagonal will cross 135 squares in two places (ie the sides) and another 16 in just one place (ie the corners), giving a total of 151.

Therefore considering the lines to have a thickness, but infinitesimally small, I would say 151.

If the line has zero thickness it wont exist anyway and wont touch anything!

Yes, the line will touch 16 extra tiles, but cross usually means encountering the interior of the tiles. And in geometry, the width of a line is zero.

okay

Taking that definition of the word "cross", which sounds good, the answer would be 135.

Your comment about the width of a line in geometry always being zero, also makes good sense.

Thanks for setting me on the right path.

Mike

The answer is the square root of 81 square + 63 square

the square root of 10530 = 102.62

that means the line would cross 103 tiles

Yep, had to happen

not the length of the line, the number of tiles are requested (diagonal lines are longer than any side of a rectangluar area)

Reduce the "dimensions" to relatively prime numbers. In this case, the tile dimensions will be reduced from 81 x 63 to 9 x 7. Remember the greatest common factor used in the reduction (9, in this case.) In general, the original dimensions are X by Y. Find the greatest common factor, Z. X =Z*M by Y=Z*N will then reduce to M by N. Also, assume M >= N.

Plot this M x N on a rectangular Cartesian coordinate system. The line with slope N/M through (0,0) will be the diagonal. The slope will be <= 1.

Some observations:

The diagonal will not cross at a tile corner (other than the points (0,0) and (M,N)). (i.e., the diagonal will not cross at an integer intersection.)

The diagonal will cross every horizontal tile line. With N rows of tiles, there will be N-1 tile lines crossed.

Every time a horizontal tile line is crossed, an additional tile will be "added" to the tiles-crossed-count.

Every column of tiles will be crossed once.

Because the slope is <= 1, for every tile crossed from left to right will result in at most 1 additional crossing. Every horizontal tile line crossed will add 1 and only 1 tile crossed to the count.

The total tiles crossed will be M + (N-1).

Bringing the greatest common factor back in, the total number of tiles crossed will be:

Z*(M + (N-1)). For this problem, this will be 9*(9 + (7-1)) = 135.

This formula will work if M = N =1 or if N = 1.

theres no difference in the result if M>N, M=N or M<N

the number of crossed tiles in an (prime)-grid is still the same expression: M*N-1

if the prime grid is just a sub-grid in a larger area the result is to multiply with the factor of numer sub-grids: Z*(M+N-1)

surely: not M*N-1, M+N-1, the difference between these cases is only the shift-key!

143 tiles will be crossed by the line.

Steve-Applied Ind.Tech.

Using Pythagorean's theorem for triangles the line is going to cross 102.6 tiles. The sq. root of the hyp (the diagonal line) = sq. root of (81 squared + 63 squared).

134 tiles will be crossed

I agree with others that the problem can be simplified knowing that 81 by 63 tiled floor can be looked at as 9x9 by 7x9. But I looked at some smaller samples and wondered if the problem can be simplified further as x+y-1 where x and y are the widths of the sides of the floor. So in this case the crossings would be 81+63-1=143. While I have not proven this answer it would at least be a reasonable first engineering quess as to what the answer might be

there are 9*9 areas of 7*9 tiles in the 81*63 field, so the value is the result of 9*(9+7-1) or 81+63-9

It appears that 149 tiles are crossed if including intersecting points.

Since the grid is 81 by 63, a diagonal must traverse 81 tiles in the long direction and 63 tiles in the short direction or a total or 144 tiles.

See Post # 107 for a short proof as to why that answer is wrong.

The formula is Root under 81*81 + 63*63 = 102.61 say 103.

The stright line drawn diagonally will cross 103 tiles.

123 tiles

The diagonal crosses 88 tiles

Let us consider 81 rows of tiles. The first and the last rows will have only one tile each crossing the diagonal. Balance rows will have two tiles each intersecting the diagonal. So number of tiles crossed by diagonal are:

2+(81-2)x2=160

No, it should be 144. 81 and 63 can be broken down in 9 identical blocks of 7 and 9. I a block of 7 and 9 there will be

2+(9-2)x2=16 tiles involved.

So for 9 rows 16x9 = 144 tiles will be involved

Well done!

Welcome to the CR4 forum, too!!!

Doubly welcome and done - post # and answer synchronicity

That was the whole idea!

Does it play any role how many tiles in y direction are crossed for one tile in x direction ? I dont't think so; if you have that rectangle consisting of squares with number of rows (r) and number of columns (c) relative prime a line must cross all the rows plus all the columns thru tiles (i.e. 'sneaks' thru no crosspoints).
This leads to the formula for number of crossed tiles (t) t = c + r in the first place.
Experience now tells it is one less ( t = c + r - 1 ).
I read only 1 explanation for that here (#95: "However 1 tile is common to both the row and column count and will be counted twice leading to the "-1" component.") - Well that reads fine. On a 1 * 1 field this seems the resolution, but in a 2 * 1 field what would be the double counted tile than ?

the tiles in the edges of the area are both crosses only one tile an one side of the tile, independent from the direction of the crossing line.

All other tiles are crossing on two sides of the tile - this is why the number of crossed tiles are rduced by 1 (-1) in the prime area!

My explanations in #141 gives answers to your questions.

in the prime area (9*7 tiles) are 15 tiles crossed (9+7-1=15), the rectngular floor is made by 9*9 prime areas. each column and each row contains one prime area that is diagonal crossed; so the total amaount of crossed tiles is 9*15=135

my first - my last - my everything (unknown interpret)

Thank you for your comments and welcomes. Let me drive the general formula from my analysis.

The increments in Y direction (0, 2/7, 4/7, 6/7, 1 1/7, 1 3/7, 1 5/7, 2) can also be written as; (((b-a)/a))*0, ((b-a)/a))*1, ((b-a)/a))*a*2,...., ((b-a)/a))*a) where a is the # of tiles in x direction and b is the number of tiles in y direction.

For example, if a=4 and b=7 then the increments would be (0, 3/4, 1 2/4, 2 1/4, 3) Being an integers last increments indicate that the line ends at the corner. Whenever the increment exceeds an integer then at this tile column the line travels 3 tiles. In the original problem this occurs once and in my example it occurs 2 times.

(The last increment -1 ) is the number of occurences in which the line travels three tiles. In general this is ((b-a)/a))*a-1

Then from my analysis;

The # of tiles crossed = 2*(the # of tiles in X direction) + (the # of occurences of travelling three tiles)

The # of tiles crossed = 2a + ((b-a)/a))*a-1

The # of tiles crossed = a + b -1

If there are common divisors;

The # of tiles crossed through whole diagonal in the room = a + b - GCD (A,B)

Where A and B are the # of tiles at the sides of the room.

For narrow rectangles, for example a=4 and b=11, the increments (0, 1 3/4, 3 2/4, 5 1/4, 7) can skip two integers at once and in these cases the line travels 4 tiles at the particular column but formula is still valid.)

A + B - GCD(A,B) not a + b - GCD (A,B)

"(The last increment -1 ) is the number of occurences in which the line travels three tiles. In general this is ((b-a)/a))*a-1"

This is false, it would be ((b-a)/a))*(a-1). This never leads to a + b - GCD, but the idea is nice...

Thank you for your attention, But there is no mistake, let me explain.

The last increment is an integer because the line crosses through the corner at the last tile, we need to find number of occurences where the increments exceed an integer. Everytime the increments exceed an integer the line crosses one extra tile.

Let's say O = The # occurences where the lines crosses one extra tile

Then O = (the last item -1)

O = (((b-a)/a))*a) -1)

O = b-a-1

Then;

The # of tiles the line crossed = 2 * (# of tiles in X direction) + O

= 2a + b -a -1

= a + b -1

This the formula when there is not a common divisor. When there is a common divisor then let's divide each side of the above formula with GCD.

Then ;

The # tiles the line crossed *GCD(A,B) = a*GCD(A,B)

+ b*GCD(A,B)-GCD(A,B)

Where A&B are the total # tiles in x&y direction in the whole room where a&b are the # of tiles in x&y direction for the small rectangle without a common divisor.

The # tiles the crossed (the whole room) = A + B - GCD(A,B)

That's the formula for the whole room. If one use a&b for the # of tiles in each side of the room.

The one can rewrite the formula as; a + b - CGD (a,b)

We leave the set of natural numbers with that.
Lets say: a columns of tiles, b rows o.t., line orientation right/up.
The slope is b/a "tiles up per tile right"
Define "Increment" (I) as the row-coordinate (y), where the line leaves a specific column of tiles (x) to the right: I = b/a * x
a, b, x are natural numbers, y is a rational nuber
Now is I(x+1) - I(x) = a/b constant
What you found is that: If I - INT(I) < a/b than some parts of the line must have crossed thru another tile (below) than this in this column.
And I - INT(I) > a/b than all the slope of the line appears in this tile.
Here by the way you'd have to bother the GCD to fix the "=" case ...
The whole case can be simplified to INT(a/b) < 1 without making restrictions, so the only remaining question is about "1 additional tile or not ?"
Right so far ? I'd like to get you. Consider that you wrote the sequence I as ((b-a)/a)*x that is b/a * x - x
How often now happens that 2 tiles are involved per column pass ? It should lead to b - 1, presumed the GCD is stripped off before.

b/a, not a/b (typ$@/$$.ß)

Drop the portions of the line to the first row, as if the portions start from the x-axis for each column. Then it is clear with a slope of 9/7, the line needs to travel at least through 2 tiles in each column. Note that the line travels in y direction 9/7 tile side long. What I call "increment" is the part of these portions above the first row. The projections of these increments on y axis is 2/9 tile side long. This means that while the line travels through the 7 X 9 grid from corner to corner, it crosses at least two tiles in each column but also starts 2/9 tile side long (one increment) higher from the lower border of the border compared to the previous column. These increments add up and when the summation exceeds an integer then the line travels through 3 tiles instead of 2 in this particular column. If the projection of the line travels 1 2/7 tile side long in y direction, then the line can travel through 3 tiles in that column.

In our case a=7, b=9 then the summations of increments at the end of each column are (2/7, 4/7, 6/7, 1 1/7, 1 3/7, 1 5/7, 2) Note that increments exceed an integer only once at the forth column and in this column the line travels through 3 tiles. These are the occurences we need to count and sum up with the min. number of tiles the line needs to travel through for each column for finding the number of tiles crossed. Please note that the last item in the summations of increments is (b-a)=(9-7)=2

If a=5 and b=9 for example then then the summations of increments are (4/5, 1 3/5, 2 2/5, 3 1/5, 4) or the last item is again (b-a)

"...lower border of the row..." not "...lower border of the border..."

So this is counting out the 9 * 7 case. Now I understand your increment:
It is indeed I = b/a * x - x = ((b - a) / a) * x
You use the "- x" to reduce the slope b/a (9/7 > 1) by 1, than you can presume a count 2 for each step (column forth, row up). The remaining part above a slope of 1 is described by I.
Where INT(I) = INT(b/a * x - x) = INT(b/a * x) - x becomes greater than 1 an additional tile is effected in the current column.
This approach does not lead to generally "a + b - 1" (a, b relative prime).

((b-a)/a)*x is the general expression which gives the summation of the increments at the end of that particular column. The increment is (b-a)/a and is same for each column.

For every occurence in which the value of ((b-a)/a)*x (or b/a*x-x ) as you write exceeds an integer there appears a third tile crossed.

If two integers exceeded once then a fourth column is also crossed. In the case a=5, b=13 where the summations are 1 3/5, 3 1/5, ......8 ) the line crosses three tiles in the first column and four in the second. (because the summation for the first column exceeds one integer, namely 1 and in the second column it exceeds two integers, namely 2 and 3. ) This shows that for each integer exceeded, there is one extra tile (additional to two for each column) crossed. The easiest way to count these occurences is subtracting one from the value of the summation of increments at the end of the last column. That is why (((b-a)/a)-1) or (b-a-1) gives us always the count for these occurences. Then you add up this with two necessary ones for each column then 2a + (b-a-1) = a + b -1

In the case a=5, b=13, by observing that the line needs to cross at least 3 tiles, one could define the increment as (b-2a)/a then the summation at the end of each column would be ((b-2a)/a)*x for a particular column. Everytime this value exceeds an integer then this would point out a fourth tile crossed. The count of these occurences is one less than the last item (b-2a)-1 and then summing this up with three necessary ones for each column would lead 3a + (b-2a)-1 = a + b -1 again.

If we were to start with a=11 and b=5 then the distance travelled on the y axis is 5/11 tile side long, then the min # of tiles must be crossed for each column is 1. The increment could be defined as (b/a) and the summation of the increments in general could be writen as (b/a)*x. Everytime this value exceeds an integer then this would point out a second tile crossed. The count of these occurences is one less than the last item (b-1) and then summing this up with one necessary tile for each column would lead a + (b-1 ) = a + b -1 again.

Ok, I guess I got you.
Let's say a > b (if a < b exchange a and b, that makes no difference)
It is then b/a < 1, INT(b/a) = 0
This means you count 1 for each column (x) passed, this sums up to a
The line is y = b/a * x
At the end (x = a), where the line leaves the prime rectangle is y = b
One column before (a - 1) it is b/a less
You calculate now the rows passed as INT(b/a * (a-1)) = INT(b - b/a) = b - 1
In total indeed a + b - 1 !
;-)

In general we can rewrite the formula as; (b is the long side and GCD=1)

The # of tiles= [1+INT(b/a)]*a + {{b -[INT(b/a)]*a} / a}*a -1

= a + b -1 again.

Dividing the floor into blocks of 9 x 7 tiles, the diagonal will always pass through the diagonal corner of the block.

In each block the diagonal will cut through one tile in the first and ninth column and two tiles in the rest. Hence in one block, the diagonal will cut 1+7x2+1=16 tiles.

In the nine blocks, the number of tiles cut will be 9x16=144 tiles.

Anonymous Hero is correct in his statement that the problem can be reduced to nine blocks of 7x9 squares and that the line will cross 15 squares in a block of 7x9 squares. He is however wrong when he states that the answer is the product of 15 squares times 9 blocks. The line crosses only three blocks, therefor the correct answer is 15 squares/block times 3 blocks which equals 45 squares crossed by the line.

Off Topic ?
Let x and y the extension of the floor in tiles,
than let r = x/GCD(x,y) and c = x/GCD(x,y) these are rows and columns of the smallest sub-floor in which the line goes from corner to corner diagonaly, these sub-floors repeat GCD(x,y) times in the floor along the line.
For the sub-floor is the number of crossed tiles (t) t = c + r - 1
To proof this, imagine a point moving along the line and consider the transitions from tile to tile:
Each transition leads to a tile crossing, the corners where the line starts or end count as half a transition each.
Hence r and c are relative prime there are only transitions either in x or in y direction exclusively.
To reach the opposite corner fromoff the start corner c - 1 and r - 1 transitions are neccessary, together with the two half-transitions is it (c-1)+(r-1)+1 = c + r - 1 So less is not possible.
It cannot be more hence following the line forces direction towards the opposite corner
, it can't go back anyway to cross more tiles.
So is t = c + r - 1 valid and the total number of crossed tiles on the origin floor (T) is:
T = (x/GCD(x,y) + x/GCD(x,y) - 1) * GCD(x,y) or T = x + y - GCD(x,y)

still 135

than let r = x/GCD(x,y) and c = x/GCD(x,y) ? r=c?

in some rows/columns are more than one tile is crossed!

typewriteprint error, unfortunately copied again - xcuse

the 2nd expression "x/GCD(x,y)" appearing at the right in the terms are to be read as "y/GCD(x,y)" (of course)

sure - what else

Please showing drawing of your solution. Your question implies a single line crossing a rectangle floor. I believe your answer is incorrect or I am not understanding your question; see post 31 for the correct answer.

According to the actual "answer" posted at the top of the page, 135 is the answer.