Floor sequence

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

va2010

1276 posts

va2010

#1 h Jul 7, 2016, 9:20 PM • 11 Y

Y by mathmaths, Davi-8191, llpllp, itslumi, Adventure10, centslordm, TFIRSTMGMEDALIST, megarnie, nmoon_nya, Mango247, chakrabortyahan

Determine all positive integers $M$ such that the sequence $a_0, a_1, a_2, \cdots$ defined by $a_0 = M + \frac{1}{2} \qquad \textrm{and} \qquad a_{k+1} = a_k\lfloor a_k \rfloor \quad \textrm{for} \, k = 0, 1, 2, \cdots$ contains at least one integer term.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ABCDE

1963 posts

ABCDE

#2 h Jul 7, 2016, 9:32 PM • 26 Y

Y by v_Enhance, shinichiman, PRO2000, claserken, programjames1, pablock, MathbugAOPS, yunseo, Leartia, Pluto1708, Tenee, Kamran011, mathleticguyyy, fukano_2, A-Thought-Of-God, Adventure10, centslordm, ZHEKSHEN, normalqher, Infinityfun, levifb, GioOrnikapa, Aopamy, nmoon_nya, GMMeowChand, ZZzzyy

The answer is all $M>1$ . Clearly, $M=1$ fails, as the sequence is just going to be all $\frac{3}{2}$ . To show that all $M>1$ work, we induct on $v_2(M-1)$ . If $v_2(M-1)=0$ , then $M$ is even, and we have that $a_1=M(M+\frac{1}{2})$ is an integer as desired. If $v_2(M-1)=k>0$ , then $a_1=M(M+\frac{1}{2})=\frac{2M^2+M-1}{2}+\frac{1}{2}=N+\frac{1}{2}$ , and $v_2(N-1)=v_2(\frac{2M^2+M-3}{2})=v_2(\frac{(2M+3)(M-1)}{2})=k-1$ , so we can shift the sequence and reduce to the case of $v_2(M-1)=k-1$ . Hence, $a_{k+1}$ will be an integer as desired.

This post has been edited 1 time. Last edited by ABCDE, Jul 7, 2016, 9:33 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

navi_09220114

487 posts

navi_09220114

#4 h Jul 8, 2016, 3:35 AM • 2 Y

Y by Adventure10, Luchitha2

The answer is all positive integers $M\ge 2$ . Call an positive integer $M$ good if such term exist, and bad otherwise. We prove that $1$ is the only bad positive integer.

Notice that for any $k$ , $\frac{2k+1}{2}\lfloor {\frac{2k+1}{2}} \rfloor=\frac{k(2k+1)}{2}\in \mathbb{N}\iff k\enspace\text{is even.}$
So all even numbers are good. Now consider $k$ be an odd integer, then $\frac{k(2k+1)}{2}=\frac{2(k^2+\lfloor \frac{k}{2}\rfloor)+1}{2}$ So $k$ is good $\iff$ $k^2+\lfloor \frac{k}{2}\rfloor$ is good.

Now notice that if $k$ is in the form of $4p+3$ , then $(4p+3)^2+\lfloor \frac{4p+3}{2}\rfloor$ is even, so $4p+3$ is good for all $p$ . Now suppose $k$ is in the form $2^{i+1}p+(2^i+1)$ , and suppose all numbers in the form $2^ip+(2^{i-1}+1)$ is good. Then notice that $(2^{i+1}p+(2^i+1))^2+\lfloor\frac{2^{i+1}p+(2^i+1)}{2} \rfloor\equiv 1+2^{i-1}\pmod {2^i}$ which is in the form of $2^ip+(2^{i-1}+1)$ , which is good. So all numbers in the form of $2^{i+1}p+(2^i+1)$ is good as well.

Note that any odd integer $k$ at least $2$ can be written as $k=2^{i+1}p+(2^i+1)$ for some suitable $i, p$ , because we can take $i=v_2(k-1)$ and then $p$ follows directly. So this proves that all $M\ge 2$ are good. For $M=1$ , then $a_i=\frac{3}{2}$ for all $i$ , so $M=1$ is bad. So the answer is all positive integers $M\ge 2$ .

This post has been edited 2 times. Last edited by navi_09220114, Jul 8, 2016, 3:35 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kezer

986 posts

Kezer

#5 h Jul 8, 2016, 11:50 AM • 2 Y

Y by Adventure10, Mango247

This was also German TSTST #4

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

WizardMath

2487 posts

WizardMath

#6 h Jul 8, 2016, 12:14 PM • 2 Y

Y by Adventure10, Mango247

Just notice that if we assume to the contrary that this is not true then the greatest integers less than each of the terms should be odd which is easily proven to be true if and only if the sequence is constant.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

zamfiratorul

136 posts

zamfiratorul

