Challenge Math Challenge - February 2021

[Not anonymous]

Spoiler: Question 12

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)} = \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.

 

[fresh_42]

Spoiler: Question 12

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.

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$

 

[Not anonymous]

Spoiler: Question 11

Let $x$ be the number formed by the first (leftmost) $n$ digits of $z$ and let $y$ be the number formed by removing those first $n$ digits from $z$. For example, if $z=54321$ (this is not a 1995-digit number but using this just for illustration) and $n=2$, then $x$ and $y$ would be 54 and 321 respectively. A 1995-digit $z$ and the corresponding $z^{[n]}$ can be expressed in terms of $x, y$ as $z = 10^{1995-n}x + y$, and $z^{[n]} = 10^{n}y + x$. The difference between the 2 numbers is #### $d = z^{[n]} - z = (10^{n} - 1)y - (10^{1995-n} - 1)x$.

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.
####

 

[fresh_42]

Spoiler: Question 11

Let $x$ be the number formed by the first (leftmost) $n$ digits of $z$ and let $y$ be the number formed by removing those first $n$ digits from $z$. For example, if $z=54321$ (this is not a 1995-digit number but using this just for illustration) and $n=2$, then $x$ and $y$ would be 54 and 321 respectively. A 1995-digit $z$ and the corresponding $z^{[n]}$ can be expressed in terms of $x, y$ as $z = 10^{1995-n}x + y$, and $z^{[n]} = 10^{n}y + x$. The difference between the 2 numbers is #### $d = z^{[n]} - z = (10^{n} - 1)y - (10^{1995-n} - 1)x$.

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.
####

Looks o.k.

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

 

[Not anonymous]

Spoiler: Question 13

$(x_{0}, x_{1}, x_{2}, ...)$ is an infinite sequence but since $x_{i}$'s can take only a finite number of values ($x_{i} \in \{0, 1, ..., m-1\} \, \forall i$) there can only be a finite number of distinct values for pairs of adjacent elements in the sequence. Also, the complete sequence, or any subsequence of contiguous elements is completely determined by the first 2 elements. Thus there must be some $p \geq 0, q > 0$ such that the finite subsequence $(x_{p}, x_{p+1}, ..., x_{p+q})$ starts repeating to form the rest of the sequence, i.e. $x_{p+q+1} = x_{p}, x_{p+q+2} = x_{p+1}$ and so on.

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$

 

[fresh_42]

Spoiler: Question 13

$(x_{0}, x_{1}, x_{2}, ...)$ is an infinite sequence but since $x_{i}$'s can take only a finite number of values ($x_{i} \in \{0, 1, ..., m-1\} \, \forall i$) there can only be a finite number of distinct values for pairs of adjacent elements in the sequence. Also, the complete sequence, or any subsequence of contiguous elements is completely determined by the first 2 elements. Thus there must be some $p \geq 0, q > 0$ such that the finite subsequence $(x_{p}, x_{p+1}, ..., x_{p+q})$ starts repeating to form the rest of the sequence, i.e. $x_{p+q+1} = x_{p}, x_{p+q+2} = x_{p+1}$ and so on.

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$

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$.

 

[Not anonymous]

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 contiguous subsequence $(0, 1, 1)$ occurs again in the full sequence. And I attempted to prove that by showing that the sequence can be viewed as consisting purely of a repeating subsequence (I consider only subsequences of length at least 2, hence $q >0$, and $j$ is the value of $q$ for the specific case of $p = t$) after some offset (at this point, the proof leaves open the possibility of the original sequence consisting of a prefix subsequence that does not repeat itself) and and then showing that $t=0$ is the smallest offset of such a repeating subsequence. And $t=0$ implies that the ordered contiguous pair $(0, 1)$ occurs again.

We already have a determined subsequence $(0,1,1)$ and it doesn't matter where it is

There is specifically a mention of $k \geq 1$ in the question, meaning we a looking for a repetition of $(0, 1, 1)$ after the subsequence starting $(x_{0}, x_{1}, x_{2})$. So shouldn't the proof show that $(x_{i}=0, x_{i+1}=1)$ occurs (again) for some $i > 0$?

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 contiguous elements, so it only attempts to show repetition of $(0, 1, 1)$, not $(0,\ldots,1,\ldots,1)$ with gaps between the indices of those 3 elements.

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 earliest repeating subsequence is a subsequence that starts with the pair $(x_{0}=0, x_{1}=1)$, thus proving that $(0, 1, 1)$ will occur again for some $k \geq 1$. This being the case, it is not clear why it is necessary to show that $j > 1$ leads to a contradiction. Please let me know if you need more clarification on some part of the proof or if I have got something wrong in the proof.

 

[Not anonymous]

A slightly different approach compared to my earlier answer for question 13. I hope the proof presented here will be clearer as it considers only repetition of pairs (instead of arbitrary length subsequences as in the earlier answer) in order to show the repetition of $(0, 1, 1)$.

Spoiler: Question 13

Consider all non-overlapping pairs of adjacent elements in the given sequence starting with $(x_{0}, x_{1})$, i.e. $\{(x_{i}, x_{i+1}) \, \forall i \in \{0, 2, 4, ...\}\}$. The number of pairs in the set if infinite, yet the number of distinct values a pair can take is finite - there are at most $m^{2}$ distinct pair values possible in any sequence consisting only of integers that are remainders of division by $m$. Thus there must be at least one pair, say $(x_{p}, x_{p+1}), p \in \{0, 2, 4, ...\}$, in the infinite pair set that repeats, i.e. there exists some $q \in \{2, 4, 6, ...\}$ such that $x_{p+q} = x_{p}$ and $x_{p+q+1} = x_{p+1}$.

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}$ (Eq. 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 (Eq. 1) and the fact that $x_{t+j} = x_{t}$ by definitions of $t, j$, we get $x_{t} = (x_{t+j-2} + x_{t-1}) \mod m$.

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}$ (Eq. 2)

From (Eq. 1) and (Eq. 2) it follows that $(x_{t-2}, x_{t-1})$ is also a repeating pair, i.e. a repeating pair is found at index $t-2$ that is smaller than $t$, contradicting the assumption that $t \geq 2$ is the smallest start index of a repeating pair. Hence we must have $t=0$ as the smallest start index of repeating pairs in the sequence, i.e. the pair value $(x_{0}=0, x_{1}=1)$ must occur again in the sequence. Thus there must be some $k \geq 2$ such that $x_{k}=0, x_{k+1}=1$. By definition of the sequence, $x_{k+2} = (x_{k}+x_{k+1}) \mod m = 1$ (as $m > 1$), and hence it follows that there exists a $k \geq 2$ such that $x_{k}=0, x_{k+1}=1, x_{k+2}=1$

 

[fresh_42]

Sorry, I don't understand why $t$ is not relevant to the proof.

Let's make an example and set $m=7$. Then we get as $(x_0,x_1,x_2,\ldots)$
$$
0,1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,\ldots
$$
and

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.$

asks for $k=16$, the subsequence $x_{16},x_{17},x_{18}.$However, you considered

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)

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$.

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?

 

[Not anonymous]

asks for $k=16$, the subsequence $x_{16}, x_{17}, x_{18}$.

Yes, that is my understanding too.

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$.

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.

 

[fresh_42]

That's why I said "I don't get it" and not that it is wrong. And I still can't follow you. You have all the necessary ingredients but your conclusion is strange. You assume a minimal starting point $t$ for a repetition and found a contradiction unless $t=0,$ i.e. $(x_1,x_2,x_3)=(0,1,1)$ which is also wrong.

How can you conclude that

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$

I can only see contradictions all over the place.

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.

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}
$$

 

[Not anonymous]

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 consecutive elements, repeats itself to fill the original sequence. I had pictured the sequence in mind in this diagrammatic way while arriving at 1st proof.

