Math Challenge - October 2020

  • Challenge
  • Thread starter fresh_42
  • Start date
  • Featured
  • #26
15,756
14,032
There must be a simpler way to prove this, but I think this works.

Problem 8a.
Let a configuration ##C_t## (of the given process) be defined by the ON/OFF states of each lamp before applying the ##t^{th}## step, combined with the current lamp index ##I_t = t \mod n##.

Because there is a finite number of configurations, some configuration must be repeated eventually.

Let ##C_a## be the first repeating configuration and assume for contradiction that ##a \neq 0##. Let ##C_b## be the configuration preceding the second occurrence of a configuration equal to ##C_a##. Then ##C_{a} = C_{b+1}## but ##C_{a-1} \neq C_b## because if ##C_{a-1} = C_{b}##, then ##C_{a-1}## is a repeating configuration that appears before ##C_a##.

Since ##C_{b}## and ##C_{a-1}## both precede a configuration equal to ##C_a##, ##I_{(b \mod n)} = I_{((a-1) \mod n)}##. Thus ##C_b## and ##C_{a-1}## must have different lamp states. Since a single step can only change the state of at most ##1## lamp, and both configurations are ##1## step away from being equal, if follows that they must differ only in ##L_{((a-1) \mod n)} \equiv L_{(b \mod n)}##. Thus ##L_{((a-2) \mod n)} \equiv L_{((b-1) \mod n)}## must be in the same state in both ##C_{b-1}## and ##C_{a-2}##.

Case 1: That state is OFF. Then neither lamp states (neither in ##C_{b}## nor ##C_{a-1}##) would change in their next step. But they both differ, and are both assumed to directly precede a configuration equal to ##C_{a}##, which is a contradiction.

Case 2: That state is ON. Then, the next step would change both lamp states ( both in ##C_{b}## and ##C_{a-1}##), namely by flipping ON/OFF ##L_{ (b \mod n} )##, but since they both differed in ##L_{ b (\mod n} )## prior to this step, afterwards they would still differ in ##L_{ (b \mod n} )##.

All cases are covered, and each contradict the assumption that ##a\neq 0##

It follows that the first repeating configuration must be the initial configuration.

##Q.E.D.##

EDIT: Tried to make the notation and definitions more consistent.
If we phrase it positively, then you have proven that each step can be reversed. Hence any repetition can be brought into a repetition of the initial state of finitely many possible states.

As you mentioned the notation, here is which I have used:
Lamp ##L_j## is in state ##x_j\in \{0,1\}##
initial state: ##v_0=(1,1,\ldots,1)\text{ since }x_{-n}=x_{-n+1}=\ldots=x_{-1}=1##
configuration before step ##S_j## is applied: ##v_j=(x_{j-n},\ldots,x_{j-1})##

The trick is to find a formula ##x_j=x_j(x_{j-n},\ldots,x_{j-1}).##
 
  • #27
StoneTemplePython
Science Advisor
Gold Member
1,203
597
7 seems to be a strengthening of Kantorovich's Inequality.... interesting.
 
  • #28
julian
Gold Member
659
147
Problem #7:

We take ##0 < p \leq a_1 \leq a_2 \leq a_3 \leq a_4 \leq a_5 \leq q##. Write

\begin{align*}
M = (a_1 + a_2 + a_3 + a_4 + a_5) \left( \frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3} + \frac{1}{a_4} + \frac{1}{a_5} \right)
\end{align*}

This is increased when all the weights are on ##a_1## and ##a_5##, i.e. when:

\begin{align*}
M \leq (m a_1 + (5-m) a_5) \left( \frac{m}{a_1} + \frac{5-m}{a_5} \right)
\end{align*}

where ##1 \leq m \leq 4##. We prove this by induction. Consider the general formula

\begin{align*}
M = \left( \sum_i \lambda_i a_i \right) \left( \sum_i \frac{\lambda_i}{a_i} \right) .
\end{align*}

where the ##\lambda_i##'s are integers, some of which are zero, such that ##\sum_{i=1}^n \lambda_i = n##. Consider the ##a_j## term with next term to the left ##a_{j-l}## and next term to the right ##a_{j+l'}##. Define the function

\begin{align*}
M (x) = \left( \sum_{i \not= j} \lambda_i a_i + \lambda_j x \right) \left( \sum_{i \not= j} \frac{\lambda_i}{a_i} + \frac{\lambda_j}{x} \right) .
\end{align*}

where ##x## varies between ##a_{j-l}## and ##a_{j+l'}##. We find that

\begin{align*}
\frac{d}{dx} M (x) & = \left( \sum_{i \not= j} \frac{\lambda_i}{a_i} + \frac{1}{x} \right) - \left( \sum_{i \not= j} \lambda_i a_i + x \right) \frac{1}{x^2}
\\
& = \left( \sum_{i \not= j} \frac{\lambda_i}{a_i} \right) - \left( \sum_{i \not= j} \lambda_i a_i \right) \frac{1}{x^2}
\end{align*}

and

\begin{align*}
\frac{d^2}{dx^2} M (x) = \left( \sum_{i \not= j} \lambda_i a_i \right) \frac{2}{x^3} > 0 .
\end{align*}

So ##M(x)## is convex, which means it has a maximum value at one of the end points. Therefore, ##M## is increased by replacing ##a_j## by either ##a_{j-l}## or ##a_{j+l'}##. This completes the inductive argument.

So that

\begin{align*}
& \; (a_1 + a_2 + a_3 + a_4 +a_5) \left( \frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3} + \frac{1}{a_4} + \frac{1}{a_5} \right)
\\
& \leq (m a_1 + (5-m) a_5) \left( \frac{m}{a_1} + \frac{5-m}{a_5} \right)
\\
& = m^2 + (5-m)^2 + m (5-m) \left( \frac{a_1}{a_5} + \frac{a_5}{a_1} \right)
\\
& = m^2 + (5-m)^2 + 2 m (5-m) + m (5-m) \left( \frac{a_1}{a_5} + \frac{a_5}{a_1} - 2 \right)
\\
& = 25 + m (5-m) \left( \sqrt{\frac{a_1}{a_5}}- \sqrt{\frac{a_5}{a_1}} \right)^2
\end{align*}

This is maximised by taking ##m=2##:

\begin{align*}
(a_1 + a_2 + a_3 + a_4 +a_5) \left( \frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3} + \frac{1}{a_4} + \frac{1}{a_5} \right)
\leq 25 + 6 \left( \sqrt{\frac{a_1}{a_5}}- \sqrt{\frac{a_5}{a_1}} \right)^2 \quad (*)
\end{align*}

Define

\begin{align*}
f (x) = \left( \sqrt{\frac{a_1}{x}} - \sqrt{\frac{x}{a_1}} \right)^2
\end{align*}

and take the derivative

\begin{align*}
\frac{d}{dx} f (x) & = \left( \sqrt{\frac{a_1}{x}}- \sqrt{\frac{x}{a_1}} \right) \left( - \frac{1}{x} \sqrt{\frac{a_1}{x}} - \sqrt{\frac{1}{a_1 x}} \right)
\\
& = - \frac{1}{x} \left( \sqrt{\frac{a_1}{x}} - \sqrt{\frac{x}{a_1}} \right) \left( \sqrt{\frac{a_1}{x}} + \sqrt{\frac{x}{a_1}} \right)
\\
& = \frac{1}{x} \left( \frac{x}{a_1} - \frac{a_1}{x} \right)
\end{align*}

is ##\geq 0## for ##a_1 \leq x < \infty##. Which means we can replace ##a_5## in ##(*)## with any number, denote it ##q##, larger than or equal to ##a_5##.

Define

\begin{align*}
g (x) = \left( \sqrt{\frac{x}{q}} - \sqrt{\frac{q}{x}} \right)^2
\end{align*}

and take the derivative

\begin{align*}
\frac{d}{dx} g (x) = \frac{1}{x} \left( \frac{x}{q} - \frac{q}{x} \right)
\end{align*}

is ##\leq 0## for ##0 < x \leq q##. Which means that, after having replaced ##a_5## with ##q##, we can replace ##a_1## in ##(*)## with any number, denote it ##p > 0##, smaller than or equal to ##a_1##. So finally we have

\begin{align*}
(a_1 + a_2 + a_3 + a_4 +a_5) \left( \frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3} + \frac{1}{a_4} + \frac{1}{a_5} \right)
\leq 25 + 6 \left( \sqrt{\frac{p}{q}}- \sqrt{\frac{q}{p}} \right)^2 .
\end{align*}

where ##0 < p \leq a_1, a_2 , a_3 , a_4 , a_5 \leq q##.

It is easy to generalise these arguments. We have

\begin{align*}
\left( \sum_{i=1}^n a_i \right) \left( \sum_{i=1}^n \frac{1}{a_i} \right)
& \leq (m a_1 + (n-m) a_n) \left( \frac{m}{a_1} + \frac{n-m}{a_n} \right)
\\
& = m^2 + (n-m)^2 + m (n-m) \left( \frac{a_1}{a_n} + \frac{a_n}{a_1} \right)
\\
& = m^2 + (n-m)^2 + 2 m (n-m) + m (n-m) \left( \frac{a_1}{a_n} + \frac{a_n}{a_1} - 2 \right)
\\
& = n^2 + m (n-m) \left( \sqrt{\frac{a_1}{a_n}}- \sqrt{\frac{a_n}{a_1}} \right)^2 .
\end{align*}

For ##n## odd this is maximised by choosing ##m= \frac{n-1}{2}##,

\begin{align*}
\left( \sum_{i=1}^n a_i \right) \left( \sum_{i=1}^n \frac{1}{a_i} \right) \leq n^2 + \frac{n^2 - 1}{4} \left( \sqrt{\frac{a_1}{a_n}}- \sqrt{\frac{a_n}{a_1}} \right)^2
\end{align*}

For ##n## even this is maximised by choosing ##m= \frac{n}{2}##,

\begin{align*}
\left( \sum_{i=1}^n a_i \right) \left( \sum_{i=1}^n \frac{1}{a_i} \right) \leq n^2 + \frac{n^2}{4} \left( \sqrt{\frac{a_1}{a_n}}- \sqrt{\frac{a_n}{a_1}} \right)^2
\end{align*}

We further maximise, as before, by introducing ##p## and ##q## such that ##0 < p \leq a_1, a_2 , \dots, a_n \leq q##. So the general formula are (##n## odd):

\begin{align*}
\left( \sum_{i=1}^n a_i \right) \left( \sum_{i=1}^n \frac{1}{a_i} \right)
\leq n^2 + \frac{n^2-1}{4} \left( \sqrt{\frac{p}{q}}- \sqrt{\frac{q}{p}} \right)^2
\end{align*}

