# Math Challenge - February 2019

• Challenge
• Featured
Gold Member

## Main Question or Discussion Point

Time for our new winter challenge! This time our challenge has also two Computer Science related questions and a separate section with five High School math problems. Enjoy!

Rules:

a)
In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.
b) 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.
c) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
d) 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.
e) Mentors, advisors and homework helpers are kindly requested not to post solutions, not even in spoiler tags, for the challenge problems, until 16th of each month. This gives the opportunity to other people including but not limited to students to feel more comfortable in dealing with / solving the challenge problems.
f) High School problems are intended exclusively for High School students. There is no point to be solved by people with higher education, so members are kindly requested to respect this rule as well.

Questions

Recurrence relations and algorithms (Questions ##1## and ##2##)

In the cases that an algorithm includes a recursive call, its running time can be expressed via a recurrence relation or equivalently via an equality or inequality which gives the general term of a sequence as a function of smaller terms.
The main techniques used for solving recurrence relations are

- Guess: We guess the solution and then by substitution and utilizing mathematical induction, we try to prove that we guessed right. This method is used when we don't seek for an exact solution but for finding an upper bound. In many cases a good guess can be found using the recursion tree.

- Iteration method (a.k.a. expansion or unfolding method or repeated substitution): This is a (usually) laborious method as we repeatedly apply the given recurrence relation till we find an easily solvable form.

- Master method: As its name implies, it is a "recipe" for solving recurrence relations of the form
##T(n) = a T(\frac{n}{b}) + f(n),\space\space\space\space a, b \geq 1, f(n) > 0, \forall n \geq n_0## where ##a, b## are constants, ##f(n)## is an asymptotically positive function and the division ##\frac{n}{b}## can be translated as either ##\lfloor \frac{n}{b} \rfloor## or ##\lceil \frac{n}{b} \rceil##. Such recurrence relations are present in the analysis of algorithms that use the divide-and-conquer technique. In rough lines, the solution of a problem amounts to the recursive solution of ##a## sub-problems, each of size ##
\frac{n}{b}## and the combination of these individual solutions. The function ##f(n)## represents the cost of both the segmentation in ##a## sub-problems and the combination of their respective solutions.

##1##. (solved by @lpetrich ) Find an upper bound for the recurrence relation ##T(n) = 2T(\lfloor \frac{n}{2} \rfloor) + 1## using the guess method in an optimal way. If ##T(1) = 4## find the lower bounds for the values of constants.

##2##. (solved by @lpetrich ) Solve the recurrence relation ##T(n) = 2T(\frac{n}{3}) + n##,##\space\space\space\space T(1) = 1##. Assume that ##n## is a power of ##3##.

##3##. (solved by @lpetrich ) Let ##f(x)=\dfrac{(\cos \varphi - \sqrt{3}\sin \varphi +1)x+2\sqrt{3}\sin \varphi}{x^2}##
and ##g(x)=\dfrac{(\cos \varphi - \sqrt{3}\sin \varphi -1)x+2\sqrt{3}\sin \varphi}{x^2}##. For which values of ##\varphi## are ##f \perp g## in ##L^2([1,\infty))\,?##

##4##. (solved by @lpetrich ) Let ##x## be a real number. Find ##\lim_{n\to\infty}n\left(\left(1+x/n\right)^n-e^x\right).##

##5##. a.) (solved by @QuantumP7 ) Compute the last three digits of ##3^{2405}\,.##
##\space\space\space\space##b.) (open) Show that there is an integer ##a \in \mathbb{Z}## such that ##64959\,|\,(a^2-7)\,.##

##6##. (solved by @Periwinkle ) Let ##f: [0,1] \rightarrow \mathbb{R}## be a continuous function with ##f(0) = f(1)## . Prove that the equation ##f(x) = f(x + \frac{1}{n})## has at least one real root, for all ## n = 1, 2, 3,\dots##

##7##. Let ##\zeta## be a primitive ##7##th root of unity. For how many ##(a_1,\ldots,a_6)\in \{0,1\}^6## is it true that ##\mathbb{Q}(a_1\zeta+\ldots+a_6\zeta^6)=\mathbb{Q}(\zeta)\,?##

##8##. (solved by @Periwinkle ) In a conference there are ##n## persons. Show that there are two persons such that, from the rest ##n - 2## persons, there are at least ##\lfloor \frac{n}{2} \rfloor - 1## persons each of which knows both the aforementioned two persons or else knows no one of them. Suppose that "know someone" is a symmetric relation.

##9##. Let ##A## be a real square matrix. Show that if ##A-I## is nilpotent, then ##A## has a square root.

##10##. If an ##n \times n## matrix ##A## satisfies ##A^2 - 3 A + 2 \mathbb{I} = \mathbb{O}## where ##\mathbb{I}## is the ##n \times n## identity matrix and ##\mathbb{O}## the ##n \times n## zero matrix, prove that for all positive integers ##n \geq 1## holds ##A^{2n} - (2^n + 1)A^n + 2^n \mathbb{I} = \mathbb{O}##. ##1##. (solved by @Leo Consoli ) A man wants to figure out the length of an escalator, i.e. the number of steps ##[N]## if it was out of order. Since it wasn't out of order, he counted ##60## steps if he walks with the stairs and ##90## steps if he walks in the opposite direction. What is ##[N]?##

##2##. (solved by @Young physicist ) We are looking for a number with eight digits: two of each ## 1,2,3,4##. The ones are separated by one other number, the twos by two, the threes by three, and the fours by four other numbers.

##3##. (solved by @archaic ) Which of you four threw the ball in my window?
##A## says: It was ##E##.
##E## says: It was ##G##.
##F## says: It was not me.
##G## says: ##E## lied
a.) If only one of the four lied, who threw the ball?
b.) If only one person has told the truth, who was the culprit?

