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

granted, a theoretical, but to draw a straight line, how wide?

If the "line" is about 90 tiles wide, it will cover all 5103 of them.

you could cancel the question

The only way the problem can work is to use the classic definition of a line and that is the line has zero width.

I SAY THE ANSWER IS 144. IF IT IS A DIAGONAL LINE FROM THE EXTREME TOP RIGHT CORNER TO THE EXTREME BOTTOM LEFT OR VICE VERSA. AN ANSWER FOR ANY OTHER DIAGONAL DESTINATION MUST BE SPECIFIED FOR ACCURACY.

KATANAKATA

Your math is good, and so is your logic except for a small mistake in your logic, which you made in it's last step. While 15 squares are crossed in each block of 7x9 squares that the line crosses, the line does not cross all nine blocks. It crosses only 3 blocks of 7x9 squares. 15 sq/bl x 3 bl = 45 squares crossed.

Extra GA for "attitude" demonstration.

there are 81 blocks of size 9*7; 9 rows and 9 columns of blocks!

If it's a true tile floor it will have grout lines between each tile. Grout lines will vary and humans laying the tile will also have an effect on the spacing. I think you have to go with 143 tiles crossed because I believe you have to rule out any perfect tile crossings.

ET

I think you are reading too much into the puzzle, but let's explore that claim a little more. At what tolerance must the "tiles' placement and grout thickness" be in order to yield 143 tiles and no other answer?

In other words, what range of error and thickness will always yield 143? Is this even solvable without extensive wok?

I suspect that if you did that analysis and plotted the probability for 143 versus other possible number of crossings, that you would not see 143 as being particularly special or more likely correct by any comfortable margin.

If that proves to be true, that would indicate to me that grout was a condition of the original puzzle and therefore, not a factor to be considered. In other words, word challenges are written so as there will not be ambiguities that could lead to an undefined answer.

You could go on ad nausium with the possibilities of unintended ambiguities. For instance, if the floor is not flat then this would also impact where a line may cross a tile.

Therefore, ambiguous and undefined factors should be ignored in word puzzles and assumed to not be a factor. Grout was never mentioned, nor the degree of perfection of the tiles and their placement. It would seem reasonable to assume that these are not factors of the puzzle.

Just adding my 2 cents to that;

Who said they are ceramic (or slate), so grouted - or have 'round corners'?

Why not add an industrial squareness tolerance?

----------------

If it must be 'brought to real world" why not think cork or vinyl tiles?

GAs to Hero and Usbport.

There is nothing to add, I failed to find a general answer.

Thank you.

Both methods work fine. I suspect there is a pure mathematical solution and fully expect someone to razzle-dazzle us with some neat formula that supplies an answer. That would be very cool.

Excellent. Thanks!

Lets assume m(columns) and n(rows) of tiles

Number of tiles (N_T) touched by the diagonal line will be:

N_T = m+n-GCD(m,n)....where GCD= Greatest Common Divisor

Substituting the values for m & n we get....

GCD(81,63) = 9

N_T = 81+63-9=135........

Hope it satisfies your quest/curiosity…J

There is a neat mathematical solution.

Assuming all tiles are perfectly square, no gaps between tiles and a thin line crossing from one corner of the grid to the other.

For a grid of tiles "L" tiles long by "W" tiles wide, find the largest common denominator "D". The number of tiles crossed by a thin line running from one corner of the grid to the other "N" can be calculated by:

N=L+W-D.

Neat.

One can find the derivation of the formula in #141

There may be an ambiguous reading of the phrase "one side of the floor." If a floor of 81 x 63 = 5103 tiles is meant, then the solution of 135 applies.

However, it could also be read as a floor of two sections (9 x 9) + (9 x 7) = 81 + 63 = 144 tiles. (The whole floor would 9 x 16. If drawn as 9 high x 16 wide, as the diagonal crosses each vertical course, sometimes it traverses one tile and sometimes two, crossing 24 tiles in all.)

For either version, I suspect a general formula would use modulo arithmetic.

I think the first sentence says otherwise:

"A rectangular floor is made up of square tiles, all the same size."

Misprint: That should have been GCD (greatest common divisor).

I sort of figured it was a misprint. ;-)

It will cross 72 tiles.

