- #36

julian

Gold Member

- 738

- 225

https://www.physicsforums.com/threads/math-challenge-september-2020.993056/page-3

Got fed up with tweaking it so have posted it as it is. Sorry it so long.

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Challenge
- Thread starter fresh_42
- Start date
- Featured

- #36

julian

Gold Member

- 738

- 225

https://www.physicsforums.com/threads/math-challenge-september-2020.993056/page-3

Got fed up with tweaking it so have posted it as it is. Sorry it so long.

- #37

julian

Gold Member

- 738

- 225

To elaborate on problem 4.

It was obvious that the AM-GM inequality would be involved, but like I said, a simple application leads to the Harmonic series:

\begin{align*}

\sum_{n=1}^\infty \prod_{k=1}^n (a_k)^{1/n} & \leq \sum_{n=1}^\infty \sum_{k=1}^n \frac{a_k}{n} \\

& = a_1 \sum_{n=1}^\infty \frac{1}{n} + a_2 \sum_{n=2}^\infty \frac{1}{n} + \cdots

\end{align*}

but the Harmonic series diverges, so I decided to consider a "weighted" version of the AM-GM inequality. It is not uncommon to see "weighted" versions of inequalities.

Replacing ##\sum_{n=1}^\infty \sum_{k=1}^n \rightarrow \sum_{k=1}^\infty \sum_{n=k}^\infty## is playing around with double sums, and has a simple interpretation in terms of dots on a 2d grid. You need the sum over ##k## to go from 1 to ##\infty##.

Putting ##b_k = \frac{c_k}{c_{k-1}}## and getting ##c_1 c_2 \cdots c_n = b_n## is simply telescoping products and obviously simplifies things.

And ##\left( 1 + \frac{1}{k} \right)^k \leq e## is a well known inequality.

This

\begin{align*}

\sum_{n=k}^\infty \frac{1}{n(n+1)} = \sum_{n=k}^\infty \left( \frac{1}{n} - \frac{1}{n+1} \right) = \frac{1}{k}

\end{align*}

is a very well known example of telescoping for series.

It was obvious that the AM-GM inequality would be involved, but like I said, a simple application leads to the Harmonic series:

\begin{align*}

\sum_{n=1}^\infty \prod_{k=1}^n (a_k)^{1/n} & \leq \sum_{n=1}^\infty \sum_{k=1}^n \frac{a_k}{n} \\

& = a_1 \sum_{n=1}^\infty \frac{1}{n} + a_2 \sum_{n=2}^\infty \frac{1}{n} + \cdots

\end{align*}

but the Harmonic series diverges, so I decided to consider a "weighted" version of the AM-GM inequality. It is not uncommon to see "weighted" versions of inequalities.

Replacing ##\sum_{n=1}^\infty \sum_{k=1}^n \rightarrow \sum_{k=1}^\infty \sum_{n=k}^\infty## is playing around with double sums, and has a simple interpretation in terms of dots on a 2d grid. You need the sum over ##k## to go from 1 to ##\infty##.

Putting ##b_k = \frac{c_k}{c_{k-1}}## and getting ##c_1 c_2 \cdots c_n = b_n## is simply telescoping products and obviously simplifies things.

And ##\left( 1 + \frac{1}{k} \right)^k \leq e## is a well known inequality.

This

\begin{align*}

\sum_{n=k}^\infty \frac{1}{n(n+1)} = \sum_{n=k}^\infty \left( \frac{1}{n} - \frac{1}{n+1} \right) = \frac{1}{k}

\end{align*}

is a very well known example of telescoping for series.

Last edited:

- #38

- 17,657

- 18,380

I'm having trouble sweeping this up to a proof, starting with a forgotten root in the very first term. It looks somehow right (even though I used Stirling), but can you line up your inequalities`?To elaborate on problem 4.

It was obvious that the AM-GM inequality would be involved, but like I said, a simple application leads to the Harmonic series:

\begin{align*}

\sum_{n=1}^\infty \prod_{k=1}^n a_k & \leq \sum_{n=1}^\infty \sum_{k=1}^n \frac{a_k}{n} \\

& = a_1 \sum_{n=1}^\infty \frac{1}{n} + a_2 \sum_{n=2}^\infty \frac{1}{n} + \cdots

\end{align*}

but the Harmonic series diverges, so I decided to consider a "weighted" version of the AM-GM inequality. It is not uncommon to see "weighted" versions of inequalities.

Replacing ##\sum_{n=1}^\infty \sum_{k=1}^n \rightarrow \sum_{k=1}^\infty \sum_{n=k}^\infty## is playing around with double sums, and has a simple interpretation in terms of dots on a 2d grid. You need the sum over ##k## to go from 1 to ##\infty##.

Putting ##b_k = \frac{c_k}{c_{k-1}}## and getting ##c_1 c_2 \cdots c_n = b_n## is simply telescoping products and obviously simplifies things.

And ##\left( 1 + \frac{1}{k} \right)^k \leq e## is a well known inequality.

This

\begin{align*}

\sum_{n=k}^\infty \frac{1}{n(n+1)} = \sum_{n=k}^\infty \left( \frac{1}{n} - \frac{1}{n+1} \right) = \frac{1}{k}

\end{align*}

is a very well known example of telescoping for series.

- #39

julian

Gold Member

- 738

- 225

- #40

- 17,657

- 18,380

Oops! Your proof on page 1 was fine, no need to explain it. It is indeed Carleman's inequality. It is even a strict one.Sorry, I already gave the proof on page 1. Here I'm just commenting on my methodology.

The problems which have names can certainly be found somewhere, but that does not mean that they are famous enough to be automatically known, plus it means they are worth tackling them! I think it is still better to have a "I already have proven this" moment when encountering those statements in a book, than having solved a complicated but useless integral. I do not assume cheating in such cases. Why should I? Anyone who writes down an answer that they found elsewhere only cheats themselves, but at least has made the effort to learn a new theorem. I always try to put some value to the problems even if it means that they can be found somewhere.

Last edited:

- #41

julian

Gold Member

- 738

- 225

- #42

- 17,657

- 18,380

You can simply consider GM=AM to get a contradiction. That's easier than to deal with the exponential function.

- #43

julian

Gold Member

- 738

- 225

