14
$\begingroup$

I've been given this task:

A unit square is cut into rectangles. Each of them is coloured by either yellow or blue and inside it a number is written. If the color of the rectangle is blue then its number is equal to rectangle’s width divided by its height. If the color is yellow, the number is rectangle’s height divided by its width. Let $x$ be the sum of the numbers in all rectangles. Assuming the blue area is equal to the yellow one, what is the smallest possible $x$?

I've came with the solution below: I've simply split the unit square in half and assigned the colors. The reasoning behind that is that I want to have the blue side as high as possible (to make the $x$ as low as possible) and the yellow side as wide as possible (for the same reason). I didn't divide the square into rectangles with infinitely small height or width, because no matter how small they are, they eventually add up and form the two big rectangles that are on my picture.

I feel my solution is wrong though, because it is stupidly easy (you have to admit, that often means it's wrong). Is there anything I'm missing here? enter image description here

$\endgroup$
8
  • 2
    $\begingroup$ Even if it is the right solution (it may or may not be; I'm not sure), the real challenge is in proving it is right., That's not necessarily "stupidly easy" even if the configuration is simple. $\endgroup$ – hmakholm left over Monica Jan 3 '16 at 13:06
  • $\begingroup$ Oh, didn't even think about that. I don't have any idea about how should I prove it, but at least now it feels more challenging. $\endgroup$ – Eugleo Jan 3 '16 at 13:11
  • $\begingroup$ It's easy to see that sum of the yellow numbers is greater than $1/2$ and the same for the blue numbers; so the total sum will be always greater than $1$. However I have the feeling that one of the two sums will be always greater than $2$, but I don't know how to prove it yet. $\endgroup$ – mrprottolo Jan 3 '16 at 20:48
  • $\begingroup$ there's a connection b/w rectangular tillings and current flow on planar electrical networks, the ratio plays role of conductivity... $\endgroup$ – DVD Jan 6 '16 at 1:05
  • 2
    $\begingroup$ Just to make sure I understand the problem correctly -- does the "width" and "height" of the rectangles denote their horizontal and vertical size? (I initially interpreted them as the "smaller" and "greater" dimension, irrespective of the rectangle's orientation... which changes the problem quite a bit :-) ). $\endgroup$ – Peter Košinár Jul 27 '16 at 15:51
2
$\begingroup$

Here is the full solution. The answer is, indeed, $5/2$. An example was already presented by the OP. Now we need to prove the inequality.

First of all we notice that for any color (blue or yellow) the sum of height/width (or width/height) ratios is always at least $1/2$.

Indeed, since all dimensions do not exceed $1$, we have (e.g., for blue color) $$ \sum \frac{w_i}{h_i} \geqslant \sum w_i h_i = \frac 12 \,. $$ as the final sum is the total area of all blue rectangles.

Second, we observe that either the blue rectangles connect the left and the right sides of the square, or the yellow rectangles connect the top and the bottom sides. We leave that as an exercise for the readers :) (Actually, as you will see below, it would suffice to show that either the sum of all blue widths or the sum of all yellow heights is at least $1$.)

Without loss of generality, assume that the blue rectangles connect the lateral sides of the large square. Then we intend to prove that $$ \sum \frac{w_i}{h_i} \geqslant 2 \,, $$ where the summation is done over the blue squares. Combining that with the inequality $\sum h_i/w_i \geqslant 1/2$ for the yellow squares we will have the required result, namely that the overall sum is always at least $5/2$.

Since the projections of the blue squares onto the bottom side must cover it completely, we have $\sum w_i \geqslant 1$. We also have $\sum w_ih_i = 1/2$. Now all we need is the following fact.

Lemma. Two finite sequences of positive numbers $\{w_i\}$ and $\{h_i\}$, i = $1$, ... , $n$ are such that $$ \sum w_i = W, \qquad \sum w_ih_i = S \,. $$ Then $$ \sum \frac{w_i}{h_i} \geqslant \frac{W^2}S \,. $$

Proof. We will use the well-known Jensen's inequality (which follows from the geometric convexity of the area above the graph of any convex function) for function $f(x) = 1/x$. That gives us $$ \sum \frac{w_i}W f(h_i) \geqslant f \left( \sum \frac{w_i}W h_i \right) \,. $$ In other words $$ \frac1W \sum \frac{w_i}{h_i} \geqslant \frac1{\sum \frac{w_i}W h_i } = \frac{W}{\sum w_i h_i} = \frac WS \,. $$ and the required inequality immediately follows. $\square$

Applying this lemma to our case where $W \geqslant 1$ and $S = 1/2$ completes our solution.

$\endgroup$
1
  • $\begingroup$ Thanks! I almost forgot I asked this question 4 years ago. $\endgroup$ – Eugleo Sep 18 '20 at 22:13
1
$\begingroup$

Assuming that width and height refer to the 'longer' and 'shorter' dimension respectively


Why does this assumption seem what the OP had in mind?

Because his "solution" implicitly takes this to be true. If the OP has $X$ and $Y$ directions in mind, he would have written the same number on both of the rectangles in his solution.


Let number of blue triangles be $p$ and number of yellow triangles be $q$. The number written inside a blue triangle will always be greater than or equal to $1$. Hence,

$$ x \geq p $$

You have already found a solution for which $x=2.5$.

Also, this is the best solution for the case $p=1$

Hence we need to only examine the case $p=2$ since for $p>2$, $x$ will be greater than $2.5$.

Again, we have to prove all the cases when $p=2$, ie, $q$ can be any finite number while $p=2$.


Case 1

$q$ is $I$.

This means the unit square is divided into $3$ rectangles. The only way in which we can divide a square into 3 rectangle is given below. Three rectangles are named accordingly. Notice that there will be two more sub cases. One where the $q$ rectangle is upright and another where the $q$ rectangle is either the one named or $III$. $q$ cannot be $II$ since then its area will always be less than $0.5$.

Unit square partitioned into three rectangles

Note that $b \leq 0.5$ in the above image.

Case 1.1

$q$ rectangle is upright. Here it is trivial that $a=0.5$ (by equating the areas). Hence, $x= 0.5 + \frac{1}{2b} + \frac{1-b}{\frac{1}{2}} = 2.5 + \frac{1}{2b} + 2b$

Hence this case is proved since it is trivial that $x \geq 2.5$. In fact, we have another possible solution candidate when $b=0.5$.

Case 2

$q$ is $III$.

By equating area of blue rectangles equal to $0.5$, we get,

$$ a+b-ab=0.5 $$

or,

$$ a=\frac{0.5-b}{1-b} $$

The number written on triangle $I$ will be $\frac{1}{a}$.

The number written on triangle $II$ will depend on whether $1-a$ or $b$ is greater. Keep in mind that $b \leq 0.5$. This graph tells us that $1-a \geq b$. Hence, the number written on triangle $II$ will be $\frac{1-a}{b}$.

The number on triangle $III$ will again depend on which dimension is greater. This graph tells us that

$1-a \geq 1-b$ when $1-b \leq 0.709$ or $0.2929 < b < 0.5$

In such a case, the number written will be $\frac{1-b}{1-a}$.

This graph tells is that in such a case $x \geq 6.518$. Not a problem!

When $0 < b < 0.2929$, then the number written will be $\frac{1-a}{1-b}$.

This graph tells is that in such a case $x \geq 6.775$. Not a problem again!

Hence all the cases when $p=2$ and $q=1$ are proved!

I am trying to prove this for higher cases of $q$, any ideas anyone?

$\endgroup$
2
  • $\begingroup$ I think your interpretation of width and height is not correct. Width refers to the $x$ direction and height refers to the $y$ direction for all rectangles. $\endgroup$ – Ross Millikan Jul 27 '17 at 19:04
  • $\begingroup$ The numbers written in the two rectangles are $\frac X Y$ for the blue and $\frac Y X$ for the yellow, as they should be. Your interpretation is incorrect. $\endgroup$ – Jens Jul 28 '17 at 19:31
0
$\begingroup$

We cannot assume that height and width refer to the longer and shorter sides. Here is a counter example. Let us denote our unit square by $K$. Consider a square with dimensions $\frac1{\sqrt2} \times \frac1{\sqrt2}$ with its upper left corner coinciding with the upper left corner of $K$, and paint it blue. Split the remaining part of $K$ into two yellow rectangles---one of them with width $1$ and height $1-\frac1{\sqrt2}$ whose bottom side coincides with the bottom side of $K$, and the other one, sharing its top right corner with the corresponding corner of $K$, has width $1-\frac1{\sqrt2}$ and height $\frac1{\sqrt2}$. Then the sum of longer/shorter ratios for the blue squares is $1$, and the sum of the shorter/longer ratios for the yellow squares is $$ \frac{1-\frac1{\sqrt2}}{1} + \frac{1-\frac1{\sqrt2}}{\frac1{\sqrt2}} = 1-\frac1{\sqrt2} + \sqrt{2}-1 = \frac1{\sqrt2} \approx 0.707... $$ Thus, the overall sum of the numbers will be 1.707..., which is quite noticeably less than $2.5$.

However, if we follow exactly the given conditions: blue = width/height, yellow = height/width, then we obtain the following sum $$ 1 + \left( 1-\frac1{\sqrt2} + \frac{\frac1{\sqrt2}}{1-\frac1{\sqrt2}} \right) = 3 + \frac1{\sqrt2} \approx 3.707... > 2.5 $$

$\endgroup$
1
  • $\begingroup$ However, the following is true: if we label each blue rectangle with longer/shorter ratio, and every yellow rectangle with shorter/longer ratio, then the sum of all numbers is at least $b + 0.5$ where $b$ is the number of blue rectangles. That can be easily proved by considering areas of yellow squares (sum of the numbers for the blue squares is obviously always at least $b$). $\endgroup$ – JimT Sep 7 '20 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.