Counting crossings is similar to finding X and Y steps (like in Bresenham algorithm) needed to reach the opposite corner - which in this case is 144. Since every X+Y step crosses a tile twice we need to divide by 2 to get the correct answer.

Counting crossings is similar to finding X and Y steps (like in Bresenham algorithm) needed to reach the opposite corner - which in this case is 144

This part is right!

BUT:

because there are 9*9 the same areas as part of the whole floor there are 9 times one tile that willnot be crossed by the diagonal (each 9 by 7 part has 4 edges which are crossed right in the corner not in the fiel of the tile). so you have to subtrct 9 (for each crossed part and not divide by 2!

81

I think the answer is 81. The diagonal will cross the same number of tiles as are along the length. Masood Khan (Nedmasood)

That only happens if:

1) The slope of the diagonal line is equal to exactly 1 and...

2) The tiles are arranged in a square configuration of 81 tiles by 81 tiles.

This is Pythagoras. The diagonal is the hypotenuse of a right - angle triangle whose other two sides are 81 and 63 units long. The diagonal then, has to be 102.61578 units, and therefore bisects 103 tiles - it only clips the corner of some of 'em!

The diagonal then, has to be 102.61578 units, and therefore bisects 103 tiles.
I don't see where the 'therefore' comes from... The line isn't running across each tile for 1unit of length.
You may as well say, it must cross 81 to getacross one way and 63 to cross the other way so the answer is 144 (which is probably close enough for cat maths)
Del