In May 2018 I found that I could prove the inequality: ##(\theta^2 +x_1^2) \dots (\theta^2 +x_n^2) \geq [\theta^2 + (x_1^2 \dots x_n^2)^{1/k}]^k## with Cauchy's forward-backward induction proof, which I was pleased about:

https://www.physicsforums.com/threa...challenge-may-2018.946386/page-3#post-6006214

@StoneTemplePython pointed out a simpler proof: that the inequality is basically the superadditivity of the Geometric Mean. Something I wasn't aware of but I reckon might possibly be the mainstream proof. I have just now done a search for "superadditivity of the Geometric Mean" and the Cauchy's forward-backward induction proof and couldn't find anything (well, aside from the physicsforums "Math Challenge - May 2018" webpage). However, there is most be somebody else who has also had this idea.

Also, I have realized that the inequality can be derived by solving a constrained extremal problem. Which by the way is one of the challenge problems that I have come up with.

I have also come up with a combinatorial proof which was fairly easy to understand but takes ages to explain. It is also a good moment when you come up with proofs that might not be the mainstream proof.

p.s. Sorry if got defensive. It is just that there is a bunch of idiots following me around, but you don't want to know about that.

https://www.physicsforums.com/threa...challenge-may-2018.946386/page-3#post-6006214

@StoneTemplePython pointed out a simpler proof: that the inequality is basically the superadditivity of the Geometric Mean. Something I wasn't aware of but I reckon might possibly be the mainstream proof. I have just now done a search for "superadditivity of the Geometric Mean" and the Cauchy's forward-backward induction proof and couldn't find anything (well, aside from the physicsforums "Math Challenge - May 2018" webpage). However, there is most be somebody else who has also had this idea.

Also, I have realized that the inequality can be derived by solving a constrained extremal problem. Which by the way is one of the challenge problems that I have come up with.

I have also come up with a combinatorial proof which was fairly easy to understand but takes ages to explain. It is also a good moment when you come up with proofs that might not be the mainstream proof.

p.s. Sorry if got defensive. It is just that there is a bunch of idiots following me around, but you don't want to know about that.

Last edited:

- #44

julian

Gold Member

- 738

- 225

Anyway.

- #45

- 17,657

- 18,380

If you look at the previous solutions (currently 4 pdf files), you will find a lot of useful inequalities and equations around symmetries. Whenever possible I added their name.I have just now done a search for "superadditivity of the Geometric Mean" and the Cauchy's forward-backward induction proof and couldn't find anything (well, aside from the physicsforums "Math Challenge - May 2018" webpage). However, there is most be somebody else who has also had this idea.

Also, I have realized that the inequality can be derived by solving a constrained extremal problem. Which by the way is one of the challenge problems that I have come up with.

- #46

mathwonk

Science Advisor

Homework Helper

- 11,397

- 1,640

In reference e.g. to problems generally, I suggest that the goal of this exercise might be to illuminate some key point, rather than to quote a powerful result that implies the problem. Problem #9 e.g., which is indeed essentially the maximum modulus principle, has several proofs, with different morals, each with something to teach us. The mean value property, which follows from integral representations, and I think shows that the value of an appropriate function at the center of a circle equals the average of its values on the boundary, is one that will appeal to analytically minded persons. The approach I hinted at is more geometric, and shows that every analytic function which is non constant near 0, (and with value zero there), looks locally, in some coordinates, like the function z^n, for some n ≥ 1. This makes the local geometric behavior of analytic complex functions very transparent, and implies also the useful "open mapping principle". To each his/her own. The mean value property also has the virtue of remaining true also for harmonic functions, and even in characterizing them, as I recall.

Remrk on #10: most group theory problems I solve follow from the Sylow theorems. But there are some more powerful results out there due to Burnside and others which some of us are not aware of. This problem #10 seems to yield to his "transfer theorem" or "N/C theorem", one that I only learned today. Is there a more clever, less advanced solution, does anyone know, using only Sylow? E.g. as an example of this sort, just try to show that every group of order 30 = 2.3.5 is solvable.

Remrk on #10: most group theory problems I solve follow from the Sylow theorems. But there are some more powerful results out there due to Burnside and others which some of us are not aware of. This problem #10 seems to yield to his "transfer theorem" or "N/C theorem", one that I only learned today. Is there a more clever, less advanced solution, does anyone know, using only Sylow? E.g. as an example of this sort, just try to show that every group of order 30 = 2.3.5 is solvable.

Last edited:

- #47

suremarc

- 147

- 64

3.Prove or find a counterexample to:

(a)##L^2## convergence implies pointwise convergence.

(b)##\displaystyle{\lim_{n \to \infty}\int_{0}^{\infty}\dfrac{\sin x^n}{x^n}\,dx}=1##

(c)Let ##(f_n)## be a sequence of measurable functions which converge uniformly to zero on ##[0,\infty).## Then

$$

\lim_{n \to \infty}\int_{[0,\infty)} f_n(x)\,dx=\int_{[0,\infty)} \lim_{n \to \infty} f_n(x)\,dx\,.

$$

Now consider ##\int_1^\infty\frac{\sin x^n}{x^n}dx##. We have the simple chain of inequalities $$\Bigg|\int_1^\infty\frac{\sin x^n}{x^n}dx\Bigg|\leq \int_1^\infty\Bigg|\frac{\sin x^n}{x^n}\Bigg|dx\leq\int_1^\infty\frac{1}{x^n}dx=\frac{1}{n+1}$$ so our integral is bounded between ##0## and ##\frac{1}{n+1}##, and shrinks to ##0## as ##n\rightarrow\infty##.

Since $$\int_0^\infty\frac{\sin x^n}{x^n}dx=\int_0^1\frac{\sin x^n}{x^n}dx+\int_1^\infty\frac{\sin x^n}{x^n}dx,$$ the integral is equal to ##0+1## or ##1##.

Last edited:

- #48

- 23,792

- 15,406

View attachment 277251Let ##z## be a natural number with ##1995## decimal digits and ##1\leq n\leq 1994.## Then we note the number, which we get by cutting off the first ##n## digits and append them in the same order at the end of ##z## by ##z^{[n]}.## Show that if ##z## is divisible by ##27,## then all ##z^{[n]}## are divisible by ##27,## too.

High Schoolers only

11.

12.Let ##a,b,c,d## be positive real numbers. Prove (in the logically correct order)

$$

