Basic Math Challenge - June 2018

[QuantumQuest]

And yes I'm a U.S student- a horrendous public education, but that's no excuse for me. My lack of mathematical skills is my own doing as I didn't care in the least for it when I was in high school. Trying to make up for that now!
I think these problems are really great and helpful and I'm going to spend some time on trying to understand them so I can have meaningful participation down the road.

Well, I don't live in US but as far as I know, public education is not horrendous compared to other countries in the world. What I can tell you for sure is that at College and University level is great and personally I really owe a lot of my knowledge in US resources - online classes, books, University resources, just to name a few of them. In any case, it's really good that you recognize that it is essentially your efforts that can make the difference - I was in this same position in my country as I was finishing High School, when I prepared on my own for what was missing in my knowledge in order to have a good head start when getting to University.

 

[fresh_42]

Thread is now open to all. We have still four unsolved problems: 1,2,5,8.

So Homework Helpers, Science Advisors and Mentor can you help?

 

[Phylosopher]

5.5. Can one pack 53 bricks, each of dimension 1 x 1 x 4\text{1 x 1 x 4} into a 6 x 6 x 6\text{6 x 6 x 6} box?
(by @StoneTemplePython)

Thread is now open to all. We have still four unsolved problems: 1,2,5,8.

So Homework Helpers, Science Advisors and Mentor can you help?

I always wanted to solve such problem. Mr. fresh_42 suggested that this is a combinatorics problem. I didn't studied such problems before. From my own search on the web, this is called an optimization problem.

At first I tried to solve it directly by thinking. I remained with one brick and a volume of a brick if I am not mistaken (If I remember correctly, I had a volume of a brick but not its shape). I was going to make a program that solves the problem, but I felt Like cheating ^^".

since it is Jun 16. Can anyone give us a hint?

 

[PeroK]

$2.$ One card out of a deck has been lost. The other 51 cards are repeatedly shuffled and then thirteen cards are dealt, face up. The cards are 2 spades, 3 clubs, 4 hearts, and 4 diamonds. What is the chance that the missing card is (a) spade, (b) club, (c) heart, (d)diamond $\space$ $\space$ (by @StoneTemplePython)

Spoiler

We can use the idea of relative frequecies. If we repeat the experiment many times, then the missing card will initially be a S, C, H or D with equal frequency. So, we need to calculate how often in each of these cases we get 2S, 3C, 4H and 4D.

First, we can simplify things by noting that the frequency of getting those cards exactly in that order is related to the frequency of getting those cards in any order by a common factor (regardless of which card is missing). The common factor is $\binom{13}{2} \binom{11}{3} \binom{8}{4}$

Second, the frequency is related by another common factor in all cases of $\frac{1}{51} \frac{1}{50} \dots \frac{1}{39}$.

Omitting these common factors, we have the frequency of being dealt SSCCCHHHHDDDD:

If a Spade is missing: $12 \times 11 \times 13 \times 12 \times 11 \times 13 \times 12 \times 11 \times 10 \times 13 \times 12 \times 11 \times 10 = 13^3 \times 12^4 \times 11^4 \times 10^2$

If a Club is missing: $13 \times 12 \times 12 \times 11 \times 10 \times 13 \times 12 \times 11 \times 10 \times 13 \times 12 \times 11 \times 10 = 13^3 \times 12^4 \times 11^3 \times 10^3$

If a Heart is missing: $13 \times 12 \times 13 \times 12 \times 11 \times 12 \times 11 \times 10 \times 9 \times 13 \times 12 \times 11 \times 10 = 13^3 \times 12^4 \times 11^3 \times 10^2 \times 9$

And the same for Diamonds.

Finally, taking out the common factors again we get the relative frequencies:

If a Spade is missing: $11$

If a Club is missing: $10$

If a Heart is missing: $9$

If a Diamond is missing: $9$

This means that out of every $39$ times we get dealt the cards 2S, 3C, 4H and 4D: $11$ times a Spade was the missing card, $10$ times the Club was the missing card etc.

Given we have been dealt 2S, 3C, 4H and 4D, therefore:

The probability a Spade is the missing card is $11/39$; a Club the missing card $10/39$; and a Heart or Diamond each $9/39$.

 

[StoneTemplePython]

I always wanted to solve such problem. Mr. fresh_42 suggested that this is a combinatorics problem. I didn't studied such problems before. From my own search on the web, this is called an optimization problem.

At first I tried to solve it directly by thinking. I remained with one brick and a volume of a brick if I am not mistaken (If I remember correctly, I had a volume of a brick but not its shape). I was going to make a program that solves the problem, but I felt Like cheating ^^".

since it is Jun 16. Can anyone give us a hint?

I don't think writing a program would get credit, but to be honest if you make one, and you don't mind posting code at the end of the month, I'd be interested in seeing it if you're ok with sharing.

There's a few different ways to view the problem. Let me think on possibility of a hint.

 

[StoneTemplePython]

I always wanted to solve such problem. Mr. fresh_42 suggested that this is a combinatorics problem. I didn't studied such problems before. From my own search on the web, this is called an optimization problem.

At first I tried to solve it directly by thinking. I remained with one brick and a volume of a brick if I am not mistaken (If I remember correctly, I had a volume of a brick but not its shape). I was going to make a program that solves the problem, but I felt Like cheating ^^".

since it is Jun 16. Can anyone give us a hint?

This is a 3-D problem. Maybe it is tough... so consider a simpler, 2-D problem first. For the hint, I'll give a suggestive 2-D problem:

consider packing $\text{1 x 2}$ blocks on an 8 x 8 chessboard that has two squares at opposite corners removed. Can you pack 31 blocks into this slightly modified board? Why or why not?

It then takes a bit of visualization to make the leap from 2-D to 3-D.

 

[pbuk]

As its nearly the end of June, I'll bite...

consider packing $\text{1 x 2}$ blocks on an 8 x 8 chessboard that has two squares at opposite corners removed. Can you pack 31 blocks into this slightly modified board? Why or why not?

No, because each block covers 1 black square and 1 white square but the modified board has 32 black squares and 30 white squares (or vice versa).

It then takes a bit of visualization to make the leap from 2-D to 3-D.

A bigger leap than I have managed in the last fortnight...

 

[StoneTemplePython]

As its nearly the end of June, I'll bite...

No, because each block covers 1 black square and 1 white square but the modified board has 32 black squares and 30 white squares (or vice versa).

A bigger leap than I have managed in the last fortnight...

I think we're posting solutions to unsolved problems mid-month, so stay tuned.

 

[FelixLudi]

$5.$ Can one pack 53 bricks, each of dimension $\text{1 x 1 x 4}$ into a $\text{6 x 6 x 6}$ box?
(by @StoneTemplePython)

Spoiler

Assuming that each brick is $1m * 1m * 4m$, and the box is $6m * 6m * 6m$;
The volume taken by 1 brick is equal to $1m * 1m * 4m = 4m^3$ and the volume of said box would be $6m * 6m * 6m = 216m^3$, then;
$216m^3 / 4m^3 = 54$
You can fit 54 bricks into said box, therefore the answer is yes.

EDIT: I may be a bit late but the topic wasn't locked and the answer wasn't posted so I figured I would do it.

 

[fresh_42]

Spoiler

Assuming that each brick is $1m * 1m * 4m$, and the box is $6m * 6m * 6m$;
The volume taken by 1 brick is equal to $1m * 1m * 4m = 4m^3$ and the volume of said box would be $6m * 6m * 6m = 216m^3$, then;
$216m^3 / 4m^3 = 54$
You can fit 54 bricks into said box, therefore the answer is yes.

EDIT: I may be a bit late but the topic wasn't locked and the answer wasn't posted so I figured I would do it.

Problem is: you have to keep the bricks in one piece!

 

[mfb]

@FelixLudi: With that argument you could also fit two 4x1x1 bricks in a 2x2x2 box. But you cannot.

 

[FelixLudi]

I overlooked that somehow, but I'm out of solutions now since I can't get the right distribution of bricks to fit in (not even with an online 3d modeler).

 

[Phylosopher]

Spoiler

Assuming that each brick is $1m * 1m * 4m$, and the box is $6m * 6m * 6m$;
The volume taken by 1 brick is equal to $1m * 1m * 4m = 4m^3$ and the volume of said box would be $6m * 6m * 6m = 216m^3$, then;
$216m^3 / 4m^3 = 54$
You can fit 54 bricks into said box, therefore the answer is yes.

EDIT: I may be a bit late but the topic wasn't locked and the answer wasn't posted so I figured I would do it.

I did the same thing first to verify whether it is impossible to fit them or not. If the total volume of the bricks is larger than $6*6*6$ then it is impossible to fit the bricks inside such space. If total volume of the bricks is equal or smaller than the volume of the space, then it might be possible to do so.

It can be impossible to fit them even if they have equal or smaller volume.

Counterexample: Fitting $2*2*2$ brick in $1*1*5$ space (Im not sure, but I think this is a valid counterexample somehow!)

 

[mfb]

I overlooked that somehow, but I'm out of solutions now since I can't get the right distribution of bricks to fit in (not even with an online 3d modeler).

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

 

[Phylosopher]

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

Can you share your trials with us? It might give us a new perspective.

I tried to approach the problem mathematically but I failed. I tried to think of it outside the mathematical formulas, but to be honest I am not satisfied with the such method (Its not giving me an answer anyway ^^").

 

[FelixLudi]

New perspective?

Spoiler

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.

 

[mfb]

@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]

Spoiler

@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]

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.

 

[FelixLudi]

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]

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.

 

[FelixLudi]

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.

Spoiler: Image

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.

Spoiler: Image

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.

 

[mfb]

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.

 

[FelixLudi]

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.

 

[mfb]

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.

 

[FelixLudi]

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]

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*}

 

[QuantumQuest]

Solution for Problem $8$:

Spoiler

$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]

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.