#7 h Jul 8, 2016, 9:05 PM • 1 Y

Y by Adventure10

I thinck this works : Call a number bad if it does not respect the statement . Then prove by induction that all candidates for bad numbers must be of the form $2^n + 1$ . So now if we have a bad number $M$ then $M - 1$ is divizible with every power of $2$ so $M = 1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

zamfiratorul

136 posts

zamfiratorul

#8 h Jul 8, 2016, 9:09 PM • 1 Y

Y by Adventure10

I made a typo : there should be $2^n k + 1$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rkm0959

1721 posts

rkm0959

#9 h Jul 9, 2016, 2:26 PM • 3 Y

Y by biomathematics, Adventure10, Mango247

The answer is all $M>1$ . We induct on $v_2(M-1)$ .
If $v_2(M-1)=0$ , i.e. $M$ is even, then $\lfloor a_0 \rfloor \equiv 0 \pmod{2}$ , so we are clear on $a_1$ .
Suppose the sequence has at least one integer term if $v_2(M-1)=k-1$ .
We prove the statement when $v_2(M-1)=k$ .
Let $M=2^kn+1$ . Then $a_1=(2^kn+1)^2 + \frac{2^kn+1}{2} = (2^{2k}n^2+2^{k+1}n+2^{k-1}n)+\frac{1}{2}$ .
Now note that $v_2(2^{2k}n^2+2^{k+1}n+2^{k-1}n)=k-1$ , so by shifting the indices we are good to go.

So pretty much the first integer comes up is $a_{v_2(M-1)+1}$ I guess?

This post has been edited 1 time. Last edited by rkm0959, Jul 9, 2016, 2:26 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

huricane

670 posts

huricane

#10 h Jul 9, 2016, 3:09 PM • 3 Y

Y by Adventure10, Mango247, RobertRogo

For $M=1$ we obtain $a_k=\frac{3}{2}\not\in\mathbb{Z},\forall k\ge 0$ ,so $1$ does not satisfy the given condition.

We will now prove that any integer $M>1$ satisfies the given condition.
Suppose that there exists an integer $M>1$ such that the sequence $(a_k)$ doesn't contain any integer term.In this case it's obvious that all the terms of the sequence will be of the form $t+\frac{1}{2},t\in\mathbb{Z}$ .
$a_1=M^2+\frac{M}{2}\not\in\mathbb{Z}$ ,so $M\equiv 1\pmod{2}$ i.e. $\lfloor a_0\rfloor\equiv 1\pmod{2}$ .By looking at $a_1$ and $a_2$ ,we obtain,in a similar fashion,that $\lfloor a_1\rfloor\equiv 1\pmod{2}$ i.e. $M^2+\frac{M-1}{2}\equiv 1\pmod{2}$ or $M\equiv 1\pmod{4}$ i.e. $\lfloor a_0\rfloor\equiv 1\pmod{4}$ .
By the same argument as above we conclude that $\lfloor a_1\rfloor\equiv 1\pmod{4}$ or $M^2+\frac{M-1}{2}\equiv 1\pmod{4}$ ,which implies that $M\equiv 1\pmod{8}$ (we used $M\equiv 1\pmod{4}$ ).
By repeating this over and over again we obtain that $M\equiv 1\pmod{2^n},\forall n\in\mathbb{N}$ ,so $M=1$ ,contradiction!

Hence the answer:All positive integers $M>1$ satisfy the given condition.

This post has been edited 1 time. Last edited by huricane, Jul 9, 2016, 3:10 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

biomathematics

2568 posts

biomathematics

#11 h Jul 11, 2016, 2:39 PM • 3 Y

Y by PRO2000, Adventure10, Mango247

Just a gist:

1)Clearly, there is no integer term in the sequence for $M=1$ .

2) For $M >1$ , let $2^{\alpha}||(M-1)$ . Then $a_{\alpha +1}$ is an integer.

3) To prove the second point, note that if $a_{t} = 2^{j}*k_{t} + 1.5$ for some positive integer $j$ and odd natural $k_{t}$ , then $a_{t+1}$ is of the form $2^{j-1}*k_{t+1} +1.5$ for odd natural $k_{t+1}$ .

This post has been edited 1 time. Last edited by biomathematics, Jul 11, 2016, 2:39 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kezer

986 posts

Kezer

#12 h Aug 11, 2016, 9:21 PM • 2 Y

Y by Adventure10, Mango247

Had I solved this one in December, then I would've made it into the German IMO TST group but well I failed back then. Now I've come back and have found a solution in quite a short while. Would've been more use to me, if that was 9 months ago, though.

