- #1
- 926
- 483
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##)
##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\,?##
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.
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
Last edited by a moderator: