Challenge Basic Math Challenge - June 2018

  • Thread starter QuantumQuest
  • Start date
  • Featured
New perspective?
Attempting to find a solution to the 5. problem you are probably going to encounter the problem of having to fit the bricks vertically.
If you fit them vertically you are bound to be stuck with the bottom 2 lines that can't have their bricks vertical (since you can't fit a 4 tall brick in a 2 tall space).

Therefore you can attempt to fit the top area with the use of vertical ones and at my best I could fit 36 bricks in a 6 x 4 x 6 in the x, y and z axis (y being the vertical axis).
You are left with the bottom 6 x 2 x 6 area in which you need to fit 17 bricks, put down horizontally since the bricks are too tall to fit in the area vertically.
For that you need a 6 x 1 x 6 design that can fit 8.5 bricks, and it is not possible to half the bricks so that one is ruled out, no matter the design you come up with.

The second design would be a design that encorporates all bricks laid down horizontally, without vertical bricks.
A 6 x 1 x 6 design (by the x y z axis) multiplied by 6 times, atop each other.
In the 1 tall area, you need to fit 53 bricks / 6 = 8.83 bricks per area, therefore this design wouldn't work either because you may not split the bricks.

I believe that you may not fit 53 bricks that are 1 x 1 x 4 into a 6 x 6 x 6 area.

I can provide designs I had mentioned, and I can highlight the mathematical part if needed.
 
32,678
8,551
@FelixLudi: You don't exclude all options that way.

My previous approach: Consider this hint given: If you put 2x1 blocks on a chess board, then you will use as many white as black squares. Any board that has more white than black squares or vice versa cannot be fully covered.

To apply this to 4x1 blocks in two dimensions, we can use 4 colors (called 0,1,2,3), where coordinate (x,y) gets the color "x+y mod 4". Every block will occupy one spot of each color. By counting (or by putting imaginary blocks on most of the grid) we see that color 0 has 9 fields, color 1 has 10, color 2 has 9 and color 3 has 8. We can put at most 8 blocks in the 6x6 grid, four spots have to stay free.

Extending this to three dimensions we assign the color "x+y+z mod 4". You can see that e.g. x=2 to 5 makes groups of 4, y=2 to 5 of the remaining spots make groups, and z=2 to 5 make groups as well. Now we found 52 groups. That leaves a 2x2x2 block where we have to evaluate the colors: Color 0 has the spot (0,0,0), while color 1 has (0,0,1), (0,1,0), (1,0,0), color 2 has (0,1,1), (1,1,0), (1,0,1) and color 3 has (1,1,1). This means we have 53 spots with color 0 and 3 respectively and 55 with colors 1 and 2. We showed that you cannot fit 54 blocks in, but 53 is not ruled out.
 
@FelixLudi: You don't exclude all options that way.

My previous approach: Consider this hint given: If you put 2x1 blocks on a chess board, then you will use as many white as black squares. Any board that has more white than black squares or vice versa cannot be fully covered.

To apply this to 4x1 blocks in two dimensions, we can use 4 colors (called 0,1,2,3), where coordinate (x,y) gets the color "x+y mod 4". Every block will occupy one spot of each color. By counting (or by putting imaginary blocks on most of the grid) we see that color 0 has 9 fields, color 1 has 10, color 2 has 9 and color 3 has 8. We can put at most 8 blocks in the 6x6 grid, four spots have to stay free.

Extending this to three dimensions we assign the color "x+y+z mod 4". You can see that e.g. x=2 to 5 makes groups of 4, y=2 to 5 of the remaining spots make groups, and z=2 to 5 make groups as well. Now we found 52 groups. That leaves a 2x2x2 block where we have to evaluate the colors: Color 0 has the spot (0,0,0), while color 1 has (0,0,1), (0,1,0), (1,0,0), color 2 has (0,1,1), (1,1,0), (1,0,1) and color 3 has (1,1,1). This means we have 53 spots with color 0 and 3 respectively and 55 with colors 1 and 2. We showed that you cannot fit 54 blocks in, but 53 is not ruled out.
So basically we can fit in 53 bricks in, but we now need to demonstrate a design that proves that?
 

fresh_42

Mentor
Insights Author
2018 Award
10,296
7,015
So basically we can fit in 53 bricks in, but we now need to demonstrate a design that proves that?
I don't know the correct proof, but I agree with
"No" is a valid answer if you can prove that they cannot fit.
I'm quite sure they cannot fit but the approaches I tried to prove it don't work (or work only in two dimensions).
Any design with 52 bricks won't leave you we with 4 free places in a row. But proofs along the line "... does not exist" are immanently hard to prove.
 
It's harder to prove that something isn't possible when it isn't, rather than it is to prove that it's possible when it is.
 

StoneTemplePython

Science Advisor
Gold Member
1,051
502
Any design with 52 bricks won't leave you we with 4 free places in a row.
This would seem to be a key insight to build a proof off of...

- - - -
Note that this is a B thread so there is some slack on proofs.

A couple other things I'd highlight:

1) this problem nicely illustrates a common phenomenon in math and computing in that jumping from ##2## dimensions to ##\geq 3## frequently causes an awful lot more difficulties than people imagine (e.g. 2-SAT vs 3-SAT is a big jump, 2-body problems vs n-body problems in physics and so on.)

2.) The chessboard problem I gave as a hint (albeit somewhat modified), used to be an interview problem in some employment circles but it got too well known so some people started asking questions like this one. A pretty awful thing to do in an on-site interview if you ask me, but an interesting question over coffee.
 
So on a 2d grid you basically have a 6 by 6 area (x,y).
A brick as said is 1 by 4 (x,y).

Just to be clear, I'm saying grid as area of space, brick as said brick and a block as a 1 by 1 space on the grid/area.

On such grid you may only fit 1 brick that is 4 blocks in the y axis, per 1 x axis.
(##6 / 4 = 1 + \frac{2}{4}##)
That leaves you with a 2 block gap per x axis.

If you fill the grid on the x axis you will be left with a 2 block gap per 1 x axis in which you can rotate the bricks (from ##(x,y) = (1,4)## to ##(x,y) = (4,1)##).
Doing will provide you with the ability to fit in 2 more bricks by the y axis leaving a 2 by 2 gap.

For the green area:
##(x,y) = ((1,1), (1,2), (1,3), ... , (5,3), (5,4), (6,1), (6,2), ... , (6,3), (6,4))##

For the red area:
##(x,y) = ((5,5), (5,6), (6,5), (6,6))##

Adding a 3rd dimension would simply mean repeating this design, in which state you would have the same problem of the gap as in the 2d design.
If you rotate the bricks again to fit them in you can fit at most 4 bricks in the red area, leaving you with a 2 x 2 x 2 area in which you can not fit more bricks.

In conclusion my answer would be that at most you can fit 52 bricks inside of the 6 x 6 x 6 area, but not 53.

Images are from a site named 3dslash.net
The program used to design is free, and is owned by the site.
 
32,678
8,551
So basically we can fit in 53 bricks in, but we now need to demonstrate a design that proves that?
No, it means we can easily fit in 52, and we cannot fit in 54, but the approach doesn't tell you anything about 53.
Adding a 3rd dimension would simply mean repeating this design
You don't have to! That is the point.
In 2 dimensions you can easily go through all cases, but in 3 dimensions this is very difficult. You can't just say "let's try to repeat the pattern - oh doesn't work - therefore no arrangement can work".

There are no images visible in your post.
 
If said design is the least space consuming and the most efficient one it is generally safe to say that there isn't another more efficient design. In any way possible, you will end up with 4 blocks that you can no longer form a row from.

Since the bricks can be put in any axis to form a 4 tall, 6 wide and 6 long area you can just work on a 6 x 2 x 6 design and attempt to figure that out.
Considering that the area is only 2 tall you can no longer stand the bricks upright and therefore it's the same as working on 2, 6 x 6 areas (2d perspective).
And we already established the design for the 2d design.

EDIT: I believe that the difference in working in 2d and 3d in this case atleast is the change of axis in said object (bricks). In 2d you can change it from x to y (and vice versa) but in 3d you have 3 possible options.
In a linear design (considering 6 x 6 x 6) I suspect that it's not of importance if you aligned them on a different axis (from 1 x 1 x 4 to 1 x 4 x 1 etc.). Correct me if I'm wrong though.

I had deleted the images last night but they didn't serve a real purpose since I got the point off.
 
32,678
8,551
If said design is the least space consuming and the most efficient one it is generally safe to say that there isn't another more efficient design.
You didn't show that it is the most efficient one overall.
you will end up with 4 blocks that you can no longer form a row from.
Showing that 4 blocks will be left is not sufficient, we have to show that 8 will be left.
Since the bricks can be put in any axis to form a 4 tall, 6 wide and 6 long area you can just work on a 6 x 2 x 6 design and attempt to figure that out.
No. There might be solutions to the 6x6x6 cube which don't have 6x2x6 as separable space.
 
Showing that 4 blocks will be left is not sufficient, we have to show that 8 will be left.
8 will be left yes, that was a mistake on my part of the math (an area of 2 x 2 x 2).
 

fresh_42

Mentor
Insights Author
2018 Award
10,296
7,015
Solution to #1.

a) Prove ##(e+x)^{e-x}>(e-x)^{e+x}## for ##0<x<e.##

We define
$$f\, : \,]0,e[ \longrightarrow \mathbb{R}\, , \,f(x):=(e-x)\log(e+x)-(e+x)\log(e-x)$$
and observe ##\lim_{x \searrow 0}f(x)=0\,.## Then
\begin{align*}
f\,'(x)&=\dfrac{e-x}{e+x}+\dfrac{e+x}{e-x}-\left(\log(e+x)+\log(e-x)\right)\\[6pt]
&=2\cdot \underbrace{\dfrac{e^2+x^2}{e^2-x^2}}_{>1}-\underbrace{\log(e^2-x^2)}_{<2}\\[6pt]
&> 0
\end{align*}
and ##f(x)>0\,##, resp. ##(e-x)\log(e+x)>(e+x)\log(e-x)\,## resp. ##(e+x)^{e-x}>(e-x)^{e+x}##

b) Show that for ##0 < b < a## we have
$$\dfrac{1}{a} < \dfrac{2}{a+b} < \dfrac{\log (a) - \log (b)}{a-b} < \dfrac{1}{\sqrt{ab}} < \dfrac{1}{b}$$
For ##x=\dfrac{a}{b}>1## we have
\begin{align*}
\log(x^2)&=2 \log(x)\\
&=2 \int_1^x \frac{1}{t}\,dt\\
&< \int_1^x \left(1+\frac{1}{t^2}\right)\,dt\\
&= x-\frac{1}{x}\\
&\text{or}\\
\log(x)&<\sqrt{x}-\frac{1}{\sqrt{x}}
\end{align*}
With ##\log(x)=\sum_{k=0}^\infty \frac{2}{2k+1}\left(\dfrac{x-1}{x+1}\right)^{2k+1}> 2\cdot\dfrac{x-1}{x+1}## we get
$$
2\dfrac{\frac{a}{b}-1}{\frac{a}{b}+1}=2\dfrac{a-b}{a+b}< \log(\frac{a}{b})=\log(a)-\log(b)<\sqrt{\frac{a}{b}}-\sqrt{\frac{b}{a}}=\dfrac{a-b}{\sqrt{ab}}
$$
c) Let ##f,g\, : \,[a,b]\longrightarrow \mathbb{R}## be two monotone integrable functions, either both increasing or both decreasing. Show that ##\int_a^bf(x)g(x)\,dx \ge \int_a^bf(x)\,dx \cdot \int_a^bg(x)\,dx##