##4##. (solved by @Ujjwal Basumatary ) Choose any two but different natural numbers and form their sum, their difference and product. Prove that among these three numbers at least one is divisible by ##3##.

##5##. (solved by @Leo Consoli ) Prove that the remainder in dividing any prime by ##30## is either ##1## or prime again. Is this also true when dividing a prime number by ##60\,?##

#### Attachments

• 2.8 KB Views: 226
Last edited by a moderator:
• Periwinkle, atyy, Greg Bernhardt and 4 others

High school 2:
41312432

I found that literally by trial and error though, not sure what the proper method is.

The only “ method” I use is that because 4 has to be separated by 4 numbers, the are only 3 possible positions, which I then can trial and error easier.

• atyy
fresh_42
Mentor
High school 2:
41312432

I found that literally by trial and error though, not sure what the proper method is.

The only “ method” I use is that because 4 has to be separated by 4 numbers, the are only 3 possible positions, which I then can trial and error easier.
Yes, conclusions and exclusions are probably the only way here. However, your answer is not complete.

Yes, conclusions and exclusions are probably the only way here. However, your answer is not complete.

fresh_42
Mentor
Yes.

• YoungPhysicist
fresh_42
Mentor
Are you still trying to find it? Please do so, for a) it's quite easy and b) an important lesson to learn here!

Are you still trying to find it? Please do so, for a) it's quite easy and b) an important lesson to learn here!
Yeah, I am just playing baseball for the past couple hours. I’ll do that as soon as I finished my game.

Last edited:
• atyy
High school 2 second attempt:
23421314 is also correct (wait, isn’t that the first one reversed? Is that the lesson?)

• atyy
fresh_42
Mentor
High school 2 second attempt:
23421314 is also correct (wait, isn’t that the first one reversed? Is that the lesson?)
Yes, it is, at least one half of it. The other half to learn is: do not make hidden assumptions or be satisfied too early! In this case the assumption, that one solution already does it, because the way to find it has left apparently no other possibilities. That's a mathematical standard: There are always two parts: Does a solution exist at all? If so, is it unique?