\dfrac{1}{\dfrac{1}{a}+\dfrac{1}{b}}+\dfrac{1}{\dfrac{1}{c}+\dfrac{1}{d}}\leq \dfrac{1}{\dfrac{1}{a+c}+\dfrac{1}{b+d}}

$$

13.Let ##m\geq 2## be a given natural number. We define a sequence ##(x_0,x_1,x_2,\ldots)## of numbers by ##x_0=0,x_1=1,## and for ##n\geq 0## we set ##x_{n+2}## to be the remainder of ##x_{n+1}+x_n## by division by ##m,## chosen such that ##0\leq x_{n+2} < m.## Decide whether for every ##m\geq 2## there exists a natural number ##k\geq 1,## such that ##x_{k+2}=1\, , \,x_{k+1}=1\, , \,x_k=0.##

14.We define real functions

$$

f_n(x):=x^3+(n+3)\cdot x^2+2n\cdot x -\dfrac{n}{n+1}

$$

for every non-negative integer ##n\geq 0.## Determine all values of ##n,## such that all zeros of ##f_n(x)## are contained in an interval of length ##3.##

15. (a)Determine the number of all pairs of integers ##(x,y) \in \mathbb{N}_0^2## with ##\sqrt{x}+\sqrt{y}=1993.##

15. (b)Determine for every ##n\in \mathbb{N}## the greatest power of ##2## which divides ##[( 4+\sqrt{18} )^n ].##

I guess it's clear that the high-school questions have become too hard. Given that none of them has been solved!

These look like a sufficient challenge for anyone without the pure maths knowledge to tackle the main questions.

- #49

- 17,657

- 18,380

I won't mind if anyone else tries to solve them in this case, i.e. at the end of month. But I am not sure whether your hypothesis (too hard) holds. There could be other reasons. I admit that some are tricky, but #11 and #12 are quite easy. Especially #12 is straight forward: start with the inequality, end up with something like ##f(a,b,c,d)^2\geq 0## and write it down backwards. It's more a question about proof logic than about arithmetic.I guess it's clear that the high-school questions have become too hard. Given that none of them has been solved!

These look like a sufficient challenge for anyone without the pure maths knowledge to tackle the main questions.

The questions in March will be easier, or at least significantly shorter to answer.

Last edited:

- #50

fishturtle1

- 394

- 81

Proof: We have ##a(a+k) \ge 2(a+k) = (a+k) + (a+k) \ge (a+1) + (a+k) > a + (a+k)##. []

Suppose ##G## is a group of order ##pqr## where ##p < q < r## are distinct primes. Then ##G## is solvable.

Proof: We note that a group of order ##ab## where ##a## and ##b## are distinct primes is solvable. So, it's enough to show ##G## has a normal subgroup of prime order. Let ##n_p## denote the number of Sylow p subgroups of ##G##. Define ##n_q, n_r## similarly. Sylow's theorems tells us

\begin{align*}

n_p &= 1 (\text{ mod p })\\

n_q &= 1 (\text{ mod q })\\

n_r &= 1 (\text{ mod r }) \\

\end{align*}

Sylow's theorems also tells us ##n_p \vert qr##, so ##n_p = 1, q, r,## or ##qr##. Similarly, ##n_q = 1, p, r## or ##pr## and ##n_r = 1, p, q## or ##pq##. If ##n_r = 1##, we're done. If ##n_r = p##, then ##p = 1 (\text{ mod r })##. But that means ##p - 1 = rk## for some positive integer ##k##. But ##p-1 < p < r \le rk##. We may conclude ##n_r \neq p## and ##n_r \neq q##. So we must have ##n_r = pq##. This shows ##G## has ##pq(r-1) = pqr - pq## elements of order ##r##. Subtracting that from ##pqr##, we have ##pqr - (pqr - pq) = pq##. Subtracting ##1## for the identity element, we have ##pq - 1## elements unaccounted for.

Assume by contradiction ##n_p, n_q \neq 1##. We'll show that no matter how small ##n_p## and ##n_q## are, there are still too many elements. If ##n_q = p##, then ##p - 1## is a positive multiple of ##q## which is a contradiction. So, the smallest ##n_q## can be is ##n_q = r##.

The smallest ##n_p## can be is ##n_p = q##. So, if ##n_q = r## and ##n_p = q##, we have ##r(q-1)## elements of order ##q## and ##q(p-1)## elements of order ##p##. But we only have ##pq - 1## elements left. We see

$$(pq - 1) - q(p-1) - r(q-1) = pq - 1 - pq + q - qr + r = q + r - qr - 1 < q + r - qr < 0$$

We've reached a contradiction and can conclude ##n_p = 1## or ##n_p = 1##. This gives a normal subgroup ##H## of prime order, say ##p##. Then ##G/H## is a group of order ##qr##. So, ##G/H## and ##H## are solvable. We may conclude ##G## is solvable.

- #51

Not anonymous

- 143

- 58

\dfrac {1} {\dfrac {1} {a} + \dfrac {1} {b}} + \dfrac {1} {\dfrac {1} {c} + \dfrac {1} {d}}

$$

is equivalent to $$

\dfrac {ab} {a+b} + \dfrac {cd} {c+d} = \dfrac {ab} {x} + \dfrac {cd} {y} = \dfrac {aby + cdx} {xy}

$$

Similarly, the RHS can be expressed in terms of ##x## and ##y## as

##\dfrac {1} {\dfrac {1} {a+c} + \dfrac {1} {b+d}} = \dfrac {(a+c)(b+d)} {a+b+c+d} = \dfrac {(a+c)(b+d)} {x+y}##

##\Rightarrow LHS - RHS = \dfrac{aby+cdx} {xy} - \dfrac{(a+c)(b+d)} {x+y} =##

##\dfrac{(abxy + aby^{2} +cdx^{2} + cdxy) - (abxy + adxy + bcxy + cdxy)} {xy(x+y)} =##

##\dfrac {aby^{2} + cdx^{2} - adxy - bcxy} {xy(x+y)} = \dfrac {(ay - cx)(by - dx)} {xy(x+y)} =##

##\dfrac {(ac + ad - ca - cb)(bc + bd - da - db)} {xy(x+y)} =##

##\dfrac {(ad - bc)(bc - ad)} {xy(x+y)} = \dfrac {-(ad - bc)^{2}} {xy(x+y)}##