We'll prove that all $M \geq 2$ satisfy the conditions. It is easy to show that $M=1$ is not a solution. So we'll now prove that all $M \geq 2$ actually are solutions. Assume the contrary. So suppose there is a $M \geq 2$ , such that all numbers $a_0,a_1,a_2,\dots$ are not integers. Since $a_0=\tfrac{2M+1}{2}$ and $a_{k+1}=a_k \cdot \lfloor a_k \rfloor$ only multiplies the previous number of the sequence with a integer, all numbers $a_0,a_1,a_2,\dots$ are of the form $\tfrac{p}{2}$ where $\gcd{(p,2)}=1$ . Thus $\lfloor a_k \rfloor a_k = a_k-\frac12$ . By simple induction we can then get $a_{k+1}=a_k \cdot \left(a_0^{k+1}-\frac12 a_0^k-\frac12 a_0^{k-1}-\dots-\frac12 \right).$ Let $b_k = a_0^k-\frac12 a_0^{k-1}-\frac12 a_0^{k-2}-\dots-\frac12 \quad \text{for } k \geq 1.$ It then suffices to show that there is a number in the sequence $(b_k)_{k \in \mathbb{N}}$ that is even to get the desired contradiction, as it then follows that $a_k$ is an integer. Again, assume the contrary, in specific that all number $b_1,b_2,b_3,\dots$ are uneven. Then $b_{n+1}-b_n$ is even for all positive integers $n$ . Now note $\begin{align*} b_{n+1}-b_n &= a_0^{n+1}-\frac32 a_0^n \\ &= \left(\frac{2M+1}{2} \right)^{n+1}-\frac32 \left(\frac{2M+1}{2} \right)^{n} \\&= \left(\frac12 \right)^{n+1} \left((2M+1)^{n+1}-3 \cdot (2M+1)^n \right)\end{align*}$ It thus suffices to show that there is a $n$ such that $v_2 \left((2M+1)^{n+1}-3 \cdot (2M+1)^n \right) = n+1$ as then $b_{n+1}-b_n$ would be uneven. But note $v_2 \left((2M+1)^{n+1}-3 \cdot (2M+1)^n \right) = v_2 \left((2M+1)^{n}(M-1) \cdot 2 \right) = v_2 (M-1) +1$ For $M \geq 2$ the term $v_2(M-1)$ takes an positive integral value. Thus, we can choose $n := v_2(M-1)$ and will hence have found the desired contradiction.
With that, we're done and indeed all $M \geq 2$ are solutions.

This post has been edited 1 time. Last edited by Kezer, Aug 13, 2016, 1:59 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sardor

801 posts

Sardor

#13 h Aug 12, 2016, 4:34 PM • 2 Y

Y by Adventure10, Mango247

This was also Uzbekistan TST P2.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

B101099

65 posts

B101099

#14 h Sep 1, 2016, 3:19 PM • 1 Y

Y by Adventure10

Answer:all $M>1$ .
If $M$ =1,then $a_i$ = $\frac{3}{2}$ $\forall$ $i$ $\in$ $\mathbb{N}$ $_0$ .
If $M$ is even,then $a_1$ = $a_0$ $\lfloor$ $a_0$ $\rfloor$ =( $M$ + $\frac{1}{2}$ ) $\lfloor$ $M$ + $\frac{1}{2}$ $\rfloor$ = $M^2$ + $\frac{M}{2}$ is an integer.
$Lemma1$ :If $a_i$ is such that $\lfloor$ $a_i$ $\rfloor$ is even,then $a_{i+1}$ $\in$ $\mathbb{Z}$ .
$Proof$ : $a_{i+1}=a_i$ $\lfloor$ $a_i$ $\rfloor$ = $a_{i-1}$ $\lfloor$ $a_{i-1}$ $\rfloor$ $\lfloor$ $a_i$ $\rfloor$ = $\dots$ = $a_0$ $\lfloor$ $a_0$ $\rfloor$ $\dots$ $\lfloor$ $a_i$ $\rfloor$ , $\lfloor$ $a_i$ $\rfloor$ $\in$ $\mathbb{Z}$ $a_0$ $\lfloor$ $a_i$ $\rfloor$ =( $2M+1$ ) $\frac{1}{2}$ $\lfloor$ $a_i$ $\rfloor$ is an integer,hence $a_{i+1}$ $\in$ $\mathbb{Z}$ .
Now assume that $M$ is odd, $M$ = $2^lk+1$ ,where $l$ $\in$ $\mathbb{N}$ and $k$ is an odd possitive integer.
$Lemma2$ :If $a_i$ = $2^x$ $k$ +1+ $\frac{1}{2}$ ,where $k$ $\in$ $\mathbb{N}$ is odd and $x$ $\in$ $\mathbb{N}$ then $a_{i+1}$ = $2^{x-1}m+1+\frac{1}{2}$ ( $m$ is an odd integer).
$Proof$ : $a_{i+1}$ = $a_i$ $\lfloor$ $a_i$ $\rfloor$ =( $2^x$ $k$ $+1+$ $\frac{1}{2}$ )( $2^x$ $k$ $+1$ )= $2^{x-1}k(2^{x+1}k+2^2+1$ )+1+ $\frac{1}{2}$ = $2^{x-1}m+1+$ $\frac{1}{2}$ .
Now $a_0$ = $M$ + $\frac{1}{2}$ = $2^lk+1+$ $\frac{1}{2}$ .By $Lemma2$ $a_1$ = $2^{l-1}y+1+$ $\frac{1}{2}$ $\Rightarrow$ $a_2$ = $2^{l-2}z+1+$ $\frac{1}{2}$ $\Rightarrow$ $\dots$ $\Rightarrow$ $a_l$ = $2^{0}t+1+$ $\frac{1}{2}$ $\Leftrightarrow$ $\lfloor$ $a_l$ $\rfloor$ = $k+1$ is even (since $k$ is odd),hence by $Lemma1$ $a_{l+1}$ is an integer.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sa2001