When it comes to solution spaces, always look out for symmetries! They can make life a lot easier, e.g. to restrict a proof on one case as others are symmetric. They can also show the structure of solutions. O.k. maybe not so much in this simple case, but in general. Symmetries are of extraordinary importance in mathematics as well as in physics. So always look out for symmetries.

• maline, atyy and YoungPhysicist
High school 3a:
E lied.

Process:
If A lied, then E lied as well since what G said is the truth. Contradiction.

If E lied, all other statements suggest E is the one throwing the ball.

If F lied, then the one throwing the ball is F, making A and E lying as well. Contradiction.

If G lied, than G is the one throwing the ball, then A lied as well. Contradiction.

High school 3
a) E lied and is the culprit, else there would be contradictions.
b) G told the truth and F is the culprit, contradictions otherwise.

• atyy and fresh_42
dRic2
Gold Member
3
##<f, g> = 0## with ##<f, g> = \int_1^\infty fgdx##. Since we are in ℝ this operator is bilinear and so:
$$<f, g> = (cos \phi - \sqrt{3} sin \phi + 1)(cos \phi - \sqrt{3} sin \phi - 1) \left< \frac 1 x, \frac 1 x \right> + (2\sqrt{3} sin \phi) (cos \phi - \sqrt{3} sin \phi + 1) \left< \frac 1 x, \frac 1 {x^2} \right> + (2\sqrt{3} sin \phi) (cos \phi - \sqrt{3} sin \phi - 1) \left< \frac 1 {x^2}, \frac 1 x \right> + (2\sqrt{3} sin \phi)^2 \left< \frac 1 {x^2}, \frac 1 {x^2} \right> = 0$$
Evaluating:
$$\left< \frac 1 x, \frac 1 x \right> = 1$$
$$\left< \frac 1 {x^2}, \frac 1 x \right> = 2$$
$$\left< \frac 1 {x^2}, \frac 1 {x^2} \right> = 3$$
Here I was lazy and I used Mathematica to simplify the above expression, but if that is against the rule please delete this and I will do the calculation by hand. I got:
$$2 sin \phi (3 \sqrt{3} cos\phi+ 7 sin\phi) = 0$$
So ##\phi = k \pi## with ##k = 0, 1, 2....## and ##\phi = -arctan \left( \frac {3 \sqrt{3}} 7 \right) + \frac {k \pi} 2## with ##k = 0, 1, 2....##

fresh_42
Mentor
3
##<f, g> = 0## with ##<f, g> = \int_1^\infty fgdx##. Since we are in ℝ this operator is bilinear and so:
$$<f, g> = (cos \phi - \sqrt{3} sin \phi + 1)(cos \phi - \sqrt{3} sin \phi - 1) \left< \frac 1 x, \frac 1 x \right> + (2\sqrt{3} sin \phi) (cos \phi - \sqrt{3} sin \phi + 1) \left< \frac 1 x, \frac 1 {x^2} \right> + (2\sqrt{3} sin \phi) (cos \phi - \sqrt{3} sin \phi - 1) \left< \frac 1 {x^2}, \frac 1 x \right> + (2\sqrt{3} sin \phi)^2 \left< \frac 1 {x^2}, \frac 1 {x^2} \right> = 0$$
Evaluating:
$$\left< \frac 1 x, \frac 1 x \right> = 1$$
$$\left< \frac 1 {x^2}, \frac 1 x \right> = 2$$
$$\left< \frac 1 {x^2}, \frac 1 {x^2} \right> = 3$$
Here I was lazy and I used Mathematica to simplify the above expression, but if that is against the rule please delete this and I will do the calculation by hand. I got:
$$2 sin \phi (3 \sqrt{3} cos\phi+ 7 sin\phi) = 0$$
So ##\phi = k \pi## with ##k = 0, 1, 2....## and ##\phi = -arctan \left( \frac {3 \sqrt{3}} 7 \right) + \frac {k \pi} 2## with ##k = 0, 1, 2....##
I have a different result, but I cannot see whether I did a mistake, which is possible as I constructed the problem myself, or you did, since you neither gave a complete proof nor does your formula fit on the page.

And yes, a complete solution is required, no hidden computer algorithms.