You can also get the 15 tiles for each 7x9 subgroup by noting that the diagonal must, after leaving the bottom left corner, enter (7 - 1) tiles at the bottom edge and (9 - 1) tiles at the left edge. (I'm arbitrarily taking the long side to be horizontal and drawing from bottom left to top right.) The diagonal never enters a tile within the subgroup at a corner because the vertical dimension is a prime number. So the number of tiles crossed is (first tile) + (Number of tiles entered at left edge) + (number of tiles entered at bottom edge) = 1 + 6 + 8 = 15.

10/28/2007Floor Tiles: Newsletter Challenge (10/30/07)

We've seen this one before.

Maths Physics Maniac nailed it.

His method is as follows:-

1. Find the highest common factor of both numbers

2. Divide both numbers by this value so that you now have a grid whose side lengths have no common factor.

3. Add the side unit lengths and subtract 1

4. multiply this result by the HCF found in step 1.

For 1st floor of 81 X 63 it goes like this:-

1. HCF is 9.

2. Reduced grid is 9 X 7

3. Number of tiles crossed in reduced grid = 9 + 7 - 1 = 15

4. Number of tiles crossed in original larger grid = 9 X 15 = 135

very interesting.

I just drew out the 81 x 63 array and the crossing line. I see a repeating pattern and depending on rotation of the grid it is

1-2-2-2-1-2-2-2-1 or 2-2-2-3-2-2-2 squares crossed

times 9 occurrences, either way the correct answer is 135.

Why, is it 135?

81 tiles.

Odd.... Being a CAD guy, I used the software, it's way smarter than I. I drew a 12x12 square, arrayed it @ 81 x 63, giving me 5,103 "tiles". I issued the erase command, used the fence selection option from the upper right endpoint to the lower left endpoint and erased 143 "Tiles". Go figure, maybe the software is not smarter....

I originally misread the question and took the dimensions as 83x61 instead of 81x63, which gave me an answer of 143. Might you have done the same thing?

Checked, rechecked and checked again.... Another CAD guy did it, still 143..... I arrayed it the other direction, same result..... Is it just one of life's mysteries?

I think the program is retaining tiles that are intersecting at the corners. These should not count. The correct answer is 135.

I agree with the previous reply. At points where the diagonal goes exactly through the corner of a tile, maybe the CAD software - through rounding or cumulative error - sees it as missing slightly and just clipping the horizontally or vertically adjacent tile which it counts as an extra. There are 7 such points in the floor, which would bring the total to 142. Maybe it's also counting an extra one at the start or end.

I get 143 using cad the units setting is at 1/10 of a mm so it is connecting don't beleive it is rounding off

Your line has thickness in CAD. Your diagonal crosses eight exact intersections, I'll bet you picked up an extra at each of those because your line has thickness.

Look at Usbport's diagram, above, repeated at the corners. The line should only get the two corner squares, see if yours got an extra.

AHA! he exclaimed. The software selected (3) "Tiles" at the (8) intersections. Removing those rendered the previously determined 135. However, one may argue (but not this one) that the correct answer is 148, considering all (4) tiles involved in each intersection to have been "crossed" as opposed to the mathematically derived solution of 135.... Another bite in the buttocks from technology..... Considering, "...If a straight line is drawn diagonally across the floor from corner to corner..." one could also argue, as passingtongreen pointed out, "...Your line has thickness in CAD...", a line drawn, even with the finest point, has thickness.....

Correction, "148" should read "147".

The correct answer is 24, to be a rectangle both sides must have the same number of rows which is 9 (9 x 9= 81) and (9 x 7= 63) so the number of columns is 9 + 7 = 16. The rectangle is 9 rows by 16 columns of square tile.

I agree with Tornado 24 is the correct answer.

73 tiles A squared plus B squared divided by 1.414

because no. of squares crossed in any uinique rectangle is x+y-1

if the sides of the rectangle are x and y, and the common divisor is C, then

no squares crossed is x+y-C

135

PLot it out on quad paper. The correct vanswer is 24 not 135!!!

The OP did not define "line" or "crossing". Semantics, once again.

Even better, he did not specify Euclidean geometry. We could always do this on a torus.

I tried it the easy way by laying out the grid in ACAD and counting the squares that are crossed by the diagonal. It came out 135.

135

The ans is 162.

135 tiles

81 tiles. The tiles could be oushed to one side to verify that it only 81 tiles.

103 tiles

Given it is a tiled floor, consider there must be a gap between the tiles. Nominally there would be a 3mm gap between tiles. Relative to the size of each tile would determine the number of tiles crossed.

Assuming the tiles are 300 mm square (common floor tile size) with a 3mm gap between the tiles then the answer of 135 would be correct. We all need to remember the world of reality. The text in the question read it was a "tiled floor" I am certain all those with the wonders of a computer to access this column will have also seen a "tiled floor"

Remember: If everyone is thinking alike, then someone isn't thinking

George S. Patton

the floor has the size of 81 by 63 tiles or the size of 9 times 9 by 7 tiles!

The size of 9 by 7 tiles has a diagonal crossing 15 tiles, the floor 9 times 9 by 7 tiles has a diagonal 9 times 15 = 135 tiles!

the 15 crossing tiles is 9 + 7 - 1

the 135 tiles crossing is 81 + 63 - 9

I agree with 135 tiles. Tried drawing it on graph paper and got 133, because of line thickness obscuring close cuts at corners. Can use just plain ratio to find out how much line moves across as it moves up a tile (or the other way around).

63/81 = 0.777777... ACROSS for 1 UP.

Calculate line's ACROSS position for every UP. If the ACROSS value moves from a N.xxx to a (N+1).nnn , (e.g. from 2.3333 to 3.1111), for a single UP, then the line cuts 2 tiles.

Excel is good for this. UP column goes from 1 to 81, and ACROSS is formulated as [(UP value)*0.77777...] Copy formula down to 83 and look at the transitions in ACROSS as described above. If you want Excel to give the number of tiles for each move, the formula for that column is [=ROUNDUP(ACROSS cell value in this row,0)-ROUNDDOWN(ACROSS cell value in previous row,0)] The "0"'s in the formula strip out the decimals. I think the formulation works for other layouts also.

Here's the first 11. Note how from Tile 4 to Tile 5 one stays in the 3's, and from 9 to 10 one stays in the 7's, giving a single tile cut. Pattern repeats itself (as others have shown) every 9th up and 7th across, which one might expect, since that's the 81/63 ratio.

There is a different answer if you think of the number of squares, not the number of tiles that are crossed. It is perhaps a more interesting problem for the theorists here!

Let's ask a different a question: How many squares will the line cross?

Each tile is a square. There are 135 tiles crossed by a diagonal line.

Each block of 4 tiles makes a larger square. It too has to be counted as 'crossed'. Each block of 3x3 tiles makes a larger square which has also been crossed. The lower right block of 4 in the 3x3 is another square that has been crossed.

And so on. A 63 x 63 square exists for each the 19 central columns (presuming it is 81 wide and 63 high). So there are a lot of squares within each of those 63x63's.

How many 'squares' in total are crossed by the diagonal line?

:)

Crispin in Waterloo

Nice expansion of the problem. First, let us determine what the maximum number of squares might be. Let the tiles be arranged in an M by N array with M greater or equal to N. Consider a coordinate system with the x-axis aligned along the long side of the array and the y-axis aligned with the short side of the array.

Starting with the largest possible square (N x N), put one on the array of tiles with one corner at the origin.

By moving the N x N square one tile at a time to the left, we see there are M-N+1 possible locations for squares of size N x N. If we now use a square that is (N-1 x N-1) and place it at the origin, we see that the upper right corner of the square could be in both the top row and the one just below the top row.

There are 2*(M-N+2) possible locations for the N-1 x N-1 square. In general, if the square has a size length of S, the total possible number of squares of that size that will fit on the array is (N-S+1)*(M-S+1). Note that for S=1, the number is N*M which is correct. The total number of squares that will fit on the array for a 63 x 81 array is 121,632.

Now we need to figure out how many of these squares are not crossed by the diagonal line. We can determine the largest square that will fit inside the array and not be crossed by the diagonal, as follows. Consider a square with its upper left hand corner in the upper left hand corner of the array. The equation for the diagonal line for the array is y = N/M*x. The equation for the diagonal for the square is y = N-x. These two diagonals intersect at x =M*N/(M+N). All squares larger or equal to M*N/(M+N) will be intersected by the diagonal.

For an 81 x 63 array, the maximum size is 35. For a square of side 35, there are two possible locations above the line. One is as shown above and the other is one tile to the right with the corner just on the diagonal. There are the same number on the other side of the diagonal. There is probably some some elegant way to determine the number for various values of S but I did it by brute force in a CAD program.

The results are shown below.

The top line is the total number of squares possible within the array for a square of a given size. The yellow line is the number of squares of a given size from the first curve that do not cross the diagonal. The open squares line is the number of squares of a given size that are crossed by the diagonal. The total is 61,212.

Thanks,

Jim

If you look carefully at the drawing of the 7x9 grid, only the center tile is actually "crossed", ie., the line going in one side, and out the other side of the tile. All other tiles have the line going thru the top, bottom, or corners. The actual answer should be 9.

Anon

As has been mentioned the question could be answered differently based on additional information. If we reduce the presumed 81x63 length and width down to 9x7 as has been mentioned we are assuming that the adjacent squares to either corner do not have the the line "crossing through them" If we are willing to exclude this from our count should we not also exclude the third square I have pointed to? To me this signifies the improtance of a purely mathematical calcaulation which has not been accurately discussed.

On the other hand because the question is very poorly worded I have illustrated another possibility for the "sides of the floor" One side 9x9 (81 tiles) the other 9x7 (63 tiles) for a 9x16rectangle??

Ideally, it would have worded it so that it was simply adjacent squares and all lines have no thickness. I think you are right that you need to approach this mathematically and I will explain my thinking...

From a pure mathematical standpoint, the arrow in the center of your square is in error.

The reason is this:

1) All squares are perfect.

2) There are 7 by 9 squares. This implies that a single square sits exactly in the center of the 7 by 9 group.

3) The slope of the diagonal that transverses from the lower left corner to the upper right corner is < 1. It also must bisect the center square perfectly and will be symmetrical with respect to the center of the center square.

4) Any line that has a slope of <1 and bisects the center square must exit passing through both the left and right sides of that center square.

Therefore, not only will the diagonal line cross the center square, it must also cross through the squares to the left and the right of the center square symmetrically.

Even if the line's slope was .999999999999999999999999 it would intersect the two adjacent squares.

Lastly, if you are basing your claim on your drawing I have two observations:

1) Your drawing is not consistent. The size of the squares varies from the bottom row to the row above it.

2) An analysis based on a drawing will not be inherently accurate due to limitations of the graphics system that recreates it. Only pure mathematics can be used and there may be limits due to the precision used. In this exercise high precision is not required, so the task is pretty easy.

I don't know about your alternate interpretation of the puzzle. That seems pretty subjective, but that is just my spin on it.

