How can the minimum diagonal be used to solve 6c?

[Gib Z]

[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 that's the smallest diagonal sum.

Dont know where to start for q5, but 6C is the most urgent one. Thanks guys

 

[VietDao29]

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.

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

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.

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

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 W_{k - 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 W_{k - 3} ways to make such arrangement.

...

Case k - 1: Only one style 2 square, it locates at the second, and third tiles. There is W₁ = 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 W₀ = 1. So there are W₀ to make such arrangement.

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

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 .

Btw, the last 2 parts are pretty much the same. .

 

[Gib Z]

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?

 

[VietDao29]

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?

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 W_{t - 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 W_{t - 3} ways.

...

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

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

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

$$W_k = 1 + \sum_{i = 0} ^ {k - 2} W_i , \ \ \ \ k \geq 2$$


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

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

 

[Office_Shredder]

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

 

[Gib Z]

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 haven't given my fullest attention and i am really sorry for that, I am 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 won't work for when 11 is on the top left square, but haven't made any real progress...

 

[tim_lou]

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...

 

[tim_lou]

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.

 

[VietDao29]

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 haven't given my fullest attention and i am really sorry for that, I am sure it was a really great solution VietDao :)

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

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 :(!

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. I cannot imagine me holding a multi-variable calculus book at 15, even in my best dreams.

 

[NateTG]

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.