and (##n## even):

\begin{align*}
\left( \sum_{i=1}^n a_i \right) \left( \sum_{i=1}^n \frac{1}{a_i} \right)
\leq n^2 + \frac{n^2}{4} \left( \sqrt{\frac{p}{q}}- \sqrt{\frac{q}{p}} \right)^2 .
\end{align*}
 
Last edited:
  • Like
Likes StoneTemplePython
  • #29
15,756
14,032
Well done, @julian. The last estimation allows a final step
$$
\left(\sum_{i=1}^{n}a_i\right)\left(\sum_{i=1}^n\dfrac{1}{a_i}\right)\leq \dfrac{n^2}{4}\cdot \dfrac{(p+q)^2}{pq}
$$
It is indeed a special case of Kantorovich's inequality (with weights all one) as @StoneTemplePython rightly noted in the previous post. The only difference is a closer look at the optimization problem, i.e. the shape of the feasible set, a polyhedron.
 
  • Like
Likes StoneTemplePython
  • #30
julian
Gold Member
659
147
Problem #1

First let us consider an individual function ##f_n \in \mathcal{A}## for arbitrary ##n##:

##
f_n = \lim_{m \rightarrow \infty} f_m^{(n)} (x) = \lim_{m \rightarrow \infty} \sum_{k=n}^m \tilde{f}_k (x) .
##

Let ##\{ f_m^{(n)} \}_{m \in \mathbb{N} , m \geq n}## be a sequence of functions on ##I = [0, 1]## such that each ##f_m^{(n)}## has continuous derivative on ##I##. If ##\sum_{k=n}^\infty \tilde{f}_k (x)## converges for some ##x_0 \in I## and the series of derivatives ##\sum_{k=n}^\infty \tilde{f}_k'## converges uniformly on ##I## to a sum function ##s_n##, then ##\sum_{k=n}^\infty \tilde{f}_k## converges uniformly on ##I## to a differentiable sum function ##f_n## on ##I##. Moreover, ##s_n = f_n'##. That is, ##\{ f_m^{(n)'} \}## converges uniformly to ##f_n'## on ##I##.

In our case ##f_m^{(n)}## corresponds to

##
f_m^{(n)} = \sum_{k=n}^m a_k \sin (kx) .
##

First ##\sum_{k=n}^\infty a_k \sin (kx)## converges for ##x=0##. We need to show that ##\sum_{n=1}^\infty \tilde{f}_n'## converges uniformly, which is easy to do using the Weierstrass M-test: If ##|\tilde{f}_k' (x)| < M_k## for each ##x \in I## and the sequence ##{M_k}## is summable, then the series ##\sum_{k=n}^\infty \tilde{f}_k'## converges uniformly on ##I##. Write ##M_k = {1 \over k^2}##. Obviously, ##| k a_k \cos (kx)| < M_k## and ##\sum_{k=n}^\infty M_k## converges.

We have established that ##f_n (x) = \sum_{k=n}^\infty a_k \sin (kx)## is differentiable on ##I##, converges uniformly to a sum function ##f_n (x)##, and that its derivatives converge uniformly to ##f_n' (x)##.

Now let us turn to the sequence ##\{ f_n \}_{n \in \mathbb{N}}## where:

##
f_n (x) = \sum_{k=n}^\infty \tilde{f}_k (x) = \sum_{k=1}^\infty \tilde{f}_k (x) - \sum_{k=1}^{n-1} \tilde{f}_k (x) = f_1(x) - \sum_{k=1}^{n-1} \tilde{f}_k (x)
##

First the ##f_n## are a sequence of functions on ##I = [0, 1]## such that each ##f_n## is differentiable on ##I##. The sequence ##f_n## converges uniformly to the zero function on ##I##. The derivatives are uniformly convergent to the zero function on ##I## because:

##
f_n'(x) = f_1' (x) - \sum_{k=1}^{n-1} \tilde{f}_k' (x)
##

Note: A continuous function on a closed bounded interval is bounded and attains its bounds. Every uniformly convergent sequence of bounded functions is uniformly bounded.
Suppose that ##f_n \rightarrow f## uniformly on ##[0,1]## and that for each ##n##, there exists ##C_n## such that ##|f_n (x)| \leq C_n## for any ##x \in I##. Let ##N## be such that

##
|f_n (x) - f (x)| = |f_n (x)| < 1 ,
##

whenever ##n \geq N## and ##x \in I## (in our case ##f(x)## is the zero function). Put

##
C = \max \{ C_1, C_2 , \dots , C_{N-1} , 1 \}
##

Then, for any ##x \in I##,

##
|f_n (x)| \leq C \quad \text{for } n=1,2,3, \dots
##

Thus ##f_n## is uniformly bounded.

Definition: a sequence of functions is uniformly equicontinuous if, for every ##\epsilon > 0##, there exists a ##\delta > 0## such that

##
|f_n (x) - f_n (y)| < \epsilon
##

whenever ##|x - y| < \delta## for all functions ##f_n## in the sequence.

We now use the above results proved for ##\{ f_n \}## to prove that they are uniformly equicontiniuous. By the mean value theorem

##
|f_n (y) - f_n (x)| = {df_n \over dx} (c) |y - x| \quad \text{for some } c \text{ where } 0 \leq x < c < y \leq 1 .
##

The derivatives being uniformly bounded implies

##
|f_n (y) - f_n (x)| \leq M |y - x|
##

where ##M## is the supremum of the derivatives of the functions in the sequence and is independent of ##n##. Take ##\epsilon > 0## and choose ##\delta = \epsilon / M##, then for ##|x - y| < \delta## we have

##
|f_n (y) - f_n (x)| \leq M |y - x| < M \delta = \epsilon .
##

That is, we have shown that a uniformly bounded sequence ##\{ f_n \}## of differentiable functions with uniformly bounded derivatives are uniformly equicontiniuous.

We then apply the Ascoli-Arzela theorem, which states that: Given a sequence of functions ##\{ f_n \}_{n \in \mathbb{N}}## defined on a closed bounded interval ##[a,b]## of the real line. If the sequence is uniformly bounded and uniformly equicontinuous, then there exists a subsequence ##\{ f_{n_k} \}_{k \in \mathbb{N}}## that converges uniformly.
 
Last edited:
  • #31
15,756
14,032
@julian I think this was a bit long, but you are right: Arzelà-Ascoli was the crucial point and checking why it can be applied the task. Well done.
 
  • #32
137
55
##4^n## and ##5^n## are positive integers. Any positive integer ##x## can be written as the product of a positive real number between 1 (inclusive) and 10 (exclusive) and an integer (non-negative) power of 10, i.e. ##x = A \times 10^k## where ##1 \leq A \lt 9## and ##k \in \mathbb{N}_{0}##. Taking the base-10 logarithm, we get ##\log_{10} {x} = k + \log_{10} {A}##. It is easy to see that the first digit of ##x## is determined entirely by ##A## and hence knowing ##\log_{10} {A}## (the mantissa) means knowing the that first digit.

Hence, if ##x = 5^n## and ##y = 4^n## have the same first digit, then their respective mantissas ##a, b## too should be such that they yield the same first digit, i.e. the integer parts of ##10^{a}## and ##10^{b}## should be the same.

##\log_{10} {5^n} = n \log_{10} {5}## (Eq. 1)
##\log_{10} {4^n} = 2n \log_{10} {2} = 2n \log_{10} {\frac {10} {5}} = 2n (1 - \log_{10} {5}) = 2n - 2n \log_{10} {5}## (Eq. 2)

##n \log_{10} {5}## must be a real number and can therefore be written as ##n \log_{10} {5} = m + a## (Eq. 3)

where ##m \in \mathbb{N}_{0}## and ##0 \lt a \lt 1##. Here ##a## is the mantissa corresponding to ##x##. Note that ##a = 0## does not arise since ##5^n## is never expressible as an integer power of 10.

Combining equations (1), (2) and (3), we find that ##\log_{10} {4^n} = 2n - 2(m + a) = 2n - 2m - 2a## (Eq. 4)

Since ##\log_{10} {5} \approx 0.699##, we get ##0 \lt n \log_{10} {5} \lt n \Rightarrow m \in \{0, 1, ..., n-1\}##, i.e., ##m## is a non-negative integer less than ##n##, i.e. ##m \leq (n - 1) \Rightarrow 2n - 2m \geq 2##. Using this property in (Eq. 4), we see that ##\log_{10} {4^n}## can be written as ##p + 2 - 2a## where ##p## is a non-negative integer given by ##(2n - 2m - 2)##.

Given that ##0 \leq a \lt 1##, we consider two subcases and express the mantissa of ##4^n## in terms of the mantissa of ##5^n##:
  1. ##0 < a < 0.5 \Rightarrow 0 < 2a < 1##. In this case, ##\log_{10} {4^n}## can be expressed as ##(p + 1) + b## where ##b = (1-2a) \in (0, 1)##. Here the fraction ##b = (1-2a)## is the mantissa
  2. ##0.5 \leq a < 1 \Rightarrow 1 \leq 2a < 2##. In this case, ##\log_{10} {4^n}## can be expressed as ##p + b## where ##b = (2-2a) \in (0, 1)##. Here the fraction ##b = (2-2a)## is clearly the mantissa
Thus, if we know the mantissa corresponding to ##5^n##, then the mantissa corresponding to ##4^n## is uniquely determined.

We now consider various possible values for the first digit of ##5^n## (obviously that digit is determined uniquely by ##n##), find what the corresponding range of values for mantissa ##a## would be, derive the possible range of values of ##b## (mantissa of ##4^n##) for the given range of values of ##a## and therefore find what are the possible values for the first digit of ##4^n##. Note: The table gives only approximate values for the fractions in the range (as most of those values are irrational numbers), but the ranges are such that even with the approximation, the first digits can be determined without error.

First digit of ##5^n##Range of ##a##Range of ##b##Possible values for first digit of ##4^n##
1##(\log_{10} {1}, \log_{10} {2}) = (0, 0.301)####(1 - 2 \times 0.301, 1 - 2 \times 0) = (0.3979, 1)##, i.e. ##b > 0.3979##Integers less than 10 and greater than ##10^{0.3979}##, i.e. ##\{2, 3, 4, ..., 9\}##
2##(\log_{10} {2}, \log_{10} {3}) = (0.301, 0.477)####(1 - 2 \times 0.477, 1 - 2 \times 0.301) = (0.046, 0.3979)####\{1, 2\}##
3##(\log_{10} {3}, \log_{10} {4}) = (0.477, 0.602)####(1 - 2 \times 0.5, 1 - 2 \times 0.477)## and ##(2 - 2 \times 0.602, 2 - 2 \times 0.5)##
i.e. ##(0, 0.046)## and ##(0.7959, 1)##
##\{1, 6, 7, 8, 9\}##
4##(\log_{10} {4}, \log_{10} {5}) = (0.602, 0.699)####(2 - 2 \times 0.699, 2 - 2 \times 0.602) = (0.602, 0.7959)####\{4, 5, 6\}##
5##(\log_{10} {5}, \log_{10} {6}) = (0.699, 0.778)####(2 - 2 \times 0.778, 2 - 2 \times 0.699) = (0.4437, 0.602)####\{2, 3, 4\}##
6##(\log_{10} {6}, \log_{10} {7}) = (0.778, 0.845)####(2 - 2 \times 0.845, 2 - 2 \times 0.778) = (0.3098, 0.4437)####\{2\}##
7##(\log_{10} {7}, \log_{10} {8}) = (0.845, 0.903)####(0.1938, 0.3098)####\{1, 2\}##
8##(\log_{10} {8}, \log_{10} {9}) = (0.903, 0.954)####(0.0915, 0.1938)####\{1\}##
9##\log_{10} {9}, \log_{10} {10}) = (0.954, 1)####(0, 0.0915)####\{1\}##

From the above table, it is seen that only in cases where the first digit of ##5^n## is either 2 or 4 can the first digit of ##4^n## too take the same value (2 and 4 respectively). For values of ##n## that lead to first digit of ##5^n## being neither 2 nor 4, the values of ##4^n## would be such that their first digit will always be different from the first digit of ##5^n##. Hence the claim stated in the the question is proved.
 
  • #33
15,756
14,032
##4^n## and ##5^n## are positive integers. Any positive integer ##x## can be written as the product of a positive real number between 1 (inclusive) and 10 (exclusive) and an integer (non-negative) power of 10, i.e. ##x = A \times 10^k## where ##1 \leq A \lt 9## and ##k \in \mathbb{N}_{0}##. Taking the base-10 logarithm, we get ##\log_{10} {x} = k + \log_{10} {A}##. It is easy to see that the first digit of ##x## is determined entirely by ##A## and hence knowing ##\log_{10} {A}## (the mantissa) means knowing the that first digit.

Hence, if ##x = 5^n## and ##y = 4^n## have the same first digit, then their respective mantissas ##a, b## too should be such that they yield the same first digit, i.e. the integer parts of ##10^{a}## and ##10^{b}## should be the same.

##\log_{10} {5^n} = n \log_{10} {5}## (Eq. 1)
##\log_{10} {4^n} = 2n \log_{10} {2} = 2n \log_{10} {\frac {10} {5}} = 2n (1 - \log_{10} {5}) = 2n - 2n \log_{10} {5}## (Eq. 2)

##n \log_{10} {5}## must be a real number and can therefore be written as ##n \log_{10} {5} = m + a## (Eq. 3)

where ##m \in \mathbb{N}_{0}## and ##0 \lt a \lt 1##. Here ##a## is the mantissa corresponding to ##x##. Note that ##a = 0## does not arise since ##5^n## is never expressible as an integer power of 10.

Combining equations (1), (2) and (3), we find that ##\log_{10} {4^n} = 2n - 2(m + a) = 2n - 2m - 2a## (Eq. 4)

Since ##\log_{10} {5} \approx 0.699##, we get ##0 \lt n \log_{10} {5} \lt n \Rightarrow m \in \{0, 1, ..., n-1\}##, i.e., ##m## is a non-negative integer less than ##n##, i.e. ##m \leq (n - 1) \Rightarrow 2n - 2m \geq 2##. Using this property in (Eq. 4), we see that ##\log_{10} {4^n}## can be written as ##p + 2 - 2a## where ##p## is a non-negative integer given by ##(2n - 2m - 2)##.

Given that ##0 \leq a \lt 1##, we consider two subcases and express the mantissa of ##4^n## in terms of the mantissa of ##5^n##:
  1. ##0 < a < 0.5 \Rightarrow 0 < 2a < 1##. In this case, ##\log_{10} {4^n}## can be expressed as ##(p + 1) + b## where ##b = (1-2a) \in (0, 1)##. Here the fraction ##b = (1-2a)## is the mantissa
  2. ##0.5 \leq a < 1 \Rightarrow 1 \leq 2a < 2##. In this case, ##\log_{10} {4^n}## can be expressed as ##p + b## where ##b = (2-2a) \in (0, 1)##. Here the fraction ##b = (2-2a)## is clearly the mantissa
Thus, if we know the mantissa corresponding to ##5^n##, then the mantissa corresponding to ##4^n## is uniquely determined.

We now consider various possible values for the first digit of ##5^n## (obviously that digit is determined uniquely by ##n##), find what the corresponding range of values for mantissa ##a## would be, derive the possible range of values of ##b## (mantissa of ##4^n##) for the given range of values of ##a## and therefore find what are the possible values for the first digit of ##4^n##. Note: The table gives only approximate values for the fractions in the range (as most of those values are irrational numbers), but the ranges are such that even with the approximation, the first digits can be determined without error.

First digit of ##5^n##Range of ##a##Range of ##b##Possible values for first digit of ##4^n##
1##(\log_{10} {1}, \log_{10} {2}) = (0, 0.301)####(1 - 2 \times 0.301, 1 - 2 \times 0) = (0.3979, 1)##, i.e. ##b > 0.3979##Integers less than 10 and greater than ##10^{0.3979}##, i.e. ##\{2, 3, 4, ..., 9\}##
2##(\log_{10} {2}, \log_{10} {3}) = (0.301, 0.477)####(1 - 2 \times 0.477, 1 - 2 \times 0.301) = (0.046, 0.3979)####\{1, 2\}##
3##(\log_{10} {3}, \log_{10} {4}) = (0.477, 0.602)####(1 - 2 \times 0.5, 1 - 2 \times 0.477)## and ##(2 - 2 \times 0.602, 2 - 2 \times 0.5)##
i.e. ##(0, 0.046)## and ##(0.7959, 1)##
##\{1, 6, 7, 8, 9\}##
4##(\log_{10} {4}, \log_{10} {5}) = (0.602, 0.699)####(2 - 2 \times 0.699, 2 - 2 \times 0.602) = (0.602, 0.7959)####\{4, 5, 6\}##
5##(\log_{10} {5}, \log_{10} {6}) = (0.699, 0.778)####(2 - 2 \times 0.778, 2 - 2 \times 0.699) = (0.4437, 0.602)####\{2, 3, 4\}##
6##(\log_{10} {6}, \log_{10} {7}) = (0.778, 0.845)####(2 - 2 \times 0.845, 2 - 2 \times 0.778) = (0.3098, 0.4437)####\{2\}##
7##(\log_{10} {7}, \log_{10} {8}) = (0.845, 0.903)####(0.1938, 0.3098)####\{1, 2\}##
8##(\log_{10} {8}, \log_{10} {9}) = (0.903, 0.954)####(0.0915, 0.1938)####\{1\}##
9##\log_{10} {9}, \log_{10} {10}) = (0.954, 1)####(0, 0.0915)####\{1\}##

From the above table, it is seen that only in cases where the first digit of ##5^n## is either 2 or 4 can the first digit of ##4^n## too take the same value (2 and 4 respectively). For values of ##n## that lead to first digit of ##5^n## being neither 2 nor 4, the values of ##4^n## would be such that their first digit will always be different from the first digit of ##5^n##. Hence the claim stated in the the question is proved.
This looks like the published solution, only that you made your life artificially difficult by dealing with logarithms and real numbers. You can do the same by setting
\begin{align*}
z\cdot 10^r &\leq 4^n=2^{2n}< (z+1)\cdot 10^r\\
z\cdot 10^s &\leq 5^n < (z+1)\cdot 10^s
\end{align*}
Then square the second and multiply both.
 
  • #34
137
55
##a+b+c+2 = abc \Rightarrow c = \dfrac{a+b+2}{ab-1}## (Eq. 1)

##(a+1)(b+1)(c+1)## can therefore be expressed as a function ##f## of variables ##a, b## alone.

##(a+1)(b+1)(c+1) \equiv f(a, b) = (a+1)(b+1)\left(\dfrac{a+b+2}{ab-1} + 1\right)##
##= (a+1)(b+1)\dfrac{(a+1)(b+1)}{ab-1} = \dfrac{(a+1)^2(b+1)^2}{ab-1}## (Eq. 2)

Since ##a, b > 0##, it follows that the numerator of (Eq. 1) is positive. Since we also need ##c > 0##, we also need denominator in that equation to be positive and hence we must have ##ab > 1##.

To find the minimum value of ##f(a, b)## for a fixed value of ##b##, find the partial derivative of this function w.r.t ##a## and equate to 0.##\dfrac {\partial f} {\partial a} = 0 \equiv \dfrac{(b+1)^2 (a+1) (ab - 2 - b)}{(ab-1)^2} = 0 \Rightarrow a = \dfrac{2+b}{b}## (Eq. 3)

That the above is a minimum, not a maximum, can be proven by looking at the sign of ##\dfrac{\partial^2 f} {\partial a^2}## at ##a = \frac{2+b}{b}##.
##\dfrac{\partial^2 f} {\partial a^2} = \dfrac{(b+1)^2}{(ab-1)^2} \left( \dfrac{-2b(a+1)(ab - 2 - b)}{ab - 1} + (2ab - 2) \right)##, which when evaluated at ##a = \dfrac{2+b}{b}## is equal to
##\dfrac{1}{b+1} \left( -2(2+2b)(2+b-2-b) + 2(b+1)^2 \right) = 2(b+1)##. Since this value is positive for any positive value of ##b## (in fact it is positive for ##b > -1##), ##a = \frac{2+b}{b}## must correspond to a local minimum, not a maximum.
##f(\frac{2+b}{b}, b)## is therefore minimum value of ##f(a, b)## for a specific value of ##b##, and for variable ##b##, these minima can be expressed as a function of ##b##.

##g(b) \equiv f(\frac{2+b}{b}, b) = \dfrac{4(b+1)^3}{b^2}##.
The minimum possible value of ##(a+1)(b+1)(c+1)## is the minimum value of ##f(a, b)## across all allowed values of ##a, b## and this is ##\min_{a>0, b>0} f(a, b) = \min_{b>0} f(\frac{2+b}{b}, b) = \min_{b>0} g(b)##

The minimum value of ##g(b)## for ##b > 0## can be found by finding the local minima of ##g(b)##.
##g'(b) = 0 \Rightarrow \dfrac{-8(b+1)^3}{b^3} + \dfrac{12(b+1)^2}{b^2} \Rightarrow \dfrac{(b+1)^2}{b^3}(4b-8) = 0 \Rightarrow b=2## (Eq. 4)

That the above is a local minimum, not a maximum, can be seen by evaluating ##g''(b)## at ##b=2## and noting that ##g''(b=2)## is a positive value (##\frac{9}{2} = 4.5## if I calculated correctly).

Thus, the minimum value of ##(a+1)(b+1)(c+1)## that meets the conditions stated in the question is ##g(2) = \dfrac{4(2+1)^3}{2^2} = 3^3 = 27##. This proves that ##(a+1)(b+1)(c+1) \geq 27## for the stated conditions and that the minimum value of 27 is achieved when ##b=2## whereby using (Eq. 2) and (Eq. 1) we get the corresponding values of ##a, c## both to be 2, i.e. ##a=b=c=2## gives the minimum value for the expression.
 

Related Threads on Math Challenge - October 2020

Replies
42
Views
8K
Replies
61
Views
2K
Replies
71
Views
7K
Replies
60
Views
5K
Replies
150
Views
11K
Replies
156
Views
11K
  • Last Post
3
Replies
61
Views
7K
Replies
98
Views
7K
Replies
137
Views
12K
M
Replies
64
Views
10K
Top