We have ##\left(f(x)-f(y)\right)\left(g(x)-g(y)\right)>0## and therefore
\begin{align*}
\int_a^bf(x)g(x)\,dx +\int_a^bf(y)g(y)\,dy &\ge \\ \int_a^bf(x)\,dx \, \int_a^bg(y)\,dy &+ \int_a^bf(y)\,dy \, \int_a^bg(x)\,dx\\
&\text{or} \\
2 \int_a^bf(x)g(x)\,dx &\ge 2\int_a^bf(x)\,dx \, \int_a^bg(x)\,dx
\end{align*}
 
Last edited:

QuantumQuest

Science Advisor
Insights Author
Gold Member
838
431
Solution for Problem ##8##:

##f(x)## and ##g(x)## have ##M(x_0,f(x_0))## as a (common) point of contact if

##f(x_0) = g(x_0)## and ##f'(x_0) = g'(x_0)##.

We have ##f(x) = e^{-x}## so ##f'(x) = -e^{-x}## and ##g(x) = e^{-x}\cos x## so ##g'(x) = -e^{-x}\cos x - e^{-x}\sin x##.

We have to solve the system of equations

$$ \begin{cases}
f(x) = g(x)\\
f'(x) = g'(x)
\end{cases} \iff \begin{cases}
e^{-x} = e^{-x}\cos x\\
-e^{-x} = -e^{-x}\cos x - e^{-x}\sin x
\end{cases} \iff \begin{cases}
\cos x = 1\\
1 = \cos x + \sin x
\end{cases} \iff$$
$$\begin{cases}
\cos x = 1\\
\sin x = 0
\end{cases} \iff x = 2k\pi, k\in \mathbb{Z}$$

So, ##f## and ##g## are tangent to each other at points ##(2k\pi, e^{-2k\pi})\space\space k\in \mathbb{Z}##.
Now, one function that is tangent to ##f## and ##g## is the tangent line

##y = f(x_0) + f'(x_0)\cdot (x - x_0)##.

For ##x_0 = 2\pi##, ##f(x_0) = e^{-2\pi}##, ##f'(x_0) = -e^{-2\pi}##. So,

##y = e^{-2\pi} - e^{-2\pi} (x - 2\pi)##
 

StoneTemplePython

Science Advisor
Gold Member
1,051
502
Problem 5:

The answer is no. I think people have collectively figured this out, though explicitly partitioning the volume enclosed in the box to be like a chessboard ties out loose ends.
- - - -
similar to the chess board problem given as a hint, but with a 3rd dimension, suppose we have black and white cubes alternating each of size 2x2x2 -- this makes up the airspace inside the box. Without loss of generality suppose it is 14 black cubes and 13 white cubes. (Note ##3^3 = 27 = 14+13##.) All we've done so far is partition or 'tile' the volume of our 6x6x6 box in a way that looks like a chessboard.

Now whenever we place one of our 1x1x4 bricks into the box, half of it is in the space of a black cube and the other half in a white cube. The issue is that at best each 2x2x2 cube can be occupied by 4 bricks. This allows us to place 52 bricks in the box. However once we've done this we must have used up the 13 white cubes (i.e. ##4(13) =52##). Adding in the 53rd brick requires 1 free black cube (available) and 1 free white cube (which doesn't exist), hence packing 53 bricks in the box is impossible.
 
Last edited:

Want to reply to this thread?

"Basic Math Challenge - June 2018" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top