# Challenge Micromass' big summer challenge

Tags:
1. Jul 16, 2016

### micromass

Summer, July, hot weather: every reason is good enough for some new challenge questions.
NEW: ranking can be found here: https://www.physicsforums.com/threads/micromass-big-challenge-ranking.879070/

For high school and first year university students, there is a special challenge thread for you! https://www.physicsforums.com/threads/micromass-big-high-school-challenge-thread.879086/

RULES:
1. In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.
2. It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
3. If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
4. You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.

1. In a village of $2016$ people, prove that the probability that exactly $m$ days (ignore leap years) are not a birthday can be approximated by a Poisson distribution.

2. SOLVED BY Charles Link, Infrared Consider the spiral in the following graphic. The spiral is started with an isosceles right triangle with rectangular sides $1$. At every step, we form adjoin a new triangle having one rectangular leg the hypothenuse of the previous triangle and the other leg equal to 1.

We see that after we add 17 triangles, we have approximately performed one rotation. Let $K$ be the number of rotations that are performed after adding a googol (i.e.\ $10^{100}$) triangles. Without using a calculator, find the first digit of $K$ and the number of digits of $K$. This answer may use approximation techniques if they are shown to be valid.

3. SOLVED BY Infrared Compute for for each $x\in \mathbb{R}$
$$\lim_{n\rightarrow +\infty} \lim_{m\rightarrow +\infty} |\cos(n! \pi x)|^m$$

4. a) SOLVED BY QuantumQuest In the Pascal triangle, replace all odd numbers by a black dot and remove all even numbers. For example, the first three rows of the Pascal triangle are
$$\begin{array}{|ccccc|} \hline & & 1 & & \\ & 1 & & 1 & \\ 1 & & 2 & & 1\\ \hline \end{array}$$
is transformed to
$$\begin{array}{|ccccc|} \hline & & \bullet & & \\ & \bullet & & \bullet & \\ \bullet & & & & \bullet\\ \hline \end{array}$$

State and prove a conjecture relating the resulting figure to the Sierpinski triangle.

4. b) SOLVED BY Math_QED Let $s_n$ be the product of the terms in the $n$th row of the Pascal triangle. Find
$$\lim_{n\rightarrow +\infty} \frac{s_{n-1}s_{n+1}}{s_n^2}$$

5. SOLVED BY QuantumQuest A drunk man is walking on an infinite grid $\mathbb{Z}\times \mathbb{Z}$. Every time he gets to a point on the grid, he chooses at random between the directions "up", "down", "left", "right" so that each direction has equal probability. After choosing a direction, he continues in that direction until the next grid point. The drunk man starts at the pub which is located at $(0,0)$ and wishes to get home which is located at $(10,10)$. Show that the drunk man will eventually reach his home with probability $1$.

6. SOLVED BY Erland Show that every point in $[-1,1]$ is an accumulation point of the sequence $x_n = \sin n$.

7. SOLVED BY Svein Dana is moving into a mansion, and she needs a huge whiteboard. This whiteboard is to be so heavy that it cannot be lifted; only wheeled. A certain corridor is 2.7 metres wide, and is perpendicular to a 6.4 metre wide corridor. What is the length (in metres) of the longest whiteboard that she can manoeuvre around the corner?

8. Let $G$ be a finite group and let $p$ be the smallest prime number which divide $|G|$. Prove that every subgroup $H$ of $G$ such that $p|H| = |G|$ is normal. Use this to find all groups of order $pq$ with $p$ and $q$ (not necessarily distinct) primes.

9. SOLVED BY Infrared Let $G$ a semigroup (a set with an associative multiplicaton). Prove that the following three conditions are equivalent:
a) $G$ is a group
b) $G$ is not empty and for all $a$ and $b$ in $G$, we have that the equation $ax=b$ has a solution and $xa = b$ has a solution.
c) There exists an $e \in G$ such that $xe = x$ for all $x\in G$. Furthermore, for that specific $e$, we have that for any $x\in G$, there is some $x'\in G$ such that $xx' = e$.

10. SOLVED BY mfb Let $X$ be a set equipped with two operations $\times$ and $*$. Suppose that
a) There is an $e\in X$ such that for each $x\in X$ we have $e*x = x*e = x$.
b) There is an $e'\in X$ such that for each $x\in X$ we have $e'\times x = x\times e' = x$.
c) for all $a,b,c,d\in X$ we have $(a\times b)*(c\times d) = (a*c) \times (b*d)$.
Prove that $\times$ and $*$ are the same. Prove furthermore, that these operations are commutative, associative and have $e=e'$.

Last edited: Jul 22, 2016
2. Jul 16, 2016

