Math Challenge - February 2019

[fresh_42]

5.(b) Show that there is an integer $a \in \mathbb{Z}$ such that 64959| $(a^{2} - 7)$

Answer:

We can see that 3 divides 64959 because its digits add up to a multiple of 3 (6+4+9+5+9 = 33 = 3+3=6). (If necessary, I can explain why. Just let me know.) So, we need to find an integer a such that $a^{2}-7$ is a number that is 3 or 3 x $10^{n}$. Honestly, I brute forced this, and came up with a = 2. $2^2-7 = 4-7=-3$ which definitely divides 64959 (64959 = -3 * -21653).

$3\,|\,64959$ but not the other way around. The key words here are the Legendre symbol and the Chinese remainder theorem.

As of part 5.a.), your solution

$3^{2405} = 3^{5+2400} = (3^{5})(3^{2400})$
$3^{400} \equiv 1(mod 1000)$ so $3^{2400} \equiv 1(mod 1000)$
Then, $3^{2405} = (3^{5})(3^{2400}) \equiv (243*1)(mod 1000)$, so that the last 3 digits of $3^{2405}$ are 243.

is correct, but a hint to Euler's theorem would have been fine:
$$
3^{\varphi(n)} \equiv 1 \,\operatorname{mod} n \\[12pt]
\varphi(1000) = \# \text{ numbers from 1 to 1000 which are relatively prime to 1000 } = \varphi(8) \varphi(125)=\varphi(2^3) \varphi(5^3)=2^3 \left(1- \dfrac{1}{2} \right) 5^3 \left(1- \dfrac{1}{5} \right) = 400
$$
and thus $3^{400} \equiv 1 \,\operatorname{mod} 1000$ is the information which really counted.

 

[archaic]

Spoiler: Fragments of 6

Well, since there's an integer $n$ this looks like induction. (I know this isn't a nice way to spot induction, do you please know a website/paper/pdf which talks about the matter?)
What jumps to me is this :
For $n=1$ we have $f(x)=f(x+\frac{1}{n})=f(x+1)$ set $x=0$ and we get$f(0)=f(1)$which is true.
For $n=2$ we have $f(x)=f(x+\frac{1}{n})=f(x+\frac{2}{n})$ set $x=0$ and we get$f(0)=f(1)$which is true.
For $n=3$ we have $f(x)=f(x+\frac{1}{n})=f(x+\frac{2}{n})=f(x+\frac{3}{n})$ set $x=0$ and we get$f(0)=f(1)$which is true.
...
For $n=n$ we have $f(x)=f(x+\frac{1}{n})=f(x+\frac{2}{n})=...=f(x+\frac{n}{n})$ set $x=0$ and we get$f(0)=f(1)$which is true.
For $n=n+1$ we have $f(x)=f(x+\frac{1}{n})=f(x+\frac{2}{n})=...=f(x+\frac{n}{n})=f(x+\frac{n+1}{n})$ set $x=0$ and we get$f(0)=f(1)$which is true.
I am unsure about the last two line and I do not know how to proceed from the first lines.

 

[QuantumQuest]

Well, since there's an integer $n$ this looks like induction. (I know this isn't a nice way to spot induction, do you please know a website/paper/pdf which talks about the matter?)

Do you mean a resource talking about induction in general or something more specific?

For $n=2$ we have $f(x)=f(x+\frac{1}{n})=f(x+\frac{2}{n})$ set $x=0$ and we get$f(0)=f(1)$which is true

This is not correct. Check again this (and the lines below it).

Also, is it necessary to use induction?

 

[QuantumP7]

$3\,|\,64959$ but not the other way around. The key words here are the Legendre symbol and the Chinese remainder theorem.

As of part 5.a.), your solution

is correct, but a hint to Euler's theorem would have been fine:
$$
3^{\varphi(n)} \equiv 1 \,\operatorname{mod} n \\[12pt]
\varphi(1000) = \# \text{ numbers from 1 to 1000 which are relatively prime to 1000 } = \varphi(8) \varphi(125)=\varphi(2^3) \varphi(5^3)=2^3 \left(1- \dfrac{1}{2} \right) 5^3 \left(1- \dfrac{1}{5} \right) = 400
$$
and thus $3^{400} \equiv 1 \,\operatorname{mod} 1000$ is the information which really counted.

Thank you, sir! Even though I misread part b, I knew that there was some deeper theory and a more elegant solution that I was unaware of. If no one else attempts part b within a few days, then I will redo it, myself.

I look like a complete idiot in this thread, but I really am learning a lot.

 

[archaic]

or something more specific?