Using pigeonhole principle, the proof said that such a repeating subsequence must exist. And by proving (or rather by trying to prove, if the proof is indeed wrong for some reason even after correcting the above-mentioned typo) that $t=0$, it establishes that the pair-value $(0, 1)$ (again considering only a pair of adjacent elements) must occur more than once in the full sequence. And by definition of how the sequence is formed, if the adjacent elements pair $(0, 1)$ occurs at index pair $(k, k+1)$, then the 3-tuple $(0, 1, 1)$ occurs at the index triple $(k, k+1, k+2)$.

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.

 

[Not anonymous]

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.

Spoiler: Question 11

Say $a_{1994}a_{1993}..a_{0}$ is the decimal representation of $z$. Applying the cut and append operation with $n=1$ (i.e. cutting from the leftmost position and appending it to the right just one digit) on $z^{[1]}$ gives $a_{1992}a_{1991}..a_{1}a_{0}a_{1994}a_{1993}$ and this is the same as $z^{[2]}$. Repeating the same cut-and-append operation on $z^{[2]}$ gives $a_{1991}a_{1990}...a_{0}a_{1994}a_{1993}a_{1992}$ and this happens to be the same as $z^{[3]}$. We can generalize this and say that repeating $k$ times the cut-and-append with $n=1$ on successive numbers from this transformation, starting with $z$, yields $z^{[k]}$.

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.

 

[fresh_42]

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.

Spoiler: Question 11

Say $a_{1994}a_{1993}..a_{0}$ is the decimal representation of $z$. Applying the cut and append operation with $n=1$ (i.e. cutting from the leftmost position and appending it to the right just one digit) on $z^{[1]}$ gives $a_{1992}a_{1991}..a_{1}a_{0}a_{1994}a_{1993}$ and this is the same as $z^{[2]}$. Repeating the same cut-and-append operation on $z^{[2]}$ gives $a_{1991}a_{1990}...a_{0}a_{1994}a_{1993}a_{1992}$ and this happens to be the same as $z^{[3]}$. We can generalize this and say that repeating $k$ times the cut-and-append with $n=1$ on successive numbers from this transformation, starting with $z$, yields $z^{[k]}$.

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.

The "correct" way to write the modular arithmetic is
$$
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]}).$

 

[Not anonymous]

Spoiler: 15a

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.

 

[fresh_42]

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).

Yes, by the use of the fundamental theorem of arithmetic, i.e. by observing that squares have an even number of each prime.

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.

 

[Not anonymous]

Does question 15(b) need an answer not expressed in terms of $(4+\sqrt{18})$? If yes, may I get some hint?

Spoiler: Question 15(b)

Let $m \in \mathbb{R}_{+}$ be the value for which $2^{m} = (4+\sqrt{18})^{n}$. Applying logarithm on both sides, we get $m \log {2} = n \log {(4+\sqrt{18})} \Rightarrow m = n \dfrac {\log {(4+\sqrt{18})}} {\log {2}}$. The largest integer power of 2 that divides $(4+\sqrt{18})^n$ must therefore be $\lfloor m \rfloor = \left\lfloor n \dfrac {\log {(4+\sqrt{18})}} {\log {2}} \right\rfloor \approx \lfloor 3.043106606 \times n \rfloor$

 

[fresh_42]

Does question 15(b) need an answer not expressed in terms of $(4+\sqrt{18})$? If yes, may I get some hint?

Spoiler: Question 15(b)

Let $m \in \mathbb{R}_{+}$ be the value for which $2^{m} = (4+\sqrt{18})^{n}$. Applying logarithm on both sides, we get $m \log {2} = n \log {(4+\sqrt{18})} \Rightarrow m = n \dfrac {\log {(4+\sqrt{18})}} {\log {2}}$. The largest integer power of 2 that divides $(4+\sqrt{18})^n$ must therefore be $\lfloor m \rfloor = \left\lfloor n \dfrac {\log {(4+\sqrt{18})}} {\log {2}} \right\rfloor \approx \lfloor 3.043106606 \times n \rfloor$

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.$

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.