The denominator of the final expression ##xy(x+y)## must be positive since the ##a, b, c, d## are all positive and therefore ##x, y## too are positive. And ##-(ad - bc)^{2} \leq 0## for any real-valued ##a, b, c, d##. Hence ##LHS - RHS \leq {0} \Rightarrow \text{LHS} \leq \text{RHS}##, hence proving the inequality.

- #52

- 17,657

- 18,380

I'm not sure whether ##x,y## are really making things easier, but o.k. The usual way to solve such problems is to start with the final statement, change that until something true comes up, and finally write them down backward! Like ##0 \geq -(ad - bc)^{2} \Longrightarrow 0\geq \dfrac {(ad - bc)(bc - ad)} {xy(x+y)} \Longrightarrow \ldots##Define ##x = (a + b)## and ##y = (c + d)##. Then the LHS of the inequality in the question, i.e. $$

\dfrac {1} {\dfrac {1} {a} + \dfrac {1} {b}} + \dfrac {1} {\dfrac {1} {c} + \dfrac {1} {d}}

$$

is equivalent to $$

\dfrac {ab} {a+b} + \dfrac {cd} {c+d} = \dfrac {ab} {x} + \dfrac {cd} {y} = \dfrac {aby + cdx} {xy}

$$

Similarly, the RHS can be expressed in terms of ##x## and ##y## as

##\dfrac {1} {\dfrac {1} {a+c} + \dfrac {1} {b+d}} = \dfrac {(a+c)(b+d)} {a+b+c+d} = \dfrac {(a+c)(b+d)} {x+y}##

##\Rightarrow LHS - RHS = \dfrac{aby+cdx} {xy} - \dfrac{(a+c)(b+d)} {x+y} =##

##\dfrac{(abxy + aby^{2} +cdx^{2} + cdxy) - (abxy + adxy + bcxy + cdxy)} {xy(x+y)} =##

##\dfrac {aby^{2} + cdx^{2} - adxy - bcxy} {xy(x+y)} = \dfrac {(ay - cx)(by - dx)} {xy(x+y)} =##

##\dfrac {(ac + ad - ca - cb)(bc + bd - da - db)} {xy(x+y)} =##

##\dfrac {(ad - bc)(bc - ad)} {xy(x+y)} = -(ad - bc)^{2}##

The denominator of the final expression ##xy(x+y)## must be positive since the ##a, b, c, d## are all positive and therefore ##x, y## too are positive. And ##-(ad - bc)^{2} \leq 0## for any real-valued ##a, b, c, d##. Hence ##LHS - RHS \leq {0} \Rightarrow \text{LHS} \leq \text{RHS}##, hence proving the inequality.

- #53

Not anonymous

- 143

- 58

Now consider positive integers that are powers of 10 and find their modulos w.r.t. 27. ##10^0 \mod {27} = 1, 10^1 \mod {27} = 10, 10^2 \mod {27} = 19, 10^3 \mod {27} = 1, ...## and we note that the modulo sequence ##{1, 10, 19}## repeats. Thus, we can write ##10^{n} \equiv (1 + 9(n \mod{3})) \mod 27## for any non-negative integer ##n##.

By the same logic, we get ##10^{1995-n} \equiv (1 + 9((1995 - n) \mod{3}))\mod 27 \equiv (1 + 9((3 - n) \mod{3}))\mod 27## for any non-negative integer ##n \leq 1995##.

If ##z## is divisible by 27, then we get ##z \mod 27 = 0 \Rightarrow (10^{1995-n}x + y) \mod 27 = 0##

##\Rightarrow y \mod 27 = -(10^{1995-n}x \mod 27) = -(1 + 9((3 - n) \mod{3}))x \mod 27 =##

##-(1 + 27 - 9(n \mod 3))x \mod 27 \equiv -(1 - 9(n \mod 3))x \mod 27##

Similarly, ##d \mod 27## can be expressed in terms of modules of ##x, y, n## w.r.t. 27.

##d \mod 27 = ((10^{n} - 1)y + (10^{1995-n} - 1)x) \mod 27 =##

##(((10^{n} - 1) \mod 27)(y \mod 27) + ((10^{1995-n} - 1) \mod 27)x) \mod 27##

Applying equations (1), (2) and (3) on (Eq. 4) gives:

##d \mod 27 \equiv ((9(n \mod{3}) \times -(1 - 9(n \mod{3}))x) - (9((3 - n) \mod{3}))x) \mod 27##

Defining ##a \equiv n \mod 3## and substituting accordingly in equation (5) gives:

##d \mod 27 \equiv ((9a \times -(1 - 9a)x) - (9(3 - a)x)) \mod 27 \equiv##

##(-9ax + 81a^{2}x - 27x + 9ax) \mod 27 \equiv (81a^{2} - 27x) \mod 27 \equiv 0 \mod 27##.

But ##d \mod 27 \equiv 0 \Rightarrow z^{[n]} \mod 27 = z \mod 27##.

In other words, ##z^{[n]} \equiv z \mod 27## if ##z \equiv 0 \mod 27##, and hence ##z^{[n]}## too is divisible by 27 if ##z## is.

####

- #54

- 17,657

- 18,380

Looks o.k.

Now consider positive integers that are powers of 10 and find their modulos w.r.t. 27. ##10^0 \mod {27} = 1, 10^1 \mod {27} = 10, 10^2 \mod {27} = 19, 10^3 \mod {27} = 1, ...## and we note that the modulo sequence ##{1, 10, 19}## repeats. Thus, we can write ##10^{n} \equiv (1 + 9(n \mod{3})) \mod 27## for any non-negative integer ##n##.(Eq. 1)

By the same logic, we get ##10^{1995-n} \equiv (1 + 9((1995 - n) \mod{3}))\mod 27 \equiv (1 + 9((3 - n) \mod{3}))\mod 27## for any non-negative integer ##n \leq 1995##.(Eq. 2)

If ##z## is divisible by 27, then we get ##z \mod 27 = 0 \Rightarrow (10^{1995-n}x + y) \mod 27 = 0##

##\Rightarrow y \mod 27 = -(10^{1995-n}x \mod 27) = -(1 + 9((3 - n) \mod{3}))x \mod 27 =##

##-(1 + 27 - 9(n \mod 3))x \mod 27 \equiv -(1 - 9(n \mod 3))x \mod 27##(Eq. 3)