Edit: I have checked my result again, so I think you made a mistake.

Last edited:
dRic2
Gold Member
your formula fit on the page.
Yes it does... Scroll to the right and you will see the whole equation.

no hidden computer algorithms.
I just used the command
Code:
Simplfy[ ---copy-paste that long equations---]
Does that mean I have to do it by hand ?

I have a different result
I checked the result I got putting it in the starting functions and I got the expected result, but I could have made some copy/paste mistake myself

fresh_42
Mentor
I checked the result I got putting it in the starting functions and I got the expected result, but I could have made some copy/paste mistake myself
I double checked it again. Have you checked for ##\pi/6## which is as far as I can see not in your list?

dRic2
Gold Member
I double checked it again. Have you checked for π/6π/6\pi/6 which is as far as I can see not in your list?
You are right, ##\pi/6## is a solution I have overlooked. The strange thing is that if I put ##\pi/6## in the equation I wrote in post #12 it doesn't yield zero... but the integral is actually zero. Is there something wrong in my answer ? Are the other results correct ? I maybe be just hitting some wrong keys on the keyboard because it's 3 am here  Tomorrow I'll try again. I'm really sorry for all the trouble.

fresh_42
Mentor
Is there something wrong in my answer ?
I think there has to be. If I made no mistake, then there is an elegant solution of it with not many easy, i.e. polynomial integrals.

4. Let ##x## be a real number. Find ##\lim_{n \rightarrow \infty}n((1+\frac {x}{n})^{n} - e^{x})##.

##\lim_{n \rightarrow \infty}n((1+\frac {x}{n})^{n} - e^{x}) = \left( \lim_{n \rightarrow \infty}n * \lim_{n \rightarrow \infty}(1+\frac {x}{n})^{n} \right) - \left( \lim_{n \rightarrow \infty}n * \lim_{n \rightarrow \infty} e^{x} \right)##

##= \left( \lim_{n \rightarrow \infty}n * e^{x} \right) - \left( \lim_{n \rightarrow \infty}n * e^{x} \right) ##

##=0##

Infrared
Gold Member
##\lim_{n \rightarrow \infty}n((1+\frac {x}{n})^{n} - e^{x}) = \left( \lim_{n \rightarrow \infty}n * \lim_{n \rightarrow \infty}(1+\frac {x}{n})^{n} \right) - \left( \lim_{n \rightarrow \infty}n * \lim_{n \rightarrow \infty} e^{x} \right)##
This is not right, as neither of the terms on your righthand side exist.

Hi, here is my attempt for high school problem 1:
Being N the number of steps when the escalator is not working, s the size of a step of the escalator and u the speed of the escalator.
In the first situation when the person is going up:
s is the relative velocity to the escalator, and (u+s) is the velocity to the ground, so the movement equation is: In the second situation: Dividing both by s:  #### Attachments

• 511 bytes Views: 1,038
• 499 bytes Views: 1,032
• 1.8 KB Views: 208
• 1.1 KB Views: 1,034
• 1.7 KB Views: 1,003
4. Let x be a real number. Find ## \lim_{n \rightarrow \infty} n \left( \left( 1 + \frac{x}{n} \right) ^{n} - e^{x} \right)##

##\lim_{n \rightarrow \infty} ln \left( n \left( \left(1 + \frac{x}{n} \right) ^{n} - e^{x} \right) \right)##

## = \lim_{n \rightarrow \infty} \left( ln(n) + ln \left( \left(1 + \frac{x}{n} \right) ^{n} - e^{x} \right) \right) ##
## = \lim_{n \rightarrow \infty} \left( ln(n) + ln \left(1 + \frac{x}{n} \right) ^{n} - ln \left( e^{x} \right) \right) ##
## = \lim_{n \rightarrow \infty} \left( ln(n) \right) + \lim_{n \rightarrow \infty} \left( ln \left(1 + \frac{x}{n} \right) ^{n} - ln \left( e^{x} \right) \right) ##
## = \lim_{n \rightarrow \infty} \left( ln(n) \right) + \lim_{n \rightarrow \infty} \left( ln \left(1 + \frac{x}{n} \right) ^{n} \right) - \lim_{n \rightarrow \infty} \left( ln \left( e^{x} \right) \right) ##
## = \lim_{n \rightarrow \infty} \left( ln(n) \right) + \left( x \right) - \lim_{n \rightarrow \infty} \left( x \right) ##
## = \lim_{n \rightarrow \infty} \left( ln(n) \right) + \left( x \right) - \left( x \right) ##
## = \lim_{n \rightarrow \infty} \left( ln(n) \right) ##
##= \infty ##