281 posts

sa2001

#15 h Apr 5, 2018, 6:36 PM • 2 Y

Y by Adventure10, Mango247

Another proof (because, why not?)

Consider the sequence $\{b_i\}$ , such that $a_i = \frac{b_i}{2}$ for all non-negative integers $i$ .

We prove the following lemma using induction:

Lemma:
If ${a_i}$ is not an integer for any non-negative integer $i$ , then for all natural numbers $n$
$b_i \equiv 3 mod 2^n$
Proof:

Base case: $n = 1$ is easy to see.

Induction step:

Suppose our lemma is true for $n = j$ ; $j \geq 1$
We'll prove it for $n = j + 1$

Using our induction hypothesis, for any non-negative integer $i$ :
$b_i = 2^j \cdot k + 3$ for some integer $k$

Then, $b_{i+1} = (2^j \cdot k + 3)(2^{j-1} \cdot k + 1)$

Using $b_{i+1} \equiv 3 mod 2^j$ , we get $k = 2l$ for some integer $l$

This implies $b_i \equiv 2^{j+1} \cdot l + 3 \equiv 3 mod 2^{n+1}$ , as required.

Using the above lemma, if no $a_i$ is an integer, then for all natural numbers $n$ :
$(2M + 1) \equiv 3 mod 2^n$
This is possible iff $(2M + 1) - 3 = 0$ , i.e. $M = 1$
It's easy to see that no $a_i$ is an integer for $M = 1$

Therefore, the answer is all natural numbers greater than $1$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Smita

514 posts

Smita

#16 h May 24, 2018, 12:03 PM • 2 Y

Y by Adventure10, Mango247

Sorry I don't know latex
Here is my solution it is beautiful.
{} Denotes floor function

Assume that Ax is the required no. Then we have Ax=A(x-1)*{A(x-1)}
And A(x-1)= A(x-2){A(x-2)} and similarly we get
Ax=A0*({A1}*{A2}....{Ax+1}) since Ax is integer we want any of the term {Ak} to be even so it can cancel out with the 2 in the denominator of (2m+1)/2 which can be shown easily.

This post has been edited 1 time. Last edited by Smita, May 24, 2018, 12:03 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2534 posts

joshualiu315

#85 h Nov 25, 2023, 6:03 AM

Y by

We claim the answer is $\boxed{M>1}$ . Clearly $M=1$ does not have an integer term as every term is $\frac{3}{2}$ .

Now, consider $\nu_2(M-1)$ . We would eventually want it to equal $0$ since that would be equivalent to $M$ being even, which is a vacuous case.

If $\nu_2(M-1) \neq 0$ ,

$a_1 = M \left(M+\frac{1}{2} \right) = \frac{2M^2+M-1}{2} + \frac{1}{2}.$
Letting $\frac{2M^2+M-1}{2}=N$ , we have that

$\nu_2(N-1) = \nu_2\left(\frac{2M^2+M-3}{2}\right) = \nu_2((2M+3)(M-1))-1 = \nu_2(M-1)-1.$
Thus, we can repeat this process until the value equals $0$ , at which point the term will be an integer.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kamatadu

481 posts

kamatadu

#86 h Dec 31, 2023, 4:58 PM

Y by

All integers $M>1$ work. If $M$ is even, $a_1 \in \mathbb Z$ . Otherwise assume $M=2^k\cdot m + 1$ where $k\ge 1$ is maximal and so $m$ is odd.

I claim that $a_{k+1} \in \mathbb{Z}$ .

Proof follows by using induction on $k$ . For $k=0$ , $M=m+1$ where $m$ is odd. Thus $a_0 = m+1 + \dfrac{1}{2}$ , $a_1 = \left(m+1 + \frac{1}{2}\right)(m+1) = (m+1)^2 +\frac{m+1}{2}$ which is an integer as $m$ is odd.