Good points - I just drew it up real quick and messed up one dimension in excel - now if we assume that as the line passes through the exact corner with no thickness - it becomes easy visually to solve @135. However if the line has any thickness we would have to add 16 unless we ridiculously (as was mentioned earlier) add in grout lines between tiles. That line of thought would take our count in the opposite direction as thickening of the line

My alternate interpretation is almost as subjective as the question - I am still hoping to see an equation posted as I have not taken the time to pursue that but would like to figure that out

The equation was posted by Tornado earlier and is as follows...

If a and b are the length and width, the number of tiles crossed = a + b - GCM (a,b).

In the 81 x 63 case, the GCM is 9; 81 + 63 - 9 = 135.

In the 9 x 16 case, the GCM is 1; 9 + 16 - 1 = 24.

The equation was given two or three times way back in the early posts: a + b - GCD(a,b).

Answer is 117 when actually draughted.

Sorry drew it wrong last time, now I'm getting 141

Reading comprehension ? The floor is a "Rectangle".... The tiles are "Square" 135 tiles

It will cross 126 tiles, because it will slope at a greater angle in the 81 direction and will therefore cross 2 each time it crosses a row in the 63 direction. Because 63 and 81 are both divisible by an ODD number of 9s (7 and 9) the diagonal will cross at the mid point of 7 lines and 9 lines which is through a corner, so at no point will it cross 3 tiles.

The floor can be divided into 81 identical blocks of 9 tiles x 7 tiles. When I drew a rectangle measuring 9 x 7, and drew the diagonal, I found that 15 tiles were cut by the diagonal. Now for the full floor, there will be 9 such rectangles being crossed by the diagonal. Therefore, my answer is 15 x 9 = 135 tiles

The question says the floor is rectangular and the tiles are square, but does not define the orientation of the tiles. In the picture below, for one 9x7 block of tiles the diagonal crosses 16 tiles. Since this block repeats diagonally 9 times across an 81x63 tile floor, the overall diagonal crosses 9x16 = 144 tiles with this configuration.

Good out of the box thinking.

there are some triangle tiles!

The tiles on your outside edge and corners are not square.

The answer is 143, I also used my cad software to calculate the number.

The question had no mention of the thickness of the line and it also doesn't mention if the tiles butt up together or there is a gap. So technically the line can still touch the corner of two tiles even if it disects on the corner. The line will still touch the corner assuming a line isn't 0 units thick and there is no gap between the tiles.

So, answer still stands at 143.

Steve

The line connecting both corners is the function: Y=63-(63X/81).

We look for the intersections of this function with the vertical lines and parallel ones

Axis Y from 0 to 63.

Axis X from 0 to 81.

The total number of intersections is 136.

The number of tiles cut =nº intersections -1 = 135 tiles being cut.

This method can be applied to any rectangular configuration of square tiles.

61 and 83 are primes, so you will never go just thru crosspoints, where it woulkd be difficult to decide how many tiles are effected. So the answer ist you have to cross one tile each column and one tile each row minus one, thus 83 + 61 - 1 = 143 tiles.

(minus one: would be nice to explain it exactly, i do it frankly the "inductive" way: start with a 1 * 1 tiled floor, the result must be 1)

81 and 63, the sum of 81 and 63 is just the same like the sum of 83 and 61, but 81 and 63 are dividable by 9!

Oh sorry !

I mixed up the digits due to time. I should have been to bed last night already for several hours ... But I could not resist to participate spontaniously in this discussion - and went totally wrong.

But I guess the trick is to divide the axles by their greatest common divider (9 - as most of You already have noted) and look at the resulting rectangular fractions. This is than (7 + 9 - 1) * 9 which results in 135. (If the at their edges touched squares do not count as crossed.)

157 average joe

I came up with 143. I just made the grid pattern on ACAD and then erased everything the diagonal line crossed. ACAD reported 143 items erased.

129 sqaures

135 or 143? It depends how pure you want the maths to be. In the pure model, the diagonal passes exactly through the corners of the 7x9 sub-groups, crossing 135 tiles altogether. If the diagonal is not ideal and deviates even infinitesimally from the pure mathematical course, it picks up additional tiles bringing the total to 143.