Similarly, ##d \mod 27## can be expressed in terms of modules of ##x, y, n## w.r.t. 27.

##d \mod 27 = ((10^{n} - 1)y + (10^{1995-n} - 1)x) \mod 27 =##

##(((10^{n} - 1) \mod 27)(y \mod 27) + ((10^{1995-n} - 1) \mod 27)x) \mod 27##(Eq. 4)

Applying equations (1), (2) and (3) on (Eq. 4) gives:

##d \mod 27 \equiv ((9(n \mod{3}) \times -(1 - 9(n \mod{3}))x) - (9((3 - n) \mod{3}))x) \mod 27##(Eq. 5)

Defining ##a \equiv n \mod 3## and substituting accordingly in equation (5) gives:

##d \mod 27 \equiv ((9a \times -(1 - 9a)x) - (9(3 - a)x)) \mod 27 \equiv##

##(-9ax + 81a^{2}x - 27x + 9ax) \mod 27 \equiv (81a^{2} - 27x) \mod 27 \equiv 0 \mod 27##.

But ##d \mod 27 \equiv 0 \Rightarrow z^{[n]} \mod 27 = z \mod 27##.

In other words, ##z^{[n]} \equiv z \mod 27## if ##z \equiv 0 \mod 27##, and hence ##z^{[n]}## too is divisible by 27 if ##z## is.

####

You could have saved a lot of text by assuming ##n=1##. Why is that sufficient?

- #55

Not anonymous

- 143

- 58

Let ##t## be the smallest such value of ##p##, i.e. the smallest among start indices of repeating subsequences in the original sequence, and let ##j## be the length of corresponding repeating subsequence.

Suppose ##t \geq 1##, i.e. the repeating subsequence starts no earlier than at the second element. Then the original sequence will be of the form ##(0, 1, ..., x_{t-1}, x_{t}, x_{t+1}, ..., x_{t+j}, x_{t+j+1}=x_{t}, x_{t+j+2}=x_{t+1}, ..., x_{t+2j} = x_{t+j}, ...)##.

By definition of how the sequence is formed and the pattern of repeating subsequences, we must have

##x_{t+1}= (x_{t-1} + x_{t}) \mod m##

##x_{t+j+1} = (x_{t+j-1} + x_{t+j}) \mod m \Rightarrow x_{t} = (x_{t+j-1} + x_{t+j}) \mod m##

##x_{t+j+2} = (x_{t+j} + x_{t+j+1}) \mod m \Rightarrow x_{t+1} = (x_{t+j} + x_{t}) \mod m##