Now we assume for $k$ and prove it for $k+1$ .

We have $a_0 = 2^{k+1}m + 1 + \frac{1}{2}$ , $a_1 = \left(2^{k+1}m + 1 + \frac{1}{2}\right)(2^{k+1}m+1) = 2^{2(k+1)}m^2 + 2^{k+2}m + 1 + 2^k m + \frac{1}{2} = 2^{k+2}(2^{k}m^2 + m) + \left(2^km + 1 + \frac{1}{2}\right)$ .

Firstly note that $2^{k+2}(2^{k}m^2 + m)$ is an integer itself. Now note that after each move, the power of two in $2^{k+2}(2^{k-1}m^2 + m)$ decreases at most by $1$ due to the $2$ in the denominator after multiplication. So after $k+1$ moves, the power of $2$ remaining in it is at least $2^1$ . But note that after $k+1$ moves, the $2^km + 1 + \frac{1}{2}$ turns into an integer due to induction hypothesis. Thus we are done. :yoda:

This post has been edited 2 times. Last edited by kamatadu, Dec 31, 2023, 5:01 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blueprimes

363 posts

blueprimes

#87 h Jan 3, 2024, 2:12 AM

Y by

We claim the the answer is $M \ge 2$ . It is clear that $M = 1$ is invalid, as all terms are $\frac{3}{2}$ and thus will never become integer.

For the sake of contradiction, assume for some $M \ge 2$ , we have $a_k = b_k + \frac{1}{2}$ for all nonnegative integers $k$ , such that $b_k$ is an integer. Then all $b_k$ are odd, otherwise an integer term would exist. Then
$b_{k + 1} + \frac{1}{2} = b_k \left(b_k + \frac{1}{2} \right) \implies 2b_{k + 1} = 2b_k^2 + b_k - 1.$ Now taking the difference from $k = t, t + 1$ yields
$2b_{t + 2} - 2b_{t + 1} = (b_{t + 1} - b_t)(2b_{t + 1} + 2b_t + 1).$ Since $M \ne 1$ , all $b_i$ are distinct, so $2 \cdot \frac{b_{t + 2} - b_{t + 1}}{b_{t + 1} - b_t}$ is an odd integer for all nonnegative integers $t$ , implying that $\nu_2(b_{k + 1} - b_k)$ decreases as we progress through the sequence. At some point, we reach a sufficient $k = m$ where $b_{m + 1} - b_m$ must be odd, a contradiction as all $b_k$ are odd. Our proof is complete.

This post has been edited 2 times. Last edited by blueprimes, Jan 3, 2024, 2:14 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EpicBird08

1758 posts

EpicBird08

#88 h Mar 6, 2024, 9:11 PM

Y by

The answer is $M \ge 2.$

The first thing is to prove that $M = 1$ doesn't work. This is clear, since $a_0 = \frac{3}{2},$ so $a_1 = 1 \cdot \frac{3}{2} = \frac{3}{2}$ and the sequence is always a constant non-integer.

Now we show that all other $M$ work.

Claim: Write $M = b \cdot 2^c + 1$ for $b$ odd. Then $a_{c+1}$ is an integer.

Proof: We induct on $c.$ The base case $c = 0$ is obvious since $M$ is even and thus $M(M+0.5) = a_1$ is an integer.
Now suppose that the claim holds for $c = k-1;$ we will use it to show that the claim holds for $c = k.$

We start with the number $a_0 = M + \frac{1}{2} = b \cdot 2^c + \frac{3}{2}.$ Then
$\begin{align*} a_1 &= \left(b \cdot 2^c + \frac{3}{2}\right)(b \cdot 2^c + 1) \\ &= b^2 \cdot 2^{2c} + b \cdot 2^c + 3b \cdot 2^{c-1} + \frac{3}{2} \\ &= (b^2 \cdot 2^{c+1} + 2b + 3b) \cdot 2^{c-1} + \frac{3}{2} \\ &= (b^2 \cdot 2^{c+1} + 5b) \cdot 2^{c-1} + 1 + \frac{1}{2}. \end{align*}$ Note that $b^2 \cdot 2^{c+1} + 5b$ is odd since $b$ is odd. Applying the inductive hypothesis on $a_1$ as the starting term gives us that $a_{1+k}$ is an integer. The induction is complete. $\square$

Therefore, $a_{c+1}$ is an integer, so all $M \ge 2$ work. These are the only solutions, and we are done.

This post has been edited 1 time. Last edited by EpicBird08, Mar 6, 2024, 9:12 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

qwerty123456asdfgzxcvb

1088 posts

qwerty123456asdfgzxcvb

#89 h Mar 6, 2024, 9:51 PM

