1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenging Squares and Tiles

  1. Jun 10, 2007 #1

    Gib Z

    User Avatar
    Homework Helper

    [img=http://img527.imageshack.us/img527/9639/96652845hm1.th.jpg]

    I can do 6.a) and b) but still need to know how to do c). I've done half of the question because I have an example of one where the diagonal adds up to 33, but I can't prove thats the smallest diagonal sum.

    Dont know where to start for q5, but 6C is the most urgent one. Thanks guys
     
  2. jcsd
  3. Jun 10, 2007 #2

    VietDao29

    User Avatar
    Homework Helper

    Woooowwww, must say that they're 2 very interesting problems. :!!) :!!)

    Spent like 2 hours working on the #5, the Tilings one, =.=" and finally, I got it. Yyyyeaaaahhh. :biggrin:

    Well, it's definitely not the most elegant way to go about solving this problem, but well, it's one way to go. o:)

    Here's my approach.

    I attach 2 pictures. The first one show the only two styles to make up a 2 x 2 square: Style 1 on the left, and style 2 to the right.

    And picture 2 shows all possible cases to makeup a 2 x k rectangle, divided into k cases.

    [​IMG]

    Say, we define Wk to be all the possible ways to make a rectangular strip of 2 x k. We'll now find the relation between Wk, and those that goes before it, i.e Wk - 1, Wk - 2, ..., and W1.

    We'll divide it into k separate cases, base on the last style 2 square seen on the whole block of tiles.

    Case 1: No style 2 square can be seen. Obviously, there's only one way to make up the 2 x k rectangle, with no style 2 square.

    Case 2: The last style 2 square lies at the end of the whole block. Since the last 2 tiles are fixed, the total possible ways to make such arrangement would be all the possible ways to build up the (k - 2) tiles that stand before it. So there are Wk - 2 ways to make such arrangement.

    Case 3: The last style 2 square locates at the (k - 2)th, and (k - 1)th tiles of the whole block. The last 3 tiles are fixed, so there are Wk - 3 ways to make such arrangement.

    ...

    Case k - 1: Only one style 2 square, it locates at the second, and third tiles. There is W1 = 1 way to make such arrangement.

    Case k: Only one style 2 square, it locates at start of the whole block. There is 1 way to make such arrangement. To make it more convenient, we may define W0 = 1. So there are W0 to make such arrangement.

    Summing all the cases above, in general, we have the formula:
    [tex]W_k = 1 + \sum_{i = 0} ^ {k - 2} W_i , \ \ \ \ k \geq 2[/tex]

    Hopefully, you can go from here, right? :)

    Just wonder if it's clear enough? It's well past mid-night over here, and I am in a little bit rush. I need to get some sleep now, feeling somewhat spinned arround, and arround :frown:.

    Btw, the last 2 parts are pretty much the same. :smile:.
     
    Last edited: Jun 11, 2007
  4. Jun 11, 2007 #3

    Gib Z

    User Avatar
    Homework Helper

    Maybe its my throbbing headache but I am quite lost on that one...PIC 2 makes it seem like there are k ways of arranging k tiles...but for 5 we can arrange 8 ways...If you look at the diagram on the original question again, are you sure you accounted for that arrangements like the one of the far right bottom one?
     
  5. Jun 11, 2007 #4

    VietDao29

    User Avatar
    Homework Helper

    Oh, I must admit that the drawing is a little bit confusing. >.< I have edited the post to make it a little bit clearer.

    Ok, about the first case again. There's no style 2 square. Obviously, there's only 1 way to make such arrangement, right?

    The 2nd case:
    The last style 2 square can be spotted at the end of the block. That means the last 2 tiles are fixed, while the rest (k - 2) tiles are not. The total ways to construct a 2 x k rectangle like this is the same as the total ways to construct the 2 x (k - 2) rectangle that stands before the last 2 tiles, since the last 2 tiles are fixed. So there'll be Wt - 2 ways.


    The 2nd case:
    The last style 2 square can be spotted at the (k -1)th, and the (k - 2)th tiles of the block. That means the last 3 tiles are fixed, and the rest (k - 3) tiles are not. The total ways to construct a 2 x k rectangle like this is the same as the total ways to construct the 2 x (k - 3) rectangle that stands before the last 3 tiles, since the last 3 tiles are fixed. So there'll be Wt - 3 ways.

    ...

    And the k-th case, there's only 1 way to make such arrangement.

    So, summing all the above, we'll have:
    [tex]W_k = 2 + \sum_{i = 1} ^ {k - 2} W_i , \ \ \ \ k \geq 3[/tex]

    If we define W0 to be 1, the above formula can be re-written as:

    [tex]W_k = 1 + \sum_{i = 0} ^ {k - 2} W_i , \ \ \ \ k \geq 2[/tex]


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

    For 2 x 5 rectangle, we have the following 5 cases:

    [​IMG]
     
  6. Jun 11, 2007 #5

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    6 (c) is easier than it seems... if 1 is on a black square, what color is 2 on? Extend this to form a pattern telling whether a number is on black or white given whether it's even or odd. Then, if we know 1,3,5,7,9 aren't on the diagonal, what would be the next smallest possible sum of numbers be on the diagonal
     
  7. Jun 12, 2007 #6

    Gib Z

    User Avatar
    Homework Helper

    Ok I don't understand how to generate the number of possible combinations for each case eg case 1 has 1, case 2 had 3 ...and perhaps i havent given my fullest attention and i am really sorry for that, im sure it was a really great solution VietDao :)

    I'm getting the solutions off a friend whose already done them, but I wanted to ask here first because its quite an embarrassment at school >.< The kid whose done multivariable calculus can't do a question that was given to people learning the sine rule :(!!!

    And Office_Shredder - umm 1,3,5,7,11 ? I've tried all day fiddling at school, i can sort of think abit of why they combination wont work for when 11 is on the top left square, but havent made any real progress...
     
  8. Jun 12, 2007 #7
    25 must appear on the left side of the diagonal, or right side of the diagonal, or on the diagonal. if it lies on the diagonal, the sum is greater than 33. If not, then there must be a path from the diagonal to the block that is labeled 25. from there, the sum is greater or equal to 33.

    edit: confused myself with 33 and 25...
     
    Last edited: Jun 12, 2007
  9. Jun 12, 2007 #8
    for problem 5, grab a book on Fibonacci number and linear recursion. or just do some quick readings on wikipedia.

    ps: GibZ, if you want to challenge yourself in the world of problem solving, I recommend you to go to www.artofproblemsolving.com and check out the forum. They have tons of people posting problems daily from easy to incredibly hard problems, plus there are plenty of smart people solving these problems and posting solutions online. It is a great way to learn.
     
    Last edited: Jun 12, 2007
  10. Jun 12, 2007 #9

    VietDao29

    User Avatar
    Homework Helper

    That's okay. I don't think my explanation is very clear though. :frown: It's sometimes pretty hard for me to write down what I think, due to my lack of terminology, and vocabulary. :cry:

    Well, I'd love to hear his approach. Mine is way too messy. >"<

    And, oh, btw, learning muti-variable calculus at 15 is just incredible. :bugeye: :wink: I cannot imagine me holding a multi-variable calculus book at 15, even in my best dreams.
     
    Last edited: Jun 12, 2007
  11. Jun 12, 2007 #10

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    For question 5:
    If you know how many 2xn rectangles there are, how many 2x(n+1) rectangles are there that end in a vertical tile?

    How many 2xn rectangles are there that end in a vertical tile?

    For question 6:
    The trick to proving 6c should be clear from 6b.
    Big hint: If you have the minimum diagonal, one half of the square will always contain 9,11,13, and 15.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Challenging Squares and Tiles
  1. Area of tiling (Replies: 2)

Loading...