(with ##\mod m## denoting the remainder of division by ##m##)

Combining equations

Note: More precisely, ##k \geq 2## since we need ##x_{k} = 0## whereas ##x_{1} = 1 \neq 0##

- #56

- 17,657

- 18,380

I don't get it. ##t## is irrelevant to the question. We already have a determined subsequence ##(0,1,1)## and it doesn't matter where it is. The ##j## is the crucial point since the problem statement requires ##j=1,## i.e. that we actually get ##(0,1,1)## as subsequence and not ##(0,\ldots,1,\ldots,1)##.

Let ##t## be the smallest such value of ##p##, i.e. the smallest among start indices of repeating subsequences in the original sequence, and let ##j## be the length of corresponding repeating subsequence.

Suppose ##t \geq 1##, i.e. the repeating subsequence starts no earlier than at the second element. Then the original sequence will be of the form ##(0, 1, ..., x_{t-1}, x_{t}, x_{t+1}, ..., x_{t+j}, x_{t+j+1}=x_{t}, x_{t+j+2}=x_{t+1}, ..., x_{t+2j} = x_{t+j}, ...)##.

By definition of how the sequence is formed and the pattern of repeating subsequences, we must have

##x_{t+1}= (x_{t-1} + x_{t}) \mod m##(Eq. 1)

##x_{t+j+1} = (x_{t+j-1} + x_{t+j}) \mod m \Rightarrow x_{t} = (x_{t+j-1} + x_{t+j}) \mod m##(Eq. 2)

##x_{t+j+2} = (x_{t+j} + x_{t+j+1}) \mod m \Rightarrow x_{t+1} = (x_{t+j} + x_{t}) \mod m##(Eq. 3)

(with ##\mod m## denoting the remainder of division by ##m##)

Combining equations(1)and(3)we see that ##x_{t-1} \mod m = x_{t+j} \mod m##. Since ##x_{t-1}, x_{t+j} \in \{0, 1, .., m-1\}##, it follows that ##x_{t-1} = x_{t+j}##. This implies that the subsequence ##(x_{t-1}, x_{t}, x_{t+1}, ..., x_{t+j-1})## is a repeating subsequence in the original sequence. But this contradicts the assumption that ##t > 1##. Hence we are left with 0 as the only valid value for ##t##. In other words, the earliest repeating subsequence start at ##i=0##, i.e. the repeating subsequence starts with the pair ##(x_{0} = 0, x_{1} = 0)##. Hence the ordered triple ##(0, 1, 1)## too must repeat in the original sequence, thereby proving that there exists ##k \geq 1## such that ##x_{k} = 0, x_{k+1} = 1, x_{k+2} = 1##

Note: More precisely, ##k \geq 2## since we need ##x_{k} = 0## whereas ##x_{1} = 1 \neq 0##

You must lead ##j>1## to a contradiction, not ##t>1##.

- #57

Not anonymous

- 143

- 58

I don't get it. ##t## is irrelevant to the question. We already have a determined subsequence ##(0,1,1)## and it doesn't matter where it is. The ##j## is the crucial point since the problem statement requires ##j=1,## i.e. that we actually get ##(0,1,1)## as subsequence and not ##(0,\ldots,1,\ldots,1)##.

You must lead ##j>1## to a contradiction, not ##t>1##.

Sorry, I don't understand why ##t## is not relevant to the proof. The question essentially asks whether the

There is specifically a mention of ##k \geq 1## in the question, meaning we a looking for a repetition of ##(0, 1, 1)##We already have a determined subsequence ##(0,1,1)## and it doesn't matter where it is

The ##j## is the crucial point since the problem statement requires ##j=1,## i.e. that we actually get ##(0,1,1)## as subsequence and not ##(0,\ldots,1,\ldots,1)##.

You must lead ##j>1## to a contradiction, not ##t>1##.

There seems to be some confusion regarding how the ##j## in my proof was interpreted. I don't get why you have mentioned ##(0,\ldots,1,\ldots,1)##. The proof only talks about subsequences of

I have already stated in the proof (though indirectly, via ##q##) that only consider subsequences where ##j \geq 1##. But I don't require ##j## to be strictly equal to 1, nor do I attempt to prove it since I think it does not matter. Suppose ##m = 2##, then the full sequence would be of the form ##(0, 1, 1, 0, 1, 1, 0, 1, 1, \ldots)##. We can view this as a repeating subsequence in many different ways, for e.g. as a repetition of ##(0, 1, 1)## (3 elements) or of ##(0, 1, 1, 0, 1, 1)## (6 elements), or of ##(0, 1, 1, 0, 1, 1, 0, 1, 1)## (9 elements), and so on. Or it can be vied as ##(0,1)## followed by the repeating srquence ##(1,0,1)##. Or as ##(0,1,1,0)## followed by the repeating sequence ##(1,1,0)##. And so on other possibilities. In the proof, I don't impose a constraint to consider only the shortest repeating subsequence. But whatever be the length of the repeating subsequence, I show that the

Last edited:

- #58

Not anonymous

- 143

- 58

Let ##t## be the smallest such value of ##p## for which ##(x_{p}, x_{p+1})## repeats as described above, and let ##j## be the corresponding value of ##q##. Suppose ##t \geq 2##. We note the following:

1. ##x_{t+j+1} = x_{t+1} \Rightarrow (x_{t+j-1} + x_{t+j}) \mod m = (x_{t+j-1} + x_{t} \mod m = x_{t+1})##

(where ##\mod m## denotes remainder of division by ##m##)

But since ##x_{t+1} = (x_{t-1} + x_{t}) \mod {m}##, it follows that

##(x_{t-1} + x_{t}) \mod {m} = (x_{t+j-1} + x_{t}) \mod {m} \Rightarrow x_{t-1} \mod {m} = x_{t+j-1} \mod m##

##\Rightarrow x_{t+j-1} = x_{t-1}##

where we use the fact that ##x_{i} \mod m = x_{i}## for all ##x_{i}##'s in the sequence as they are all values from ##\{0, 1, ..., m-1\}##.

2. ##x_{t+j} = (x_{t+j-2} + x_{t+j-1}) \mod m \Rightarrow x_{t} = (x_{t+j-2} + x_{t+j-1}) \mod m##. Using

Since ##x_{t}= (x_{t-2} + x_{t-1}) \mod m## by definition of the original sequence, it follows that

##(x_{t+j-2} + x_{t-1}) \mod m = (x_{t-2} + x_{t-1}) \mod m \Rightarrow x_{t-2} \mod {m} = x_{t+j-2} \mod m##

##\Rightarrow x_{t+j-2} = x_{t-2}##

From

- #59

- 17,657

- 18,380

Let's make an example and set ##m=7##. Then we get as ##(x_0,x_1,x_2,\ldots)##Sorry, I don't understand why ##t## is not relevant to the proof.

$$

0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,\ldots

$$

and

asks for ##k=16##, the subsequence ##x_{16},x_{17},x_{18}.##Decide whether for every ##m\geq 2## there exists a natural number ##k\geq 1,## such that ##x_{k+2}=1\, , \,x_{k+1}=1\, , \,x_k=0.##

However, you considered

Now, if ##t=15##, then you are looking for ##x_{16},x_{16+j},x_{17+j}## which is irrelevant for all cases ##j>0##. However, you didn't consider ##j## at all, only ##t##.By definition of how the sequence is formed and the pattern of repeating subsequences, we must have

##x_{t+1}= (x_{t-1} + x_{t}) \mod m##(Eq. 1)

##x_{t+j+1} = (x_{t+j-1} + x_{t+j}) \mod m \Rightarrow x_{t} = (x_{t+j-1} + x_{t+j}) \mod m##(Eq. 2)

##x_{t+j+2} = (x_{t+j} + x_{t+j+1}) \mod m \Rightarrow x_{t+1} = (x_{t+j} + x_{t}) \mod m##(Eq. 3)

Next, if ##t=7## and ##j=9## we get the subsequence ##(x_{t+1},x_{t+j+1},x_{t+j+2})=(x_{8},x_{17},x_{18})=(0,1,1)## which is in the range of what you investigated. But it is not asked for, because we want to have three consecutive sequence members, i.e. ##j=0##.

I will read your post #58 in a while, but I am a bit skeptical since you only consider pairs ...

... and used far too many indices ##i,j,m,p,q,t.## I will need a machete to get through.

Are you interested in a hint because you were on the right track with your original solution?

Last edited:

- #60

Not anonymous

- 143

- 58

Yes, that is my understanding too.asks for ##k=16##, the subsequence ##x_{16}, x_{17}, x_{18}##.

Not exactly. While it is true that I do consider only ##j > 0## (since I look for repeating subsequences of length at least 2), your interpretation of how I use ##j## is not the same as what I intended to convey. So if ##t=15##, what the proof says is that the ##(j+1)##-tuple ##(x_{15}, x_{15+1}, ..., x_{15+j})## is a subsequence that first occurs at starts at index 15 and repeats itself in the original sequence right after the end of the first occurrence, i.e. starting again at index (15+j+1), i.e. ##x_{15+j+1} = x_{15}, x_{16+j+1} = x_{16}, ..., x_{15+2j+1} = x_{15+j+1}##. Or more generally ##x_{15+u(j+1)} = x_{15}, x_{16+u(j+1)} = x_{16}, ..., x_{15+j+u(j+1)} = x_{15} \forall u \in \{1, 2, ...\}##, though the generalization for ##u > 1## is not really required for the proof.Now, if ##t=15##, then you are looking for ##x_{16}, x_{16+j}, x_{17+j}## which is irrelevant for all cases ##j > 0##. However, you didn't consider ##j## at all, only ##t##.

- #61

- 17,657

- 18,380

How can you conclude that

I can only see contradictions all over the place.Hence the ordered triple ##(0, 1, 1)## toomustrepeat in the original sequence, thereby proving that there exists ##k \geq 1## such that ##x_{k} = 0, x_{k+1} = 1, x_{k+2} = 1##

E.g.

is one contradiction. If we had two successive zeros, then we would be stuck on zeroes.... i.e. the repeating subsequence starts with the pair ##(x_{0} = 0, x_{1} = 0)##.

If you use your method without the minimality requirement you can show that

$$

x_{t+j+1} = x_{t}, x_{t+j+2} = x_{t+1}

$$

leads you to

$$

x_{t+j}=x_t

$$

which you can repeat until

$$

0=x_0=x_t\; , \;1=x_1=x_{t+1}\; , \;1=x_2=x_{t+2}

$$

I think you tried essentially this, just with a minimality argument instead of a repetition argument. But I think you got lost in your zoo of indexes. E.g. simply consider ##x_t=x_{t+j}## instead of ##x_t=x_{t+j+1}##. This little shift makes the entire consideration hard to read.

I'll give you the credit because you have used all necessary steps: pigeon hole principle, modular arithmetic, iteration, and add my solution which I think is easier to read:

There are at most ##m^3## possible triplets ##(x_t,x_{t+1},x_{t+2})_{t\in \mathbb{N}}\in \{0,1,\ldots,m-1\}^3## so there have to be repetitions. Hence there are ##t\geq 0,k\geq 1## with

$$

x_t=x_{k+t}\, , \,x_{t+1}=x_{k+t+1}\, , \,x_{t+2}=x_{k+t+2}

$$

Assume ##t>0.## Per construction we know that ##x_{t+1}\equiv x_t+x_{t-1} \mod m## and ##x_{k+t+1}\equiv x_{k+t}+x_{k+t-1} \mod m,## hence subtraction yields

\begin{align*}

x_{t+1}-x_{k+t+1}&=0=x_t+x_{t-1}-x_{k+t}-x_{k+t-1} \equiv x_{t-1}-x_{k+t-1} \mod m \\

\Longrightarrow m\,&|\,(x_{t-1}-x_{k+t-1})

\end{align*}

which is only possible if ##x_{t-1}=x_{k+t-1}## for a number between ##0## and ##m-1.## We can repeat this argument until

$$

0=x_0=x_k\; , \;1=x_1=x_{k+1}\; , \;1=x_2=x_{k+2}

$$

- #62

Not anonymous

- 143

- 58

E.g.

... i.e. the repeating subsequence starts with the pair ##(x_{0}=0, x_{1}=0)##.

is one contradiction. If we had two successive zeros, then we would be stuck on zeroes.

Sorry, there was a typo in that statement in the proof and that would have added to the confusion. I meant to say ##(x_{0}=0, x_{1}=1)## (and not ##x_{1}=0##).

Here is a sequence or state diagram illustrating what the 1st proof means when it says "repeating subsequence". The backarrow from ##x_{t+j}## to ##x_{t}## indicates that the ##(j+1)##-tuple ##(x_{t}, .., x_{t+j})##, consisting entirely of

Using pigeonhole principle, the proof said that such a repeating subsequence must exist. And by proving (or rather by

and used far too many indices ##i, j, m, p, q, t##. I will need a machete to get through.

Sorry again for complicating the proof, but to me showing the recurrence of a pair of consecutive elements or of an arbitrarily long subsequence of consecutive elements came to mind more naturally first and hence I attempted to prove using those. I agree that proving the repetition of a triple instead could have made the proof (and also verifying if there are errors in the proof) easier to follow for others.

- #63

Not anonymous

- 143

- 58

Looks o.k.

You could have saved a lot of text by assuming ##n=1##. Why is that sufficient?

Yes, the proof of modulo equivalence could have been given for just ##n=1## and then by showing how numbers obtained for other values of ##n## could be obtained by repeating the 1-digit cut-from-left, append-to-right operation.

Suppose ##y## is the rightmost digit of ##z##. Then ##z = 10x+y## where ##x## is the number formed by removing the rightmost digit from ##z##. It is easy to see that ##z^{[1]} = 10^{1994}y + x##.

If ##27 \mid z##, we have ##(10x + y) \mod 27 = 0 \Rightarrow y \mod 27 = -10x \mod 27##

##d = (z^{[1]} - z) \mod 27 = (10^{1994}y + x - 10x - y) \mod 27 = ((10^{1994}-1)y - 9x) \mod 27 =##

##(((10^{1994}-1) \mod 27)(y \mod 27) - (9x mod 27)) \mod 27 \Rightarrow##

##d = (9(1994 \mod 3)(y \mod 27) - (9x \mod 27)) \mod 27##

Here, for ##10^{1994} \mod 27##, I use an equivalence proved in my earlier proof for this question.

Applying

##d = ((-180x \mod 27) - (9x \mod 27)) \mod 27 = -189x \mod 27 = 0##

(since 27 divides 189)

(Eq. 3) implies that ##27 \mid z^{[1]}## if ##27 \mid z##, and this applies to any 1995 digit positive integer. Hence since ##z^{[2]} = (z^{[1]})^{[1]}## and ##z^{[2]}## too is a 1995-digit integer, it follows that:

##27 \mid z \Rightarrow 27 \mid z^{[1]} \Rightarrow 27 \mid z^{[2]}##. This can be generalized to say that ##27 \mid z \Rightarrow 27 \mid z^{[n]}## for any integer ##n##, ##0 < n < 1995##.

Thanks for the hint. When I started on the problem, I did try to establish some sort of an equivalence in modulo between different numbers obtained by permuting digits in the given number, so I came somewhat close, but not close enough, to the more elegant approach which you have alluded to. Sometimes, we overlook simpler approaches thinking them to be complex and only a little help from an expert makes us see the easier path.

- #64

- 17,657

- 18,380

The "correct" way to write the modular arithmetic isYes, the proof of modulo equivalence could have been given for just ##n=1## and then by showing how numbers obtained for other values of ##n## could be obtained by repeating the 1-digit cut-from-left, append-to-right operation.

Suppose ##y## is the rightmost digit of ##z##. Then ##z = 10x+y## where ##x## is the number formed by removing the rightmost digit from ##z##. It is easy to see that ##z^{[1]} = 10^{1994}y + x##.

If ##27 \mid z##, we have ##(10x + y) \mod 27 = 0 \Rightarrow y \mod 27 = -10x \mod 27##(Eq. 1)

##d = (z^{[1]} - z) \mod 27 = (10^{1994}y + x - 10x - y) \mod 27 = ((10^{1994}-1)y - 9x) \mod 27 =##

##(((10^{1994}-1) \mod 27)(y \mod 27) - (9x mod 27)) \mod 27 \Rightarrow##

##d = (9(1994 \mod 3)(y \mod 27) - (9x \mod 27)) \mod 27##(Eq. 2)

Here, for ##10^{1994} \mod 27##, I use an equivalence proved in my earlier proof for this question.

Applying(Eq. 1)on(Eq. 2)and simplifying gives:

##d = ((-180x \mod 27) - (9x \mod 27)) \mod 27 = -189x \mod 27 = 0##(Eq. 3)

(since 27 divides 189)

(Eq. 3) implies that ##27 \mid z^{[1]}## if ##27 \mid z##, and this applies to any 1995 digit positive integer. Hence since ##z^{[2]} = (z^{[1]})^{[1]}## and ##z^{[2]}## too is a 1995-digit integer, it follows that:

##27 \mid z \Rightarrow 27 \mid z^{[1]} \Rightarrow 27 \mid z^{[2]}##. This can be generalized to say that ##27 \mid z \Rightarrow 27 \mid z^{[n]}## for any integer ##n##, ##0 < n < 1995##.

Thanks for the hint. When I started on the problem, I did try to establish some sort of an equivalence in modulo between different numbers obtained by permuting digits in the given number, so I came somewhat close, but not close enough, to the more elegant approach which you have alluded to. Sometimes, we overlook simpler approaches thinking them to be complex and only a little help from an expert makes us see the easier path.

$$

10z-z^{[1]}=y\cdot(10^{1995}-1)=y\cdot (1000^{665}-1)

$$

From ##1000=37 \cdot 27+1## we get ##1000^{665}\equiv 1^{665}\equiv 1 \mod 27.## Hence ##27\,|\,(10z-z^{[1]})## and if ##27\,|\,z## then ##27\,|\,z^{[1]}=10z-(10z-z^{[1]}).##

- #65

Not anonymous

- 143

- 58

##\sqrt{x} = 1993 - \sqrt{y} \Rightarrow x = 1993^2 + y - 3986\sqrt{y} \Rightarrow \sqrt{y} = \dfrac {1993^2 + y - x} {3998}##

The RHS of the final equation above is a rational number whereas the LHS is the square root of a non-negative integer. It should be easy to show that the square root of a non-negative integer cannot be a rational number that is not also an integer (##\sqrt{y}## will be an integer if ##y## is a perfect square, will be an irrational number otherwise). Hence it must be the case that ##\sqrt{y}## is also an integer. In the same way, we can show that ##\sqrt{x}## must also be an integer.

Therefore the possible values of ##\sqrt{x}## for the solution are ##\{0, 1, ..., 1993\}## and once the value of ##\sqrt{x}## is fixed, only one value is possible for each of ##x## and ##y##. The possible solutions for the equation in question are therefore ##(x, y)## pairs from ##\{(0^2, 1993^2), (1^2, 1992^2), (2^2, 1991^2), ..., (1993^2, 0^2)\}## and so the number of pairs is 1994.

- #66

- 17,657

- 18,380

Yes, by the use of the fundamental theorem of arithmetic, i.e. by observing that squares have an even number of each prime.We need ##\sqrt{x} + \sqrt{y} =1993## with ##x, y## being non-negative integers.

##\sqrt{x} = 1993 - \sqrt{y} \Rightarrow x = 1993^2 + y - 3986\sqrt{y} \Rightarrow \sqrt{y} = \dfrac {1993^2 + y - x} {3998}##

The RHS of the final equation above is a rational number whereas the LHS is the square root of a non-negative integer. It should be easy to show that the square root of a non-negative integer cannot be a rational number that is not also an integer (##\sqrt{y}## will be an integer if ##y## is a perfect square, will be an irrational number otherwise).

Hence it must be the case that ##\sqrt{y}## is also an integer. In the same way, we can show that ##\sqrt{x}## must also be an integer.

Therefore the possible values of ##\sqrt{x}## for the solution are ##\{0, 1, ..., 1993\}## and once the value of ##\sqrt{x}## is fixed, only one value is possible for each of ##x## and ##y##. The possible solutions for the equation in question are therefore ##(x, y)## pairs from ##\{(0^2, 1993^2), (1^2, 1992^2), (2^2, 1991^2), ..., (1993^2, 0^2)\}## and so the number of pairs is 1994.

- #67

Not anonymous

- 143

- 58

- #68

- 17,657

- 18,380

This one is rather tricky. E.g. for ##n=3## we get ##\left[(4+\sqrt{18})^3\right]=560## and ##16\,|\,560## so the solution in this case is ##4.##15(b)need an answer not expressed in terms of ##(4+\sqrt{18})##? If yes, may I get some hint?

We are looking for a function ##f:\mathbb{N}\longrightarrow \mathbb{N}## such that ##2^{f(n)}\,|\,\left[(4+\sqrt{18})^n\right]## and where ##f(n)## can be calculated precisely and without calculator.

The standard approach if we see an expression like ##a_n:=(4+\sqrt{18})^n## is to consider ##b_n:=(4-\sqrt{18})^n## and get rid of what disturbes, namely ##\sqrt{18}.## In our case we define ##c_n:=a_n+b_n\,,## develop a recursion for ##c_n## and investigate which powers of ##2## divide ##c_n.## This statement can be proven by induction, and modular arithmetic yields the desired result.

Share:

Challenge
Math Challenge - December 2021

- Replies
- 93

- Views
- 8K

Challenge
Math Challenge - November 2021

- Replies
- 42

- Views
- 5K

Challenge
Math Challenge - October 2021

- Replies
- 61

- Views
- 6K

Challenge
Math Challenge - September 2021

- Replies
- 100

- Views
- 5K

Challenge
Math Challenge - July 2021

- Replies
- 93

- Views
- 5K

Challenge
Math Challenge - May 2021

- Replies
- 114

- Views
- 4K

Challenge
Math Challenge - April 2021

- Replies
- 102

- Views
- 5K

Challenge
Math Challenge - March 2021

- Replies
- 56

- Views
- 5K

Challenge
Math Challenge - January 2021

- Replies
- 86

- Views
- 8K

Challenge
Math Challenge - June 2021

- Replies
- 61

- Views
- 5K