Well, I attended this years ARML competition, and I found the questions to be challenging, and the power round to be a lot of fun.
For those who don't know: arml.com
Basically, I'm posting this year's power round. I don't know the answers yet either, I'd like to see who can come up with something though... =D
ARML POWER QUESTION 2008 - Piles of Tiles
------------------------------------------------------------- (Rules of the power round at ARML(Applies here too, but not all of them(Specifically, only the bolded rules apply)))
The power question is worth 20 points. Each problem is worth 4 points. To receive full credit the presentation must be legible(not a problem here), orderly, clear, and concise. Even if not proved, earlier numbered items may be used in solutions to later numbered items but not vice versa. The pages submitted for credit should be NUMBERED IN CONSECUTIVE ORDER AT THE TOP OF EACH PAGE in what your team considers to be proper sequential order. PLEASE WRITE ON ONLY ONE SIDE OF THE ANSWER PAPERS.
Put the TEAM NUMBER (not the Team name) on the cover sheet used as the first page of the papers submitted. Do not identify the Team in any other way.
------------------------------------------------------------- (Some background information for the questions)
Given a rectangle whose dimensions are a x b, where a and b are integers, a tiling by rectangular tiles of dimensions u1 x v1, u2 x v2, etc., where all dimensions are integers, is an arrangement of tiles that fill the rectangle with no gaps and no overlaps. The edges of the tiles are parallel to the sides of the rectangle. For example, some of the ways to tiles a 4x4 rectangle with 2 x 2 and 1 x 4 tiles would be to use four of either tile shown by the left two diagrams or two of each as shown by the right two diagrams:
((Sorry, I'm too lazy to upload an image. For each 'rectangle' lines indicate the actual lines that are drawn in and spaces are used to indicated the grid, unless filled in by a line.))
A [i]u[/i] x [i]v[/i] tile has a height of [i]u[/i] and a width of [i]v[/i]. The diagram shows a 2 x 3 tile on the left and a 3 x 2 tile on the right. Tiles cannot be rotated into different orientations and two [i]u x v[/i] are indistinguishable. As example of different tiling, there are two ways to tile a 1 x 3 rectangle with a 1 x 1 tile and a 1 x 2 tile---the 1x1 tile can go to the left or to the right of the 1 x 2 tile. Let S([i]n[/i]) and |S([i]n[/i])| represent the set of tilings of a 1 x [i]n[/i] rectangle and the number of such tilings respectively.
------------------------------------------------------------- (Now the actual questions.)
1. a) Compute the number of ways a 1 x 4 rectangle can be tile with 1 x 1 and 1 x 2 tiles.
b) Give two different tilings of a 12 x 15 rectangle with combinations of 2 x 4 and 3 x 3 tiles.
c) Prove that it is impossible to tile an 80 x 80 rectangle with tiles of sizes 3 x 11 and 4 x 15.
2. a) For [i]n[/i] that is an element of {1, 2, ..., 10}, compute the number of ways to tile a 1 x [i]n[/i] rectangle with tiles of sizes 1 x 1 and 1 x 2 tiles. Give your answers in a table.
b) Determine, with proof, a recursive formula to compute the number of ways to tile a 1 x [i]n[/i] rectangle with 1 x 1 and 1 x 2 tiles. use the formula to compute the number of ways to tile a 1 x 17 rectangle.
3. a) In a table, list all values of [i]n[/i] less than or equal to 40 such that a 1 x [i]n[/i] rectangle can be tiled with 1 x 10 and 1 by 12 tiles. For each [i]n[/i], list a combination of 10's and 12's that work.
b) Compute the number of values of [i]n[/i], where [i]n[/i] is greater than or equal to 1000 and less than or equal to 2008, for which a 1 x [i]n[/i] rectangle can be tiles with 1 x 10 and 1 x 12 tiles.
c) Determine, with justification, a recursive formula for the number of ways to tile a 1 x [i]n[/i] rectangle with 1 x 2 and 1 x 3 tiles. Then compute the number of ways to tile a 1 x 17 rectangle.
4. For this question only, suppose that 1 x 1 tiles are gray and 1 x 2 tiles are colored in two ways: the right half white and the left half black or vice-versa. Thus there are two distinct types of 1 x 2 tiles.
a) Using there colored tiles, determine the number of distinguishable tilings for a 1 x 17 rectangle. Explain the method used (we always do that, right? =P).
b) Using these colored tiles, give an [u]explicit, closed-form[/u] formula in terms of [i]n[/i] for the number of distinguishable tilings of a 1 x [i]n[/i] rectangle. This is a non recursive formula. Justify your formula.
5. Find, with justification, the number of different ways to tile an 8 x 8 rectangle using 2 x 2 and 1 x 3 tiles. It is not necessary to use both types in a tiling.
------------------------------------------------------------- (This exists on the paper. Seriously.)
For the rest of the problems, you may assume the following [i]Spanning Theorem[/i]: A 1 x [i]n[/i] rectangle can be tiles with tiles of sizes 1 x [i]u[/i] and 1 x [i]v[/i] if and only if there exist nonnegative integers [i]t[/i][sub]1[/sub] and [i]t[/i][sub]2[/sub] such that [i]ut[/i][sub]1[/sub] + [i]vt[/i][sub]2[/sub] = [i]n[/i]. Let #[i]u, v[/i]# denote {[i]ut[/i][sub]1[/sub] + [i]vt[/i][sub]2[/sub] : [i]t1,t2[/i] nonnegative integers}. We express this theorem compactly as follows:
A 1 x [i]n[/i] rectangle can be tiled with sizes 1 x [i]u[/i] and 1 x [i]v[/i] if and only if [i]n[/i] is an element of #[i]u, v[/i]#.
We now consider a generalization of the Spanning Theorem:
6. a) Prove that if an [i]m[/i] x [i]n[/i] rectangle can be tiled with [i]u[/i][sub]1[/sub] x [i]v[/i][sub]1[/sub] and [i]u[/i][sub]2[/sub] x [i]v[/i][sub]2[/sub] tiles, then [i]m[/i] is an element of #[i]u[/i][sub]1[/sub], [i]u[/i][sub]2[/sub]# and n is an element of #[i]v[/i][sub]1[/sub],[i] v[/i][sub]2[/sub]#. (*)
b) Give an example to show that the condition [i]m[/i] is an element of #[i]u[/i][sub]1[/sub], [i]u[/i][sub]2[/sub]# and n is an element of #[i]v[/i][sub]1[/sub],[i] v[/i][sub]2[/sub]# is not sufficient to guarantee the existence of a tiling of an [i]m[/i] x [i]n[/i] rectangle with [i]u[/i][sub]1[/sub] x [i]v[/i][sub]1[/sub] and [i]u[/i][sub]2[/sub] x [i]v[/i][sub]2[/sub] tiles.
----------------------------------------------------------- (I don't know why this exists on the paper either.)
Because the generalized spanning condition (*) does not guarantee the existence of a tiling of a given rectangle using two given tiles, most of the rest of this power question is devoted to understanding when such a tiling is possible.
Below are two tilings of a 6 x 7 rectangle with combinations of 2 x 2 and 1 x 3 tiles:
Notice that in Tiling 1, the 6 x 7 rectangle has been effectively subdivided into two smaller rectangles of dimensions 6 x 4 and 6 x 3, each of which is tiled with copies of a single tile. To divide Tiling 2 into sub rectangles tiled with copies of a single tile would required seven sub rectangles: one 4 x 2, two 2 x 2's, three 2 x 3's and one 2 x 4. Call the complexity of a particular tiling the smallest number c, c greater than equal to 1, of sub rectangles, each tiled with copies of a single tile, into which a tiled rectangle can be divided. So Tiling 1 is of complexity 2 and Tiling 2 is of complexity 7.
In what follows, we will assume that no tile is a scaled copy of any other tile, that is, if one tile is u1 x v1 and the other tile is u2 x v2, we assume...
SORRY, I really need to get off now. I'll finish this tomorrow, and now, you can try the beginning.
Question
Guest
Well, I attended this years ARML competition, and I found the questions to be challenging, and the power round to be a lot of fun.
For those who don't know: arml.com
Basically, I'm posting this year's power round. I don't know the answers yet either, I'd like to see who can come up with something though... =D
ARML POWER QUESTION 2008 - Piles of Tiles
------------------------------------------------------------- (Rules of the power round at ARML(Applies here too, but not all of them(Specifically, only the bolded rules apply)))
The power question is worth 20 points. Each problem is worth 4 points. To receive full credit the presentation must be legible(not a problem here), orderly, clear, and concise. Even if not proved, earlier numbered items may be used in solutions to later numbered items but not vice versa. The pages submitted for credit should be NUMBERED IN CONSECUTIVE ORDER AT THE TOP OF EACH PAGE in what your team considers to be proper sequential order. PLEASE WRITE ON ONLY ONE SIDE OF THE ANSWER PAPERS.
Put the TEAM NUMBER (not the Team name) on the cover sheet used as the first page of the papers submitted. Do not identify the Team in any other way.
------------------------------------------------------------- (Some background information for the questions)
Given a rectangle whose dimensions are a x b, where a and b are integers, a tiling by rectangular tiles of dimensions u1 x v1, u2 x v2, etc., where all dimensions are integers, is an arrangement of tiles that fill the rectangle with no gaps and no overlaps. The edges of the tiles are parallel to the sides of the rectangle. For example, some of the ways to tiles a 4x4 rectangle with 2 x 2 and 1 x 4 tiles would be to use four of either tile shown by the left two diagrams or two of each as shown by the right two diagrams:
((Sorry, I'm too lazy to upload an image. For each 'rectangle' lines indicate the actual lines that are drawn in and spaces are used to indicated the grid, unless filled in by a line.))
A [i]u[/i] x [i]v[/i] tile has a height of [i]u[/i] and a width of [i]v[/i]. The diagram shows a 2 x 3 tile on the left and a 3 x 2 tile on the right. Tiles cannot be rotated into different orientations and two [i]u x v[/i] are indistinguishable. As example of different tiling, there are two ways to tile a 1 x 3 rectangle with a 1 x 1 tile and a 1 x 2 tile---the 1x1 tile can go to the left or to the right of the 1 x 2 tile. Let S([i]n[/i]) and |S([i]n[/i])| represent the set of tilings of a 1 x [i]n[/i] rectangle and the number of such tilings respectively.
------------------------------------------------------------- (Now the actual questions.)
1. a) Compute the number of ways a 1 x 4 rectangle can be tile with 1 x 1 and 1 x 2 tiles.
b) Give two different tilings of a 12 x 15 rectangle with combinations of 2 x 4 and 3 x 3 tiles.
c) Prove that it is impossible to tile an 80 x 80 rectangle with tiles of sizes 3 x 11 and 4 x 15.
2. a) For [i]n[/i] that is an element of {1, 2, ..., 10}, compute the number of ways to tile a 1 x [i]n[/i] rectangle with tiles of sizes 1 x 1 and 1 x 2 tiles. Give your answers in a table.
b) Determine, with proof, a recursive formula to compute the number of ways to tile a 1 x [i]n[/i] rectangle with 1 x 1 and 1 x 2 tiles. use the formula to compute the number of ways to tile a 1 x 17 rectangle.
3. a) In a table, list all values of [i]n[/i] less than or equal to 40 such that a 1 x [i]n[/i] rectangle can be tiled with 1 x 10 and 1 by 12 tiles. For each [i]n[/i], list a combination of 10's and 12's that work.
b) Compute the number of values of [i]n[/i], where [i]n[/i] is greater than or equal to 1000 and less than or equal to 2008, for which a 1 x [i]n[/i] rectangle can be tiles with 1 x 10 and 1 x 12 tiles.
c) Determine, with justification, a recursive formula for the number of ways to tile a 1 x [i]n[/i] rectangle with 1 x 2 and 1 x 3 tiles. Then compute the number of ways to tile a 1 x 17 rectangle.
4. For this question only, suppose that 1 x 1 tiles are gray and 1 x 2 tiles are colored in two ways: the right half white and the left half black or vice-versa. Thus there are two distinct types of 1 x 2 tiles.
a) Using there colored tiles, determine the number of distinguishable tilings for a 1 x 17 rectangle. Explain the method used (we always do that, right? =P).
b) Using these colored tiles, give an [u]explicit, closed-form[/u] formula in terms of [i]n[/i] for the number of distinguishable tilings of a 1 x [i]n[/i] rectangle. This is a non recursive formula. Justify your formula.
5. Find, with justification, the number of different ways to tile an 8 x 8 rectangle using 2 x 2 and 1 x 3 tiles. It is not necessary to use both types in a tiling.
------------------------------------------------------------- (This exists on the paper. Seriously.)
For the rest of the problems, you may assume the following [i]Spanning Theorem[/i]: A 1 x [i]n[/i] rectangle can be tiles with tiles of sizes 1 x [i]u[/i] and 1 x [i]v[/i] if and only if there exist nonnegative integers [i]t[/i][sub]1[/sub] and [i]t[/i][sub]2[/sub] such that [i]ut[/i][sub]1[/sub] + [i]vt[/i][sub]2[/sub] = [i]n[/i]. Let #[i]u, v[/i]# denote {[i]ut[/i][sub]1[/sub] + [i]vt[/i][sub]2[/sub] : [i]t1,t2[/i] nonnegative integers}. We express this theorem compactly as follows:
A 1 x [i]n[/i] rectangle can be tiled with sizes 1 x [i]u[/i] and 1 x [i]v[/i] if and only if [i]n[/i] is an element of #[i]u, v[/i]#.
We now consider a generalization of the Spanning Theorem:
6. a) Prove that if an [i]m[/i] x [i]n[/i] rectangle can be tiled with [i]u[/i][sub]1[/sub] x [i]v[/i][sub]1[/sub] and [i]u[/i][sub]2[/sub] x [i]v[/i][sub]2[/sub] tiles, then [i]m[/i] is an element of #[i]u[/i][sub]1[/sub], [i]u[/i][sub]2[/sub]# and n is an element of #[i]v[/i][sub]1[/sub],[i] v[/i][sub]2[/sub]#. (*)
b) Give an example to show that the condition [i]m[/i] is an element of #[i]u[/i][sub]1[/sub], [i]u[/i][sub]2[/sub]# and n is an element of #[i]v[/i][sub]1[/sub],[i] v[/i][sub]2[/sub]# is not sufficient to guarantee the existence of a tiling of an [i]m[/i] x [i]n[/i] rectangle with [i]u[/i][sub]1[/sub] x [i]v[/i][sub]1[/sub] and [i]u[/i][sub]2[/sub] x [i]v[/i][sub]2[/sub] tiles.
----------------------------------------------------------- (I don't know why this exists on the paper either.)
Because the generalized spanning condition (*) does not guarantee the existence of a tiling of a given rectangle using two given tiles, most of the rest of this power question is devoted to understanding when such a tiling is possible.
Below are two tilings of a 6 x 7 rectangle with combinations of 2 x 2 and 1 x 3 tiles:
| | | | | | | |
--- --- ---- --- --- ---
| | | | | | | |
---- --- --- --- --- --- ---- ---- --- --- --- --- --- ----
| | | | | | | |
--- --- ---- --- --- ---
| | | | | | | |
---- --- --- --- --- --- ---- ---- --- --- --- --- --- ----
| | | | | | | |
--- --- ---- ---- --- ---
| | | | | | | |
---- --- --- --- --- --- ---- ---- --- --- --- --- --- ----
Notice that in Tiling 1, the 6 x 7 rectangle has been effectively subdivided into two smaller rectangles of dimensions 6 x 4 and 6 x 3, each of which is tiled with copies of a single tile. To divide Tiling 2 into sub rectangles tiled with copies of a single tile would required seven sub rectangles: one 4 x 2, two 2 x 2's, three 2 x 3's and one 2 x 4. Call the complexity of a particular tiling the smallest number c, c greater than equal to 1, of sub rectangles, each tiled with copies of a single tile, into which a tiled rectangle can be divided. So Tiling 1 is of complexity 2 and Tiling 2 is of complexity 7.
In what follows, we will assume that no tile is a scaled copy of any other tile, that is, if one tile is u1 x v1 and the other tile is u2 x v2, we assume...
SORRY, I really need to get off now. I'll finish this tomorrow, and now, you can try the beginning.
Link to comment
Share on other sites
12 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.