Infrared
Gold Member
## = \lim_{n \rightarrow \infty} \left( ln(n) + ln \left( \left(1 + \frac{x}{n} \right) ^{n} - e^{x} \right) \right) ##
## = \lim_{n \rightarrow \infty} \left( ln(n) + ln \left(1 + \frac{x}{n} \right) ^{n} - ln \left( e^{x} \right) \right) ##
This step is not right, as $\ln(A-B)$ is not the same as $\ln(A)-\ln(B)$.

This step is not right, as $\ln(A-B)$ is not the same as $\ln(A)-\ln(B)$.
Aw. You're right.

4. Let x be a real number. Find ## \lim_{n \rightarrow \infty} n \left( \left( 1 + \frac{x}{n} \right) ^{n} - e^{x} \right)##

## \lim_{n \rightarrow \infty} n \left( \left( 1 + \frac{x}{n} \right) ^{n} - e^{x} \right)##
##= \left( \lim_{n \rightarrow \infty} n \right) \left( \lim_{n \rightarrow \infty} \left( \left( 1 + \frac{x}{n} \right) ^{n} - e^{x} \right) \right)##
##= \left( \lim_{n \rightarrow \infty} n \right) \left( \lim_{n \rightarrow \infty} \left( 1 + \frac{x}{n} \right) ^{n} - \lim_{n \rightarrow \infty} \left( e^{x} \right) \right) ##
##= \left( \lim_{n \rightarrow \infty} n \right) \left( e^{x} - e^{x} \right) ##
##= \left( \lim_{n \rightarrow \infty} n \right) \left( 0 \right) ##
##= 0##

Am I getting closer? *hopeful smile*

Infrared
Gold Member
Aw. You're right.

4. Let x be a real number. Find ## \lim_{n \rightarrow \infty} n \left( \left( 1 + \frac{x}{n} \right) ^{n} - e^{x} \right)##

## \lim_{n \rightarrow \infty} n \left( \left( 1 + \frac{x}{n} \right) ^{n} - e^{x} \right)##
##= \left( \lim_{n \rightarrow \infty} n \right) \left( \lim_{n \rightarrow \infty} \left( \left( 1 + \frac{x}{n} \right) ^{n} - e^{x} \right) \right)##
##= \left( \lim_{n \rightarrow \infty} n \right) \left( \lim_{n \rightarrow \infty} \left( 1 + \frac{x}{n} \right) ^{n} - \lim_{n \rightarrow \infty} \left( e^{x} \right) \right) ##
##= \left( \lim_{n \rightarrow \infty} n \right) \left( e^{x} - e^{x} \right) ##
##= \left( \lim_{n \rightarrow \infty} n \right) \left( 0 \right) ##
##= 0##

Am I getting closer? *hopeful smile*
You can't do this, because $0\cdot\infty$ is an indeterminate form and so doesn't always evaluate to zero. This is rather like claiming that $$1=\lim_{x\to\infty} 1=\lim_{x\to\infty} \left(x\cdot\frac{1}{x}\right)=\left(\lim_{x\to\infty} x\right)\left(\lim_{x\to\infty}\frac{1}{x}\right)=\left(\lim_{x\to\infty} x\right)\cdot 0=0.$$

For what it's worth, the answer is not zero or infinity. It depends on $x$.

Buzz Bloom
Gold Member
I have a question regarding #2.

What does "Solve the recurrence relation," mean. That is, what kind of presentation would be a solution?