Y by

Claim: if M-1 has v_2 of n, then we win in n+2 steps.
For example if M is 9 mod 16 then M-1 has v_2 of 3, and after one step we go to a number with integer part 5 mod 8, then a number with integer part 3 mod 4, then a number with even integer part, then we finally get to an integer.

Note that the union of numbers cong to 0 mod 2, numbers congruent to 3 mod 4, 5 mod 8, etc etc give you every number except 1, by CRT.

The proof is trivial induction. The base cases for 3 mod 4, even integer part, integer are trivial. Thus we want to prove that if M = 2^n + 1 (mod 2^(n+1)), then the next element in the sequence has integer part M_1 = 2^(n-1) + 1 (mod 2^(n)),

Expanding (M)(M+0.5) in mod 2^(n+1) gets us 2^(2n)+2^(n+1)+1 + 2^(n-1) + 0.5, which reduces to 1 + 2^(n-1) + 0.5 (mod 2^(n+1), and all numbers like this have integer part 1 + 2^(n-1) + k*2^(n+1), and taking this mod 2^n finishes the induction.

Trivial problem. Thus we have a construction for all numbers except 1, which gets stuck at 1.5 forever.

This post has been edited 2 times. Last edited by qwerty123456asdfgzxcvb, Mar 6, 2024, 9:52 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Markas

150 posts

Markas

#90 h May 26, 2024, 5:29 PM

Y by

We have that $a_0 = M + \frac{1}{2} = \frac{2M + 1}{2}$ $\Rightarrow$ if M is even we have that $a_1 = \frac{2M + 1}{2}\cdot M$ and since $2 \mid M$ , we have that $a_1$ is an integer. So obviously every even M works. Now assume M is odd. For M = 1, it doesn't work. Now we will prove by induction that each M works.

Claim: For all $M > 1$ , we will always get an integer.

We will now induct on $\nu_2(M-1)$ . If it is 0, then it becomes an integer in one step and if not, then the next term will be $\frac{2M^2+M}{2} = \frac{2M^2+M-1}{2}+\frac {1}{2}$ $\Rightarrow$ if $\frac{2M^2+M-1}{2} = K$ , we have that $\nu_2(K-1) = \nu_2((M-1)(2M-3)/2) = \nu_2(M-1)-1$ , so the value reduces and the inductive hypothesis will end.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RedFireTruck

4255 posts

RedFireTruck

#91 h Jun 27, 2024, 9:44 PM

Y by

We claim it is all $\boxed{M>1}$ .

Clearly $M=1$ fails because $a_i=\frac32$ for all $i$ .

Clearly all even $M$ work because $a_1=M^2+\frac{M}{2}$ . Therefore, assume $M$ odd.

Since $M$ is odd, we can let $M=2k+1$ . Then, $a_1=(2k+\frac32)(2k+1)=4k^2+5k+\frac32=(k+1)(4k+1)+\frac12$ .

Since $(k+1)(4k+1)$ is even when $k$ is odd, an odd $M$ works if $k=\frac{M-1}2$ is odd.

Otherwise, $k$ is not odd, so let $k=2j$ . Then $a_1=(2j+1)(8j+1)+\frac12$ .

Since $\frac{(2j+1)(8j+1)-1}{2}=8j^2+5j$ is odd when $j$ is odd, an odd $M$ works if $j=\frac{M-1}{4}$ is odd.

Otherwise, $j$ is not odd, so let $k=4j$ . Then, $a_1=(4j+1)(16j+1)+\frac12$ .

Since $\frac{(4j+1)(16j+1)-1}4=16j^2+5j$ is odd when $j$ is odd, an odd $M$ works if $j=\frac{M-1}{8}$ is odd.

Let $k=2^nj$ and assume that an odd $M$ works when $\frac{M-1}{2^n}$ is odd for $n\ge 3$ . Then, $a_1=(2^nj+1)(2^{n+2}j+1)+\frac12$ .

Since $\frac{(2^nj+1)(2^{n+2}j+1)-1}{2^n}=2^{n+2}j^2+5j$ is odd when $j$ is odd, an odd $M$ works if $j=\frac{M-1}{2^{n+1}}$ is odd.

By induction, an odd $M$ works when $\frac{M-1}{2^a}$ is odd for some integer $a\ge 1$ . This is clearly true for all odd $M>1$ , as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1327 posts

ezpotd

#92 h Sep 17, 2024, 5:10 PM

Y by

The answer is all $M > 1$ .

To see that $M = 1$ fails, note that $a_0 = \frac 32$ and $a_1 = \frac 32$ , so the sequence is constant.

Now we show that $M > 1$ works. The denominator of the sequence is always either $2$ or $1$ (trivial by induction).Now we rephrase the problem in terms of the number on the numerator while the denominator is constant, consider the sequence $b$ where $b_0 = 2M + 1$ . Then if $b_i \equiv 1 \mod 4$ , $i$ is the last element of the sequence, otherwise we have $a_{i + 1} = \frac{b_i}{2} (\frac{b_i - 1}{2})= \frac{b^2_i - b_i}{4}$ , so $b_{i + 1} = \frac 12 (b^2_i - b_i)$ . Now we show that $\nu_2 (b_i - 3)$ decreases by $1$ for each increment in $i$ . At some point this forces $b_i \equiv 1 \mod 4$ and we are done. Let $\nu_2 (b_i - 3) = c$ , then we have $b_i \equiv 2^{c} + 3 \mod 2^{c + 1}$ , so we know $b_{i + 1} = (2^cx + 2^{c -1} + 1)(2^{c + 1}x + 2^c + 3) = 2^{c} (\mathrm{stuff}) + 3*2^{c - 1} +3$ which is $2^{c - 1} + 3 \mod 2^{c}$ , so $\nu_2 (b_{i + 1} - 3) = c - 1$ as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

smileapple

1010 posts

smileapple

#94 h Jan 2, 2025, 1:21 AM

Y by

The answer is all $M>1$ . Clearly $M=1$ does not satisfy the desired condition, and $a_1$ is an integer for all even $M$ .

Suppose that $a_k=N+\frac12$ for any index $k$ and odd $N\ge3$ . Then $a_{k+1}=\frac{(N-1)(2N+3)}2+\frac32$ , so that $\nu_2(a_{k+1}-\frac32)=\nu_2(a_k-\frac32)-1$ . Hence, for some large index $k'$ we have $\nu_2(a_{k'}-\frac32)=0$ , implying that $a_{{k'}+1}$ is an integer. Setting $(M,0)=(N,k)$ for any odd $M\ge3$ finishes. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AshAuktober

1015 posts

AshAuktober

#95 h Jan 9, 2025, 9:05 PM

Y by

Originally solved as part of Rohan Goyal's "Sequences" Lecture at the 2024 India IMO Training Camp.
We find all $M$ such that no term in the sequence is an integer.
Indeed, we claim that $2^n \mid M-1$ for all $n$ . The proof is by induction.
Obviously $M$ is odd, else $a_1 \in \mathbb{Z}$ .
Now assume that $2^n \mid M-1$ . Then note that shifting the sequence as $a_{k+1} \to a_k$ , we must have $\lfloor a_1 \rfloor \equiv 1 \pmod{2^n}$ .
As it turns out, this is nothing but $$\frac{2M^2 + M-1}{2} \equiv 1 \pmod{2^n} \implies 2^{n+1} \mid (2M+3)(M-1) \implies 2^{n+1} \mid M-1$ as desired, But now $M-1$ has infinite $\nu_2$, so $M = 1$ is the only value for which no term is an integer. And indeed no term is an integer then as the sequence consists wholely of $\frac 32$. Thus the final answer is $M \in \mathbb{N} \setminus \{1\}$.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eg4334

639 posts

eg4334

#96 h Jan 11, 2025, 7:43 PM

Y by

The answer is all $\boxed{M > 1}$ . $M=1$ obviously does not work. The idea is casework on $v_2(M-1)$ . If $M-1 = b \cdot 2^c$ for $b$ odd, then I claim $a_{c+1}$ is the desired integer. The most straightforward way to do so is induction. The $c=0$ case is immediate from $a_1 = M^2 + \frac{M}{2}$ . If we suppose that it is true for $c=k$ , we wish to prove it is so for $c=k+1$ . For $M = b \cdot 2^{k+1}+1$ , then $a_1 = (b \cdot 2^{c+1}+1)^2 + b \cdot 2^c + \frac12$ which when viewing $M ' = (b \cdot 2^{c+1}+1)^2 + b \cdot 2^c$ has $v_2(M'-1) = c$ . Using our inductive hypothesis finishes.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

577 posts

Maximilian113

#97 h Jan 15, 2025, 9:02 PM

Y by

Clearly if $M$ is even $a_1$ is an integer. If $M \equiv 3 \pmod 4,$ then write $M=4m-1,$ then $a_1=(4m-1)(4m-1/2)=16m^2-6m+1/2,$ which has an even integer part so $a_2$ is an integer.

Now, suppose that $M \equiv 1 \pmod 4,$ and $M > 1.$ For the sake of a contradiction, assume that none of the terms will be integers. Then clearly all $\lfloor a_k \rfloor \equiv 1 \pmod 4.$ Write $M=4m+1,$ we have that $a_1=(4m+1)(4m+3/2) = 16m^2+10m+3/2.$ Hence $m$ is even. Let $m=2m_0.$ Then we can write $a_1=4(16m_0^2+5m_0)+1+1/2.$ Similar to above, for $\lfloor a_2 \rfloor \equiv 1 \pmod 4$ we must have that $m_0$ is even, so continuing this logic eventually yields a contradiction as $v_2(M-1)$ is finite.

Thus we have shown that all positive integers $M \geq 2$ work. Clearly, $M=1$ does not work as $a_k = \frac32$ for all $k,$ so $M \geq 2$ are the only solutions.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

math-olympiad-clown

48 posts

math-olympiad-clown

#98 h Apr 20, 2025, 7:04 AM

Y by

We claim that the sequence contains an integer term if and only if $M \geq 2$ .
**Proof:**

Let us first observe the behavior of the sequence:
Initially, $a_0 = M + \frac{1}{2}$ , which is a half-integer.
At each step, $a_{k+1} = a_k \left\lfloor a_k \right\rfloor$ .

Now, notice:
- If $a_k$ is a half-integer and $\left\lfloor a_k \right\rfloor$ is even, then $a_{k+1}$ is an integer.
- Otherwise, the sequence continues multiplying half-integers by integers.

**Case 1: $M = 1$ **

Then,

$a_0 = \frac{3}{2}, \quad \left\lfloor a_0 \right\rfloor = 1$ and for all $k \geq 0$ ,
$a_{k+1} = a_k \times 1 = a_k$
Thus, the sequence remains constant at $\frac{3}{2}$ forever, never reaching an integer.

**Case 2: $M \geq 2$ **

Then,

$a_0 = M + \frac{1}{2}, \quad \left\lfloor a_0 \right\rfloor = M$
Now, consider

$a_1 = \left( M + \frac{1}{2} \right) \times M$
If $M$ is even, then $M \times \frac{1}{2}$ is an integer, so $a_1$ is an integer.

If $M$ is odd, then $M \times \frac{1}{2}$ is a half-integer, but multiplying it by $M$ (which is at least 3) in the next steps ensures that eventually we will multiply a half-integer by an even integer, making the product an integer.

This is because in any finite sequence of multiplications by integers $\geq 2$ , the product's denominator (which starts as 2) will eventually be canceled once an even factor appears.

Since $M \geq 2$ , either $M$ is even (done in one step) or we multiply a half-integer by increasing integers, and since after at most one multiplication by an even number the product becomes an integer, the sequence must eventually reach an integer.

**Final Answer:**
All positive integers $M \geq 2$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mathgloggers

94 posts

Mathgloggers

#99 h May 4, 2025, 4:53 PM

Y by

We will write our sequence from $a_3= M^2 +\lceil \frac{M}{2} \rceil$
$M=2^M.k+1$

Motivation:
Notice that we ought to make the numerator inside the "gif" function to be even but because of an odd factor and rest even terms it becoming odd. So we have to keep continueing our steps till we remove all the powers of 2 from one of those even numbers

$a_3= M^2 + \frac{M}{2} =(2^m(k)+1)^2+2^{m-1}k+\frac{1}{2}$ Now when we take gif of the function " $\frac{1}{2}$ " term vanishes and rest of the term becomes odd, So it does not cancel out with factor $2$ in denominator of the next term.

$a_4= (M^2 + \frac{M}{2} ) \lceil M^2 + \frac{M}{2} \rceil$
Now here is the induction step where everything remains same when we take the gif of $a_4$ but only thing remains : $\lceil \frac{ M^2 + \frac{M}{2}}{2} \rceil =\frac{(2^m(k)+1)^2+2^{m-1}k}{2}$ now notice that that the
$2^{m-1}(k)$ is reducing by a factor of $2$ every time.

Now just induct for $k'=m$ and observe that the $2^{m-1}k$ would all be reduced to $k$ which is odd and hence we are done at $a_{k+1}$ where the even term in numerator would get cancelled with the factor of $2$ in denominator .

So we can find at least one integer as $m \in Z^{+}$

OOPS: it should be floor function in place of ceil function I checked it later .

This post has been edited 2 times. Last edited by Mathgloggers, May 4, 2025, 4:55 PM
Reason: d

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

heheman

1007 posts

heheman

#100 h May 22, 2025, 7:57 PM

Y by

cool problem

The answer is $n > 1$ . Even $n$ clearly work. For odd $n = 2k+1$ , note that the second term is $(2k+1)(2k+1+\frac{1}{2}) = 4k^2+5k+1+\frac{1}{2}$ . So if $k$ is odd then $4k^2+5k+1$ is even so we're done. So suppose $k$ is even. Note that from $2k+1$ goes to $2(2k^2+\frac{5}{2}k)+1$ . So the term that's multiplied by $2$ decreases in $v_2$ every time until it becomes odd, unless $k=0$ (which is the case for $n=1$ .) So we're done.

Z K Y