### Staff: Mentor

Nice puzzles.

10:

There can be only one neutral element per operation: Assume e and f are both neutral elements for "*", then f=f*e=e*f=e. Same for "x" of course.

Consider rule c for (a x e) * (e x e') = (a * e) x (e * e'). This simplifies to a x e = a for all a.
Consider rule c for (e x a) * (e' x e) = (e * e') x (a * e). This simplifies to e x a = a for all a.
e, the neutral element for "*", is also the neutral element for "x". Therefore, e'=e.

Rule (c) with b=c=e simplifies to a * d = a x d for all a,d. Therefore, the operations are identical.
Rule (c) with a=d=e simplifies to b * c = c * d for all c,d. The operation is commutative.
Rule (c) with b=e simplifies to a*(c*d) = (a*c)*d for all a,c,d. The operation is associative.

3. Jul 16, 2016

### Svein

As to 7:
Assume the angle between the whiteboard and the 2.7m corridor is u. Let h stand for 6.4m and w stand for 2.7m. Then the maximum length of the whiteboard in that position is $l=\frac{h}{\cos(u)}+\frac{w}{\sin(u)}$. Now we need the minimum of that expression, so we derive with respect to u: $$\frac{dl}{du}=\frac{h\cdot\sin(u)}{\cos^{2}(u)}-\frac{w\cdot\cos(u)}{\sin^{2}(u)}$$.
Do the standard thing and find where $\frac{dl}{du}=0$, which means that $\frac{h\cdot\sin(u)}{\cos^{2}(u)}-\frac{w\cdot\cos(u)}{\sin^{2}(u)}=0$. Solving this gives $\tan^{3}(u)=w/h$ or $u=\arctan(\sqrt[3]{\frac{w}{h}})$. Insert the values for w and h and get $u=0.643501109$ and thereby $\sin(u)=0.6$ and $\cos(u)=0.731688869$. Insert these values in the formula for l, and you get l=13.24689m.

That is the theoretical answer, in practice do not go above 13m.

4. Jul 16, 2016

### Math_QED

I am a bit annoyed I am on a too low level to do any of these.

5. Jul 16, 2016

### micromass

You just passed high school right? Do you know calculus? Linear algebra? Maybe I can make a challenge especially for high school/beginning university students.

6. Jul 16, 2016

### Math_QED

Yes, I finished high school in Europe and I am going to university next year. In calculus, I saw sequences, series, limits, derivatives and integrals of functions f: A -> R. From linear algebra, I only saw things like matrices, determinants but not what those things really are, just so we could use it. I would be interested to know what topics other countries cover in high school.

Btw, such a challenge would be greatly appreciated!

7. Jul 16, 2016

### micromass

As for this challenge, question 3, both questions 4 (and especially the second one) shouldn't be out of your reach. If you're willing to look up some basic definitions, then question 9 shouldn't be impossible for you either.

8. Jul 16, 2016

### micromass

9. Jul 16, 2016

### Math_QED

Thanks a lot, for 4b), I claim the solution is e. This was more difficult to calculate than anything I received in high school...

10. Jul 16, 2016

### micromass

Doesn't count unless you give the method!

11. Jul 16, 2016

### Math_QED

It's coming, I'm writing it down neatly so I can take a screenshot.

12. Jul 16, 2016

### QuantumQuest

Problem 4 (the first one)

The Sierpinski triangle is a fractal with the shape of an equilateral triangle, subdivided recursively into smaller equilateral triangles. An image of such triangle can be seen here https://en.wikipedia.org/wiki/Sierpinski_triangle#/media/File:Sierpinski_triangle.svg.

Now to the Pascal triangle. We replace all odd numbers by a black dot and remove all even numbers, as the problem states.

In order to construct a conjecture that relates the previously resulted figure to the Sierpinski triangle, we can investigate how many odd numbers (i.e black dots) are there on the nth row of the Pascal triangle. This way, we can try to verify some pattern for both black dots and blank spaces, as we run down Pascal triangle and finally come to a conclusion, about the overall pattern that is formed.

We define a function $f(n)$ that denotes the number of black dots on the n-th row. We calculate $f(n)$ for a few values:

$n$ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 $\cdots$
$f$ 1 | 2 | 2 | 4 | 2 | 4 | 4 | 8 | 2 | 4 | 04 | 08 | 04 | 08 | 08 | 16 $\cdots$

Now, if we partition the above values for $f$ in this way

1 | 2 | 2,4 | 2,4,4,8 | 2,4,4,8,4,8,8,16 | $\cdots$