Yes, on how to recognize it and why it works. (a farmer which has $n+1$ sheeps of which $n$are black doesn't imply all are, I probably have a very shallow understanding of it)

Also, is it necessary to use induction?

To put it sarcastically, "I'm a simple man, I see $n$ I use induction".

 

[QuantumQuest]

Yes, on how to recognize it and why it works. (a farmer which has $n+1$ sheeps of which $n$are black doesn't imply all are, I probably have a very shallow understanding of it)

As you already know, mathematical induction is a mathematical proof technique that is used to prove that some property $P(n)$ holds true for every natural number. I think that the key here is to understand what is induction exactly and do as many examples / exercises as you can. This will vastly help you gain the required momentum in order to recognize where is induction needed and apply the concept correctly. There is a multitude of examples you can find using a simple google search. Also, you can take a look at this cmu.edu https://www.cs.cmu.edu/~adamchik/21-127/lectures/induction_1_print.pdf for some problems beyond the usual (very basic) ones - it is Computer Science notes so it has some relevant to CS examples.

To put it sarcastically, "I'm a simple man, I see $n$ I use induction".

Mathematical induction is a very important method regarding proofs but (obviously) it is not a litmus test. For this particular question, I would hint to think of the problem in terms of functions i.e. using mostly Calculus.

 

[Buzz Bloom]

Hi @Infrared:

I gather you are the reviewer for problem #4. I have just completed my second try at a solution in post #30. Please take a look at it and let me know if I made any errors, or if it still needs some additional presentation.

Regards,
Buzz

 

[Infrared]

Could you please clarify the following step for me? Your answer is close, but it's not quite right (also, you should give a closed form instead of leaving it as an infinite sum).

(1/k!)[(1-1/n)+(1-2/n)+...+(1-(n-k+1)]
= (1/k!) [ 1 - (1/n)Σ{j=1,k+1}j + O(1/n²)]

​

Also, $1+2+\ldots+(k+1)=(k+1)(k+2)/2$, not $k(k+1)/2$, but just fixing this doesn't give the right answer either.

 

[Buzz Bloom]

1+2+…+(k+1)=(k+1)(k+2)/2

but just fixing this doesn't give the right answer either.

it's not quite right (also, you should give a closed form instead of leaving it as an infinite sum).

Hi Infrared:

Thank you very much for your response to my solution attempt. The first error is just carelessness on my part. As an octogenarian I have found that happens much more often than it did a decade or two ago. I will now make an effort to find the second error to make the answer "quite right". It is not immediately obvious to me, but I should be able to find it. I expect that putting the answer into closed form will be the most difficult part of the necessary fix, but I am hopeful that when I find the second error, that step will become easier.

Could you explain a bit what needs clarification in the step

(1/k!)[(1-1/n)+(1-2/n)+...+(1-(n-k+1)]
= (1/k!) [ 1 - (1/n)Σ_{j=1,k+1}j + O(1/n²) ]​

I am guessing it is related to O(1/n²), but I am not sure about that.

ADDED
I now see that the sum
(1-1/n)+(1-2/n)+...+(1-(n-k+1)
should be a product. I will also fix that careless error in Post #30.

Regards,
Buzz

 

[fresh_42]

High School 5:

It suffices to show that any prime $p \in \{1, 7, 11, 13, 17, 19, 23, 29\}_{\mod(30)}$. Notice that this is true for otherwise we would always have another prime dividing $p$. Done.

I cannot follow your argumentation. Could you be a bit more detailed? And what about 60?

 

[Buzz Bloom]

Hi @Infrared:

I believe I have edited post #30 to correct all my errors for solving problem #4, and I think it is now OK. Please take another look at it.

Regards,
Buzz

 

[fresh_42]

High school 4:

Let $a, b$ be the two numbers. If anyone of these is divisible by $3$ we are done as $3$ also divides their product. Hence assume that $3 \nmid a, b$. This implies $a, b \equiv 1, 2 \mod(3)$. It is easy to see that any choice of $a, b$ such that $3\nmid a, b$ gives either their sum or difference as a multiple of $3$.

If it is so easy to see, why don't you write it?

 

[Ujjwal Basumatary]

I cannot follow your argumentation. Could you be a bit more detailed? And what about 60?

I have edited my posts. Sorry about the brief post I thought it would be unnecessary to post trivial facts.

 

[fresh_42]

I have edited my posts. Sorry about the brief post I thought it would be unnecessary to post trivial facts.

Sloppiness has to be earned. Easy to see, trivial or obvious are not terms I want to see in the high school section, since they all are.

 

[fresh_42]

High School 5:

It suffices to show that any prime $p$ is congruent modulo $1, 3, 7, 11, 13, 17, 19, 23, 29$ modulo $30$. Notice that this is true for otherwise we would always have another prime dividing $p$. For example if $p\equiv 6 \mod(30)$ we would have $6$ divide $p$.

Why does $30 \,|\, (p-6)$ imply $6\,|\,p\,?$ Sorry, but this needs an explanation. As it stands, it is wrong.

As for $60$, any prime is congruent to $1, 7, 11, 13, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59$ modulo $60$ and hence the statement holds good. In general a prime $p$ can be congruent to only $1$ or another prime $q$ modulo a composite number $a$ such that $q \nmid a$

Same here. Why are only those primes possible remainders? I do not need a solution, I have a better one, but you should demonstrate your reasoning on a high school level. And you did not answer the question: what about $60$? What does "holds good" mean?

 

[Buzz Bloom]

Although I think that you can find it easily on the net, in any case, the explicit solution to the Fibonacci recurrence is Fn=1√5(1+√52)n−1√5(1−√52)nF_n = \frac{1}{\sqrt{5}}(\frac{1 + \sqrt{5}}{2})^n - \frac{1}{\sqrt{5}}(\frac{1 - \sqrt{5}}{2})^n known as Binet's formula.

Hi QQ:

I get that the "solution" of the Fibonacci number recursive definition is the closed form formula that calculated the value of the nth number in the series. What I do not get is the relationship of this "solution" to algorithms and the time it takes to perform a calculation using an algorithm. hat I am guessing is there are more than one definition for what it means to solve a recursion expression. One meaning is the closed form that represents the nth term of the recursive sequence, and another meaning has something to do with algorithms and time to perform calculations. If I get the time, I will try to read the 30 page article you cited, and perhaps then I will understand this second meaning.

Regards,
Buzz

 

[Buzz Bloom]

For which values of φ\varphi are f⊥gf \perp g in L2([1,∞))?

Show that there is an integer a∈Za \in \mathbb{Z} such that 64959|(a2−7).

For how many (a1,…,a6)∈{0,1}6(a_1,\ldots,a_6)\in \{0,1\}^6 is it true that Q(a1ζ+…+a6ζ6)=Q(ζ)?

I am hoping that someone can educate me the meanings of some notation that was not included in any math courses I took as a math major over 50 years ago.
In the first quote, what does the symbol ⊥ mean, and what does L²([1,∞)) mean?
In the second quote, what does the vertical bar in 64959|(a²−7) mean?
In the third quote, what does special font Q mean in Q(a₁ζ+…+a₆ζ⁶)=Q(ζ)?

Regards,
Buzz

 

[Infrared]

@Buzz Bloom I am still concerned by $(1-1/n)\ldots (1-(k+1)/n)=1-\frac{1}{n}(1+2+\ldots+ (k+1))+O(1/n^2)$. I agree that you can expand the lefthand side in powers of $1/n$ and that the first two coefficients are what you have written. But the coefficients for $1/n^k$ are going to be polynomials in $k$ and $k$ is not bounded independent of $n$ since $k$ can be as large as $n$. For example if your next term was $k^3/n^2$, then for the terms when $k$ is close to $n$, this is $O(n)$.

 

[Buzz Bloom]

But the coefficients for 1/n^k are going to be polynomials in k and k is not bounded independent of n since k can be as large as n.

Hi Infrared:

Thank you for your reply. You definitely got me. I will have to explore this issue in detail, and it will take quite a while.

Regards,
Buzz

 

[Infrared]

I am hoping that someone can educate me the meanings of some notation that was not included in any math courses I took as a math major over 50 years ago.
In the first quote, what does the symbol ⊥ mean, and what does L²([1,∞)) mean?
In the second quote, what does the vertical bar in 64959|(a²−7) mean?
In the third quote, what does special font Q mean in Q(a₁ζ+…+a₆ζ⁶)=Q(ζ)?

Regards,
Buzz

The first two problems aren't mine, but I'm pretty sure the following is intended (and @fresh_42 can clarify what he means if I get it wrong):
$L^2([1,∞))$ means the set of real-valued functions $f$ defined on $[1,\infty)$ such that $\int_1^\infty f(x)^2 dx$ exists and is finite (technically, it is defined as equivalence classes of such functions up to equality almost everywhere, and the integral means the Lebesgue integral instead of the (improper) Riemann integral, but neither of these facts are important to the problem). There is an inner product on this space defined by
$(f,g)=\int_1^\infty f(x)g(x)dx$. Then $f\perp g$ means $(f,g)=0$. Oftentimes, you work with complex-valued functions instead and then the inner product would be $(f,g)=\int_1^\infty f(x)\overline{g(x)}dx$.

The vertical line means "divides". For example, $3\vert 9$ is true but $3\vert 10$ is not.

$\mathbb{Q}$ is the field of rational numbers. If $\alpha$ is an element of some field $K$ that contains $\mathbb{Q}$, then $\mathbb{Q}(\alpha)$ is the smallest subfield of $K$ that contains all elements of $\mathbb{Q}$ as well as $\alpha$. For example, you can check $\mathbb{Q}(\sqrt{2})=\{a+b\sqrt{2}: a,b\in\mathbb{Q}\}$.

 

[QuantumQuest]

I get that the "solution" of the Fibonacci number recursive definition is the closed form formula that calculated the value of the nth number in the series. What I do not get is the relationship of this "solution" to algorithms and the time it takes to perform a calculation using an algorithm. hat I am guessing is there are more than one definition for what it means to solve a recursion expression. One meaning is the closed form that represents the nth term of the recursive sequence, and another meaning has something to do with algorithms and time to perform calculations. If I get the time, I will try to read the 30 page article you cited, and perhaps then I will understand this second meaning.

I gave you the (explicit) solution because you asked for the solution of the equation i.e. for the $F(n)$.

Perhaps you can help me gain an insight by advising me regarding a simple recursive function. For this example I have chosen the
Fibonacci numbers as a recursive function.

F(0) = F(1) = 1
For n>1, F(n) = F(n-1) + F(n-2)

What is the solution of this recursive series?

In any case, what you ask in post #50 is something outside the questions $1$ and $2$ of the challenge themselves but I'll try to explain it as it is something inside the context of these questions.

The explicit solution of the Fibonacci series gives you the $n$-th term of the series. If you want to calculate this by developing / using a program on a computer, you have to implement an algorithm which in this case can be iterative or recursive. The iterative version is based on having a repetition structure (mostly known as a loop) which computes the $n$-th term of the series in an imperative repetition fashion. Now, the formula $F_n = F_{n-1} + F_{n-2}$ for Fibonacci series, gives us a natural example of recursion which can be written as a recursive function like this

function fib(n) {
    if n = 0 return 0
    if n = 1 return 1
    return fib(n-1) + fib(n-2)
    }

In order to measure the time it takes for the above algorithm to execute when implemented as a program, approximately, we are measuring in terms of lines of code. Let $T(n)$ denote the number of steps needed to compute fib(n). If $n \lt 2$ the function runs for just a couple of steps i.e. for $n \leq 1$ we have $T(n) \leq 2$. Now, if $n$ gets larger there are two recursive invocations of the function fib. The time they take is $T(n -1)$ and $T(n - 2)$ respectively. We must also add the time taken for the checks on the value of $n$ and for the final addition. So, we have $T(n) = T(n - 1) + T(n - 2) + 3$ for $n \gt 1$. Now, if we compare this to the recurrence relation for $F_n$ we easily see that $T(n) \geq F_n$. $T(n)$ is exponential in $n$.

In general, any recursive function such as the above gives us a recurrence relation for time: the time for any routine is the time within the routine itself, plus the time for the recursive calls.

 

[Buzz Bloom]

Hi @Infrared and @QuantumQuest:

Thank you both very much for your posts #55 and #56. I feel your posts have taught me some very useful notations and concepts.

Regards,
Buzz

 

[Buzz Bloom]

Hi @Infrared:

I have fixed another error in post #30, but I still have more work to do on it.

Regarding your issue about O(1/n), I have thought about a method to explain why this concept is correct, but I had not yet added that explanation because I have not yet decided on how to present this concept mathematically in the solution. The concept involves the terms (all multiplied by n) of the form

G_j,k(x,n) = a_j,k (1/n^j) x^k/k! for 1<j<k.​

The limit

lim_n→∞ nG_j,k (x,n) = 0​

because the values of a_j,k are all finite and are independent of n. Do you think a detailed mathematical explanation of this would be sufficient to fix the solution?

Regards,
Buzz

 

[lpetrich]

I will solve Problem 4.

Spoiler

It is to find $L = \lim_{n\to\infty} n ((1 + x/n)^n - e^x)$.

The first term in parentheses, $(1 + x/n)^n$, is well-known for having $e^x$ as a limit as $n\to\infty$. So to find L, we must evaluate $\lim_{n\to\infty} n (\text{that term's difference from } e^x)$. So in order to have a more easily-expanded expression, we do
$$ \left( 1 + \frac{x}{n} \right)^n = \exp \log \left( \left( 1 + \frac{x}{n} \right)^n \right) = \exp \left( n \log \left( 1 + \frac{x}{n} \right) \right) $$
We next expand the logarithm in an infinite series, and then do that to the exponential:
$$ \left( 1 + \frac{x}{n} \right)^n = \exp \left( \sum_{k=1}^\infty \frac{(-1)^{k+1} x^k}{k n^{k-1}} \right) = \exp \left( x - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right) = e^x \left( 1 - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right)$$
Plugging this into the expression for L, we find
$$ L = \lim_{n\to\infty} n e^x \left( 1 - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) - 1 \right) = \lim_{n\to\infty} e^x \left( - \frac{x^2}{2} + O\left( \frac{1}{n} \right) \right) = - \frac{x^2}{2} e^x$$
Thus, the answer is
$$ L = - \frac{x^2}{2} e^x $$

 

[Infrared]

@lpetrich Nice work! It's all right.

 

[fresh_42]

I will solve Problem 4.

Spoiler

It is to find $L = \lim_{n\to\infty} n ((1 + x/n)^n - e^x)$.

The first term in parentheses, $(1 + x/n)^n$, is well-known for having $e^x$ as a limit as $n\to\infty$. So to find L, we must evaluate $\lim_{n\to\infty} n (\text{that term's difference from } e^x)$. So in order to have a more easily-expanded expression, we do
$$ \left( 1 + \frac{x}{n} \right)^n = \exp \log \left( \left( 1 + \frac{x}{n} \right)^n \right) = \exp \left( n \log \left( 1 + \frac{x}{n} \right) \right) $$
We next expand the logarithm in an infinite series, and then do that to the exponential:
$$ \left( 1 + \frac{x}{n} \right)^n = \exp \left( \sum_{k=1}^\infty \frac{(-1)^{k+1} x^k}{k n^{k-1}} \right) = \exp \left( x - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right) = e^x \left( 1 - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right)$$
Plugging this into the expression for L, we find
$$ L = \lim_{n\to\infty} n e^x \left( 1 - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) - 1 \right) = \lim_{n\to\infty} e^x \left( - \frac{x^2}{2} + O\left( \frac{1}{n} \right) \right) = - \frac{x^2}{2} e^x$$
Thus, the answer is
$$ L = - \frac{x^2}{2} e^x $$

Just a little remark:
$$\exp \left( x - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right) = e^x \left( 1 - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right)$$
could have had been a bit more elaborated in my opinion. Obviously we have
$$\exp \left( x - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right)=e^x \cdot \exp \left( - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right)$$
which raises the question why $\exp \left( - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right)\stackrel{?}{=}\left(1 - \frac{x^2}{2n} + O\left( \frac{1}{n^2} \right) \right)$. No big deal, but a little remark how you approximated here, just words, no equations, would have had improved readability a lot in my opinion.

 

[lpetrich]

I will solve Problem 2.

Spoiler

One must find a function T(n) of n, a function that satisfies the recurrence relation $T(n) = 2T(n/3) + n$ where $T(1) = 1$ and n is a power of 3.

This can be simplified by using the exponent of 3 in each value of n: $n = 3^k$. So I define a function that is a function of that exponent: $T(n) = U(\log_3 n)$ or $T(3^k) = U(k)$. Using that definition turns our problem into $U(k) = 2U(k-1) + 3^k$ with $U(0) = 1$.

This recurrence is inhomogeneous, and one can add a homogeneous recurrence to it: $U(k) \to U(k) + V(k)$, where $V(k) = 2V(k-1)$. It is easily verified:
$$ U(k) + V(k) = 2U(k-1) + 3^k + 2V(k) = 2(U(k-1) + V(k-1)) + 3^k $$
The homogeneous part's solution is easy: $V(k) = 2^k V(0)$. It also is easily verified: $2V(k-1) = 2 \cdot 2^{k-1} V(0) = 2^k V(0) = V(k)$.

The inhomogeneous part's solution is more difficult. One gets:
$$ U(k) = 2U(k-1) + 3^k = 2(2U(k-1) + 3^{k-1}) + 3^k = 2(2(2U(k-2) + 3^{k-2}) + 3^{k-1}) + 3^k = \dots $$
This suggests a trial solution:
$$ U(k) = \sum_{m=0}^k 2^{k-m} 3^m $$
Inserting it into the recurrence gives
$$ 2 \sum_{m=0}^{k-1} 2^{k-m-1} 3^m + 3^k = \sum_{m=0}^{k-1} 2^{k-m} 3^m + 3^k = \sum_{m=0}^k 2^{k-m} 3^m $$
which demonstrates its correctness. This result can be simplified further. In general,
$$ \sum_{m=0}^k a^{k-m} b^m = a^k \sum_{m=0}^k \left( \frac{b}{a} \right)^m = a^k \frac{1 - (b/a)^{k+1}}{1 - b/a} = \frac{a^{k+1} - b^{k+1}}{a - b}$$
Inserting 3 and 2 gives us $U(k) = 3^{k+1} - 2^{k+1}$. Combining with the V recurrence gives $U(k) = 2^k C + 3^{k+1}$ for some constant C. It is easily verified:
$$ 2U(k-1) + 3^k = 2(2^{k-1} C + 3^k) + 3^k = 2^k C + (2 + 1) 3^k = 2^k C + 3^{k+1} = U(k) $$
What remains is to solve $U(0) = 1$. It is $C + 3 = 1$ or $C = -2$. Thus, the final result is
$$ U(k) = 3^{k+1} - 2^{k+1} $$
or
$$ T(n) = 3n - 2^{\log_3 n + 1} $$

 

[lpetrich]

I will solve Problem 1.

Spoiler

I will first solve it for the general value of the recurrence $T(n) = 2T(\lfloor n/2 \rfloor) + 1$, then insert $T(1) = 4$.

For the recurrence, I will first consider the general case of $T(n) = F(T(\lfloor n/2 \rfloor))$, and look for patterns in its solution.

• T(2) = T(3) = F(T(1))
• T(4) = T(5) = F(T(2)), T(6) = T(7) = F(T(3)) = F(T(2))
• T(8) = T(9) = F(T(4)), T(10) = T(11) = F(T(5)) = F(T(4)), T(12) = T(13) = F(T(6)) = F(T(4)), T(14) = T(15) = F(T(7)) = F(T(4))
• ...

This suggests that all values $T(n)$ are equal for $2^k \leq n \leq 2^{k+1}-1$ for each k. To verify this result, I divide this range by 2 and then round down. $\lfloor 2^k / 2 \rfloor = 2^{k-1}$ and $\lfloor (2^{k+1}-1) / 2 \rfloor = 2^{k-1} - 1$. Thus giving the corresponding range for k-1. Thus,
$$ T(2^k \text{ to } 2^{k+1} - 1) = F(T(2^{k-1} \text{ to } 2^k-1)) $$
with each range's values being equal.

I now change variables for $T(n)$ to get the exponent for 2: $T(n) = U(\log_2 n)$ or $T(2^k) = U(k)$. The equality over range means that $T(n) = U(\lfloor \log_2 n \rfloor)$. The recurrence becomes $U(k) = 2U(k-1) + 1$. Adding 1 to both sides gives $(U(k) + 1) = 2(U(k-1) + 1)$, giving the solution $U(k) = 2^k C - 1$ for some constant C. It is easy to verify:
$$ 2U(k-1) + 1 = 2(2^{k-1} C - 1) + 1 = 2^k C - 1 = U(k) $$
Since we have a value for T(1), this value gives U(0) = T(1), and the above solution in terms of U(0) is $U(k) = 2^k (U(0) + 1) - 1$.

Thus,
$$ T(n) = 2^{\lfloor \log_2 n \rfloor} (T(1) + 1) - 1 = 2^{\lfloor \log_2 n \rfloor} \cdot 5 - 1 $$
for T(1) = 4.

 

[QuantumQuest]

I will solve Problem 2.

In general the way you follow is correct but although I really appreciate your efforts, it is unnecessarily complicated. You can alternatively start from one of the suggested ways in the spoiler (I'm sure you can easily find which way to choose) and go in a much quicker way. In any case, your solution is absolutely acceptable and correct.
Now, in order to be precise - as we are in the context of algorithms for this question, we're interested for big $O$ and big $\Theta$ in comparison with $T(n)$. So, it would be best to express your result for $T(n)$ as $T(n) = 3n - 2n^{\log_3 2} \leq 3n - 2n^{0.63} = O(n)$. Now, as $T(n)$ has $n$ as a summation term we immediately see that $T(n) = \Theta(n)$.

 

[QuantumQuest]

I will solve Problem 1.

Very good.

We can work in the context of algorithms - as it is intended for this question, and use the guess method in a very simple way, which I'll show in order the question to be more clear to all.

The solution we choose to try by guessing in an optimal way is, obviously, of the order $O(n)$. So, we have to prove that $T(n) \leq cn$ where $c$ is a constant. Substituting in the given recurrence relation and applying strong induction we have $T(n) = 2c(\lfloor \frac{n}{2} \rfloor) + 1 \leq 2c(\frac{n}{2}) + 1 = cn + 1$.

At this point, we have to point out that the solution we guessed has not yet been proved, as we have not proved that $T(n) \leq cn$ albeit $cn + 1 = O(n)$. So, we have to modify our guess to $cn - b$ where $b$ is a constant. So, we have $T(n) \leq 2c(\frac{n}{2}) - 2b + 1 = cn + 1 - 2b \leq cn - b$, for all $b \geq 1$. Now, because there is the initial condition $T(1) = 4$ we have that it must hold $T(1) = 4 \leq c\cdot 1 - b$ so $c \geq 4 + b$ and because $b \geq 1$ it is $c \geq 5$. So, we have also found the lower bounds for the values of constants.

 

[lpetrich]

I will attempt to solve Problem 3.

Spoiler

The problem statement is to find the values of $\varphi$ that make $f \perp g = \int_1^\infty f(x) g(x) dx = 0$ for functions f(x) and g(x):
$$ f(x) = \frac{K_1 x + K_2}{x^2} ,\ g(x) = \frac{K_3 x + K_2}{x^2} $$
where
$$ K_1 = \cos \varphi - \sqrt{3}\sin \varphi + 1 ,\ K_2 = 2\sqrt{3}\sin \varphi ,\ K_3 = \cos \varphi - \sqrt{3}\sin \varphi - 1 $$
Plugging the function expressions into X gives
$$ f \perp g = \int_1^\infty \left( \frac{K_1}{x} + \frac{K_2}{x^2} \right) \left( \frac{K_3}{x} + \frac{K_2}{x^2} \right) dx = \int_1^\infty \left( \frac{K_1 K_3}{x^2} + \frac{(K_1 + K_3)K_2}{x^3} + \frac{(K_2)^2}{x^4} \right) dx$$
Using the well-known integral $\int_1^\infty x^{-n} \, dx = \frac{1}{1-n} x^{1-n} |_1^\infty = \frac{1}{n-1}$,
$$ f \perp g = (K_1 K_3) + \frac{(K_1 + K_3) K_2}{2} + \frac{(K_2)^2}{3} $$
Inserting the expressions for the K's gives
$$ f \perp g = (\cos^2\varphi - 2\sqrt{3}\cos\varphi\sin\varphi + 3 \sin^2\varphi - 1) + \frac{4\sqrt{3}\cos\varphi\sin\varphi - 12\sin^2\varphi}{2} + \frac{12 \sin^2\varphi}{3} $$
Simplifying further, and using a certain well-known trigonometric identity,
$$ f \perp g = \cos^2\varphi + \sin^2\varphi - 1 = 0 $$

Thus, $f \perp g = 0$ for all $\varphi$.

 

[fresh_42]

I will attempt to solve Problem 3.

Spoiler

The problem statement is to find the values of $\varphi$ that make $f \perp g = \int_1^\infty f(x) g(x) dx = 0$ for functions f(x) and g(x):
$$ f(x) = \frac{K_1 x + K_2}{x^2} ,\ g(x) = \frac{K_3 x + K_2}{x^2} $$
where
$$ K_1 = \cos \varphi - \sqrt{3}\sin \varphi + 1 ,\ K_2 = 2\sqrt{3}\sin \varphi ,\ K_3 = \cos \varphi - \sqrt{3}\sin \varphi - 1 $$
Plugging the function expressions into X gives
$$ f \perp g = \int_1^\infty \left( \frac{K_1}{x} + \frac{K_2}{x^2} \right) \left( \frac{K_3}{x} + \frac{K_2}{x^2} \right) dx = \int_1^\infty \left( \frac{K_1 K_3}{x^2} + \frac{(K_1 + K_3)K_2}{x^3} + \frac{(K_2)^2}{x^4} \right) dx$$
Using the well-known integral $\int_1^\infty x^{-n} \, dx = \frac{1}{1-n} x^{1-n} |_1^\infty = \frac{1}{n-1}$,
$$ f \perp g = (K_1 K_3) + \frac{(K_1 + K_3) K_2}{2} + \frac{(K_2)^2}{3} $$
Inserting the expressions for the K's gives
$$ f \perp g = (\cos^2\varphi - 2\sqrt{3}\cos\varphi\sin\varphi + 3 \sin^2\varphi - 1) + \frac{4\sqrt{3}\cos\varphi\sin\varphi - 12\sin^2\varphi}{2} + \frac{12 \sin^2\varphi}{3} $$
Simplifying further, and using a certain well-known trigonometric identity,
$$ f \perp g = \cos^2\varphi + \sin^2\varphi - 1 = 0 $$

Thus, $f \perp g = 0$ for all $\varphi$.

That's correct.

Here is a more elegant solution:

If we define $p(x)=x^{-1}$ and $q(x)=\sqrt{3}(2-x)x^{-2}$. Then $\{\,p,q\,\}$ define a orthonormal basis of the subspace $V$ they span in $L^2([1,\infty))$. Now $f,g$ can be written as
$$
f(x)=p(x)+p(x)\cos \varphi + q(x)\sin \varphi \, , \,g(x)=-p(x)+p(x)\cos \varphi +q(x) \sin \varphi
$$
which means they point to the same point on the unit circle of $V$ from the left and from the right intersection with the diameter, and the statement follows by the theorem of Thales, i.e. all values of $\varphi$ fulfill the condition.

 

[Leo Consoli]

My attempt for High School problem 5:
Any number N when divided by 30 will leave a remainder S such that S∈{0,1,2,3...,29}. The goal is to prove that when N is prime,S is also prime or 1.
Assuming this is not the case and S is not equal to 1 or a prime number, since the prime factors of 30 are 2,3 and 5,and N is prime, then two primes bigger than 5 have to be divisors of S, but this condradicts the fact that s can't be bigger than 29.
As for when dividing any number N by 60, we can use the information that any prime P bigger than 5 can be written as 30x+y, being x a natural number and y a coprime of 30 between 0 and 29, so the possibilities for y are {1,7,11,13,17,19,23,29}, this is true because P is bigger than 5 and prime so it is coprime to 2,3 and 5, so P is coprime to 30, and so is it remainder when divided by 30. For x=0 and x=1 the remainder of the division is y itself, for the primes smaller and equal to 5 {2,3,5} the remainder is 1 since the division can be fatorated. For bigger values of x this doesn't always hold true (ex:109), so doing the same procedure let's say that there is a prime number N that when divided by 60 leaves a remainder y that is not prime or 1.The reaminder in dividing any number by 60 belongs to {0,1,2...,59}, so since the prime factors of 60 are 2,2,3 and 5, and N is prime, two primes bigger than 5 must be divisors of y, and this doesn't contradict the fact that y can't be bigger than 59 since 7x7=49.

 

[fresh_42]

My attempt for High School problem 5:
Any number N when divided by 30 will leave a remainder S such that S∈{0,1,2,3...,29}. The goal is to prove that when N is prime,S is also prime or 1.
Assuming this is not the case and S is not equal to 1 or a prime number, since the prime factors of 30 are 2,3 and 5,and N is prime, the remainder S must be equal to the product of 2 prime numbers bigger than 5,...

because if $2,3$ or $5$ divided $S$, they would divide $N$, too: $N=30q +S$. It doesn't have to be a product of exactly two primes, but two primes bigger than $5$ have to be divisors, as per assumption $S$ isn't prime.

... but this contradicts the fact that S can't be bigger than 29.

One can also do it directly: Since $2,3,5 \nmid S$ all remainders which are left are primes or one: $1,7,11,13,17,19,23,29$. But the indirect method is nicer.

As for when dividing any number N by 60, we can use the information that any prime P bigger than 5 can be written as 30x+y, being x a natural number and y a coprime of 30 between 0 and 29, so the possibilities for y are {1,7,11,13,17,19,23,29}, this is true because P is bigger than 5 and prime so it is coprime to 2,3 and 5, so P is coprime to 30, and so is it remainder when divided by 30. For x=0 and x=1 the remainder of the division is y itself, for the primes smaller and equal to 5 {2,3,5} the remainder is 1 since the division can be fatorated. For bigger values of x this doesn't always hold true (ex:109), so doing the same procedure let's say that there is a prime number N that when divided by 60 leaves a remainder y that is not prime or 1.The reaminder in dividing any number by 60 belongs to {0,1,2...,59}, so since the prime factors of 60 are 2,2,3 and 5, and N is prime, the remainder y must be equal to the product of 2 prime numbers bigger than 5, and this doesn't contradict the fact that y can't be bigger than 59 since 7x7=49.

This is rather complicated and as far as I read it, it only shows that the proof above for $30$ does not work for $60$. However, this doesn't mean there cannot be another proof which will work! But your example $109=1\cdot 60 + 49$ is the counterexample which is needed to show, that the same statement for $60$ is actually wrong. That a certain proof does not work is meaningless, the example is already the proof that it cannot be proven (by any attempt).

 

[Leo Consoli]

because if 2,32,32,3 or 555 divided SSS, they would divide NNN, too: N=30q+SN=30q+SN=30q +S. It doesn't have to be a product of exactly two primes, but two primes bigger than 555 have to be divisors, as per assumption SSS isn't prime.

Thank you I will edit it.

One can also do it directly: Since 2,3,5∤S2,3,5∤S2,3,5 \nmid S all remainders which are left are primes or one: 1,7,11,13,17,19,23,291,7,11,13,17,19,23,291,7,11,13,17,19,23,29. But the indirect method is nicer.

I see, I didnt notice this method.

This is rather complicated and as far as I read it, it only shows that the proof above for 303030 does not work for 606060. However, this doesn't mean there cannot be another proof which will work! But your example 109=1⋅60+49109=1⋅60+49109=1\cdot 60 + 49 is the counterexample which is needed to show, that the same statement for 606060 is actually wrong. That a certain proof does not work is meaningless, the example is already the proof that it cannot be proven (by any attempt).

Thank you, if I had thought like this it would have been much easier.