we see a pattern: Each block can be obtained by doubling all $f(n)$ values seen prior to that block. We notice that these blocks have breaks that occur after the 1st, 2nd, 4th, 8th, 16th positions. Since each such block - except first, begins with a 2 - i.e 2 black dots, we can make the following conjecture:

For any positive integer l, the row $2^l$ contains only blank spaces ( one for each even number)- except for the 1's on both ends of the row. From the above table we can see that this holds true for the few values of $f$, so we can use this as a base case for a proof by induction.

We assume that our conjecture holds true for row $2^k$. We must show that holds true for $2^{k + 1}$ as well.

What is most important here, is that any triangular pattern having one black dot at the top and black dots along its sides will behave in exactly the same way.

Now, since the sum of two even numbers is even, we have that our inductive hypothesis requires that the triangular pattern of even numbers or equivalently of the blank (white) hexagons in the above sketch must all be even (blank). That means that the line of black dots, from P3 down to the next line of blank hexagons (not including the blank hexagon of this line), as the line from P4 down to the same point (also not including it) must contain only black hexagons.
(For practical reasons, the sketch is relatively small, but you can see all mentioned above, from points P1 and P2 and their respective lines of black hexagons down to P5). Now, by our observations about odd - even parity (black - white hexagons), what holds true about triangle OP1P2 regarding patterns of black and white hexagons, holds true also for the triangles with top points P3 and P4 respectively, excluding the common point that these two triangles have on the next line of hexagons (analogous to P5 case). But since the two hexagons above the common hexagon on this line are black , the common hexagon is blank. But this line of hexagons according to previous analysis, is the $2^{k + 1}$ line (from the top of the external triangle up to this line (not included), we have the first $2^k$ lines). So, line $2^{k + 1}$ consists only of blank hexagons, with the exception of both end-points of this line. Hence, by means of mathematical induction, it must hold true that for every positive integer l > 1, row $2^l$ contains only blanks (i.e even numbers), again except for the two black dots at bot ends of this row.

The pattern we found is nothing else, but a recursive subdivision of an equilateral triangle - every part of a Pascal triangle is such a triangle, regarding the number of positions of odd - even numbers or in our problem, of black dots and blanks, into smaller equilateral triangles. This recursive subdivision, can be seen very easily, as we do the above mathematical induction and see the number of patterns that appear as $k$ becomes bigger. So, we have effectively come to a Sierpinski triangle.

Last edited: Jul 16, 2016
13. Jul 16, 2016

### Infrared

9) It is clear that a group has properties a,b, so it suffices to show that either of a,b imply that $G$ is a group.
For a): We know that $G$ is nonempty, so pick an element $x\in G$. Let $e_R$ be an element of $G$ satisfying $xe_R=x$ (picking $a=b=x$ in the problem statement). We check that $e_R$ is a right identity on $G$ as follows: for any $y\in G$, there is a $z\in G$ such that y=zx. Then $ye_R=(zx)e_R=z(xe_R)=zx=y$. By analogous reasoning, there is a left identity on $G$; call it $e_L$. From the equation $e_L=e_Le_R=e_R$, the two identities are equal and so there is a two-sided identity on $G$, call it now $e$. All that's left is to check the existence of (two-sided) inverses. Let $x\in G$ be arbitrary and let $x'$ and $x''$ satisfy $x'x=e=xx''$. Since $ex'=x'e=x'$, we have $x'xx'=x'xx''$, which implies $x'=x''$ by multiplying both sides by a left inverse of $x'x$. So each $x\in G$ has a two-sided inverse $x^{-1}:=x'=x''$.

For b): Observe that if $g\in G$ is such that $gg=g$, then $g=e$ (by applying g' on the right). Let $x\in G$ be arbitrary and notice that $(x'x)(x'x)=x'(xx')x=x'x$, from which it follows that $x'x=e$. Once we show that $e$ is a two-sided inverse, this is the statement that $x'$ is a two-sided inverse for $x$ and we will be done. Indeed, for all $x\in G$, we have $ex=(xx')x=x(x'x)=xe=x$.

14. Jul 16, 2016

### Infrared

3) Claim: the limit is $1$ if $x\in\mathbb{Q}$ and $0$ if $x\in\mathbb{R}\setminus\mathbb{Q}.$

Case 1: Suppose $x$ is irrational. Then $n!\pi x$ is not a multiple of $\pi$ for any $x$ and hence there is a strict inequality $|\cos(n!\pi x)|<1$, which implies that the inner limit is zero for all $n$ (because $\lim_{m\to\infty}a^m=0$ if $|a|<1$) and so the problem reduces to $\lim_{n\to\infty}0=0$.

Case 2: If $x$ is rational, then there is a natural number $N$ such that $xN$ is an integer. For all $n\geq N$, we have
$\lim_{m\to\infty}|\cos(n!\pi x)|^m=\lim_{m\to\infty}1^m=1$ since $N$ divides $n!$ and so the argument of the cosine is an integer multiple of $\pi$. Since the inner limit is $1$ for sufficiently large $n$, the limit over $n$ evaluates to unity.

Additional note: The absolute value can be removed without altering the problem since $n!x$ is actually an even integer for large $n$ and so the value of the cosine is eventually $1$.

15. Jul 16, 2016

I think I have a solution to #2. $\\ K=1+(\int\limits_{18}^{10^{100}}\ (1/\sqrt{N}) dN )/(2 \pi)$ (approximately). $\\$ Solving $K=1+(\sqrt{10^{100}}-\sqrt{18})/\pi \\$. The answer is approximately $K=3.1 E+49$ so $K$ has $3$ as a first digit and has $50$ digits.$\\$ (For N>18, $\Delta \theta=1/\sqrt{N}$ (approximately for each increment $\Delta N$. This approximation gets far better as $N$ gets larger)). $\\$ Note: $\sqrt{10^{100}}=10^{50} \\$. The integral above approximates a summation of $\Delta \theta_N$ as $N$ goes from $18$ to $10^{100}$.

Last edited: Jul 16, 2016
16. Jul 17, 2016

### Math_QED

17. Jul 17, 2016

### micromass

How do you find this?

18. Jul 17, 2016

Perhaps I should have put a little more detail in the notes I included after the solution. This one is quite interesting=I hadn't previously seen it, but (assuming I got it right), it was kind of an easy one for me. Perhaps I should have not hurried to get in my input and left it for some of the college level students.

19. Jul 17, 2016

### micromass

You did get it right. But I don't think everybody will find it obvious what you did.

20. Jul 17, 2016

Please leave that one then for the college level students. You have one or two who are saying some of your problems are too difficult for them, so this would be a very good one for them.

21. Jul 17, 2016

### Infrared

I guess I'll be the college student to take up the challenge.
Notice that the $n$-th triangle adds an angle of $\arcsin(\frac{1}{\sqrt{n+1}})$. The total angle of the first $N$ triangles is then $\sum_{n=1}^N\arcsin(\frac{1}{\sqrt{n+1}})$. The mean value theorem gives us $\arcsin(\frac{1}{\sqrt{n+1}})=\frac{1}{\sqrt{1-x^2}}\frac{1}{\sqrt{n+1}}$ for some $0\leq x\leq\frac{1}{\sqrt{n+1}}$. Substituting these extreme values (since the expression written is decreasing in $x$), we have
$$\frac{1}{\sqrt{n+1}}\leq\arcsin\left(\frac{1}{\sqrt{n+1}}\right)\leq\frac{1}{\sqrt{n}}.$$

So, the total angle $\Theta$ after adding $N$ triangles satisfies $\sum_{n=1}^N\frac{1}{\sqrt{n+1}}\leq\Theta\leq\sum_{n=1}^N\frac{1}{\sqrt{n}}$. The rightmost term is bounded above by $1+\int_1^N\frac{dn}{\sqrt{n}}=1+2\sqrt{N}-2=2\sqrt{N}-1$. The leftmost term is bounded below by $\int_1^N\frac{dn}{\sqrt{n+1}}=2\sqrt{N+1}-2\sqrt{2}$. Putting in $N=10^{100}$, we have $2\sqrt{10^{100}+1}-2\sqrt{2}\leq\Theta\leq 2\sqrt{10^{100}}=2\cdot 10^{50}-1$. The leftmost term has the lower bound $2\sqrt{10^{100}+1}-2\sqrt{2}>2\sqrt{10^{100}}-3=2\cdot 10^{50}-1$.
So, $2\cdot 10^{50}-3<\Theta<2\cdot 10^{50}-1$. Dividing by $2\pi$ to get the number of full rotations gives Charles' answer.

Last edited: Jul 17, 2016
22. Jul 17, 2016

Your very clever observation that $1/\sqrt{N+1}< \Delta \theta_N <1/\sqrt{N}$ allows you to get extreme precision in your final result. Looks to me to be a very good solution.

23. Jul 17, 2016

### micromass

Personally, my solution used the Euler-Maclaurin integral formula which allows you to get a bound as precise as you like.

24. Jul 17, 2016

Looking it over more closely, the upper bound has a $\sqrt{10}$ factor on it. Perhaps I spoke too soon, but I still like the solution. :-)
I think your last line should read $\sqrt{10^{100}+1}$. Yes, that is now much better precision !!!