It's February and we'd love to help you find the right course plan!

G
Topic
First Poster
Last Poster
k a February Highlights and 2025 AoPS Online Class Information
jlacosta   0
Feb 2, 2025
We love to share what you can look forward to this month! The AIME I and AIME II competitions are happening on February 6th and 12th, respectively. Join our Math Jams the day after each competition where we will go over all the problems and the useful strategies to solve them!

2025 AIME I Math Jam: Difficulty Level: 8* (Advanced math)
February 7th (Friday), 4:30pm PT/7:30 pm ET

2025 AIME II Math Jam: Difficulty Level: 8* (Advanced math)
February 13th (Thursday), 4:30pm PT/7:30 pm ET

The F=ma exam will be held on February 12th. Check out our F=ma Problem Series course that begins February 19th if you are interested in participating next year! The course will prepare you to take the F=ma exam, the first test in a series of contests that determines the members of the US team for the International Physics Olympiad. You'll learn the classical mechanics needed for the F=ma exam as well as how to solve problems taken from past exams, strategies to succeed, and you’ll take a practice F=ma test of brand-new problems.

Mark your calendars for all our upcoming events:
[list][*]Feb 7, 4:30 pm PT/7:30pm ET, 2025 AIME I Math Jam
[*]Feb 12, 4pm PT/7pm ET, Mastering Language Arts Through Problem-Solving: The AoPS Method
[*]Feb 13, 4:30 pm PT/7:30pm ET, 2025 AIME II Math Jam
[*]Feb 20, 4pm PT/7pm ET, The Virtual Campus Spring Experience[/list]
AoPS Spring classes are open for enrollment. Get a jump on 2025 and enroll in our math, contest prep, coding, and science classes today! Need help finding the right plan for your goals? Check out our recommendations page!

Don’t forget: Highlight your AoPS Education on LinkedIn!
Many of you are beginning to build your education and achievements history on LinkedIn. Now, you can showcase your courses from Art of Problem Solving (AoPS) directly on your LinkedIn profile! Don't miss this opportunity to stand out and connect with fellow problem-solvers in the professional world and be sure to follow us at: https://www.linkedin.com/school/art-of-problem-solving/mycompany/ Check out our job postings, too, if you are interested in either full-time, part-time, or internship opportunities!

Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1
Monday, Feb 3 - May 19
Sunday, Mar 2 - Jun 22
Friday, Mar 28 - Jul 18
Sunday, Apr 13 - Aug 10

Prealgebra 1 Self-Paced

Prealgebra 2
Sunday, Feb 16 - Jun 8
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10

Prealgebra 2 Self-Paced

Introduction to Algebra A
Sunday, Feb 16 - Jun 8 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)
Sunday, Mar 23 - Jul 20
Monday, Apr 7 - Jul 28

Introduction to Algebra A Self-Paced

Introduction to Counting & Probability
Sunday, Feb 9 - Apr 27 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)
Sunday, Mar 16 - Jun 8
Wednesday, Apr 16 - Jul 2

Introduction to Counting & Probability Self-Paced

Introduction to Number Theory
Sunday, Feb 16 - May 4
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3

Introduction to Algebra B
Thursday, Feb 13 - May 29
Sunday, Mar 2 - Jun 22
Monday, Mar 17 - Jul 7
Wednesday, Apr 16 - Jul 30

Introduction to Algebra B Self-Paced

Introduction to Geometry
Friday, Feb 14 - Aug 1
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1

Intermediate: Grades 8-12

Intermediate Algebra
Wednesday, Feb 12 - Jul 23
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13

Intermediate Counting & Probability
Monday, Feb 10 - Jun 16
Sunday, Mar 23 - Aug 3

Intermediate Number Theory
Thursday, Feb 20 - May 8
Friday, Apr 11 - Jun 27

Precalculus
Tuesday, Feb 25 - Jul 22
Sunday, Mar 16 - Aug 24
Wednesday, Apr 9 - Sep 3

Advanced: Grades 9-12

Olympiad Geometry
Wednesday, Mar 5 - May 21

Calculus
Friday, Feb 28 - Aug 22
Sunday, Mar 30 - Oct 5

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Tuesday, Feb 4 - Apr 22
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2

MATHCOUNTS/AMC 8 Advanced
Sunday, Feb 16 - May 4
Friday, Apr 11 - Jun 27

AMC 10 Problem Series
Sunday, Feb 9 - Apr 27
Tuesday, Mar 4 - May 20
Monday, Mar 31 - Jun 23

AMC 10 Final Fives
Sunday, Feb 9 - Mar 2 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)

AMC 12 Problem Series
Sunday, Feb 23 - May 11

AMC 12 Final Fives
Sunday, Feb 9 - Mar 2 (3:30 - 5:00 pm ET/12:30 - 2:00 pm PT)

Special AIME Problem Seminar B
Sat & Sun, Feb 1 - Feb 2 (4:00 - 7:00 pm ET/1:00 - 4:00 pm PT)

F=ma Problem Series
Wednesday, Feb 19 - May 7

Programming

Introduction to Programming with Python
Sunday, Feb 16 - May 4
Monday, Mar 24 - Jun 16

Intermediate Programming with Python
Tuesday, Feb 25 - May 13

USACO Bronze Problem Series
Thursday, Feb 6 - Apr 24

Physics

Introduction to Physics
Friday, Feb 7 - Apr 25
Sunday, Mar 30 - Jun 22

Physics 1: Mechanics
Sunday, Feb 9 - Aug 3
Tuesday, Mar 25 - Sep 2

Relativity
Sat & Sun, Apr 26 - Apr 27 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
0 replies
jlacosta
Feb 2, 2025
0 replies
Find the maximum (45)
sqing   2
N a few seconds ago by RagvaloD
Source: Tsinghua University Mathematics Camp 2014 ,Q3
For any integer $n\ge 2$ have $\left[\frac{n}{\sqrt{3}}\right] +1>\frac{n^2}{\sqrt{3n^2-k}}$ . Find the maximum value of the positive integer $k$.
2 replies
sqing
Nov 14, 2014
RagvaloD
a few seconds ago
Evaluate: $\sum_{r=0}^{10} \binom{20-r}{10}\binom{20+r}{20} $
pankajsinha   6
N a few seconds ago by Tewkesbury
Evaluate using combinatorial argument
$$\sum_{r=0}^{10} \binom{20-r}{10}\binom{20+r}{20} $$The given answer is $\binom{41}{31}$.

My Attempt:

Overall it appears that $30$ objects are being selected from total of $40$ objects. So these $40$ objects are divided into two lots of $20-r$ and $20+r$ objects. After this I am not able to establish the reasoning to arrive at the given answer. It appears to be combination of Van-der-Monde's Identity and Hockey- Stick Identity.
6 replies
pankajsinha
Nov 16, 2024
Tewkesbury
a few seconds ago
P6 Geo Finale
math_comb01   7
N 3 minutes ago by GuvercinciHoca
Source: XOOK 2025/6
Let $ABC$ be a triangle with incenter $I$ and excenters $I_A$, $I_B$, $I_C$ opposite to $A,B,C$ respectively. Suppose $BC$ meets the circumcircle of $I_AI_BI_C$ at points $D$ and $E$. $X$ and $Y$ lie on the incircle of $\triangle ABC$ so that $DX$ and $EY$ are tangents to the incircle (different from $BC$). Prove that the circumcircles of $\triangle AXY$ and $\triangle ABC$ are tangent.

Proposed by Anmol Tiwari
7 replies
math_comb01
Feb 10, 2025
GuvercinciHoca
3 minutes ago
A functional equation
super1978   1
N 14 minutes ago by pco
Source: Somewhere
Find all functions $f: \mathbb R \to \mathbb R$ such that:$$ f(f(y-x)-xf(y))+f(x)=y(1-f(x)) $$for all $x,y \in \mathbb R$
1 reply
super1978
an hour ago
pco
14 minutes ago
No more topics!
An eventually periodic recursive sequence involving floor function
Photaesthesia   11
N Jan 8, 2025 by neon_paradox
Source: 2025 China Mathematical Olympiad Day 1 Problem 1
Let $\alpha > 1$ be an irrational number and $L$ be a integer such that $L > \frac{\alpha^2}{\alpha - 1}$. A sequence $x_1, x_2, \cdots$ satisfies that $x_1 > L$ and for all positive integers $n$, \[ x_{n+1} = \begin{cases} \left \lfloor \alpha x_n \right \rfloor & \textup{if} \; x_n  \leqslant L \\\left \lfloor \frac{x_n}{\alpha} \right \rfloor & \textup{if}  \; x_n  > L \end{cases}. \]Prove that
(i) $\left\{x_n\right\}$ is eventually periodic.
(ii) The eventual fundamental period of $\left\{x_n\right\}$ is an odd integer which doesn't depend on the choice of $x_1$.
11 replies
Photaesthesia
Nov 27, 2024
neon_paradox
Jan 8, 2025
An eventually periodic recursive sequence involving floor function
G H J
G H BBookmark kLocked kLocked NReply
Source: 2025 China Mathematical Olympiad Day 1 Problem 1
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Photaesthesia
94 posts
#1 • 1 Y
Y by Jupiterballs
Let $\alpha > 1$ be an irrational number and $L$ be a integer such that $L > \frac{\alpha^2}{\alpha - 1}$. A sequence $x_1, x_2, \cdots$ satisfies that $x_1 > L$ and for all positive integers $n$, \[ x_{n+1} = \begin{cases} \left \lfloor \alpha x_n \right \rfloor & \textup{if} \; x_n  \leqslant L \\\left \lfloor \frac{x_n}{\alpha} \right \rfloor & \textup{if}  \; x_n  > L \end{cases}. \]Prove that
(i) $\left\{x_n\right\}$ is eventually periodic.
(ii) The eventual fundamental period of $\left\{x_n\right\}$ is an odd integer which doesn't depend on the choice of $x_1$.
This post has been edited 2 times. Last edited by Photaesthesia, Nov 27, 2024, 7:43 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
EthanWYX2009
814 posts
#2 • 5 Y
Y by internationalnick123456, Photaesthesia, axsolers_24, LLL2019, ereh
(i) is trivial since $x_n$ is bounded. Call $x_n>L$ big and small othersise, then we prove big turns to small, small turns to small iff $x_n=\lfloor\frac{\alpha}{\alpha -1}\rfloor ,$ and if small never turns to small the number keeps decreasing and get contradiction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
YaoAOPS
1453 posts
#3 • 1 Y
Y by axsolers_24
We ignore (i) because its trivial. Here's a pretty sus solution which might be wrong but probably encapsulates the main idea.

WLOG we can take $L < x_1 < \left\lceil \alpha L \right\rceil$ else we can take the first term which satisfies so. Then we define
\[
L_1 = \left\{\left\lfloor \frac{L}{\alpha} \right\rfloor\right\}, L_2 = \left[\left\lceil \frac{L}{\alpha} \right\rceil, L\right], L_3 = \left[L+1, \left\lfloor \alpha L \right\rfloor\right]
\]Then $x_i$ just alternates
\[
L_3 \mapsto L_2 \mapsto L_2 \dots
\]under the operation. Note that the operation $L_3 \mapsto L_2 \mapsto L_3$ is strictly decreasing so eventually it jumps $L_3 \mapsto L_1$ or $L_2 \mapsto L_2$ as exactly one of $\left\lfloor\frac{L+1}{\alpha}\right\rfloor < \left\lceil \frac{L}{\alpha} \right\rceil$ or $\left\lfloor \alpha \left\lceil \frac{L}{\alpha} \right\rceil \right\rfloor < L + 1$ holds. In the first case the sequence contains $L_1$ and is thus always the same, and is odd since it has one $L_1$ and paired $L_2, L_3$. In the case of $L_2 \mapsto L_2$ this means that the sequence contains $\left\lceil \frac{L}{\alpha} \right\rceil$ and is thus always the same, and cyclic because $L_2$ repeats itself iff when that happens.
This post has been edited 1 time. Last edited by YaoAOPS, Nov 27, 2024, 4:38 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
lbh_qys
311 posts
#5
Y by
YaoAOPS wrote:
We ignore (i) because its trivial. Here's a pretty sus solution which might be wrong but probably encapsulates the main idea.

WLOG we can take $L < x_1 < \left\lceil \alpha L \right\rceil$ else we can take the first term which satisfies so. Then we define
\[
L_1 = \left\{\left\lfloor \frac{L}{\alpha} \right\rfloor\right\}, L_2 = \left[\left\lceil \frac{L}{\alpha} \right\rceil, L\right], L_3 = \left[L+1, \left\lfloor \alpha L \right\rfloor\right]
\]Then $x_i$ just alternates
\[
L_3 \mapsto L_2 \mapsto L_2 \dots
\]under the operation. Note that the operation $L_3 \mapsto L_2 \mapsto L_3$ is strictly decreasing so eventually it jumps $L_3 \mapsto L_1$ or $L_2 \mapsto L_2$ as exactly one of $\left\lfloor\frac{L+1}{\alpha}\right\rfloor < \left\lceil \frac{L}{\alpha} \right\rceil$ or $\left\lfloor \alpha \left\lceil \frac{L}{\alpha} \right\rceil \right\rfloor < L + 1$ holds. In the first case the sequence contains $L_1$ and is thus always the same, and is odd since it has one $L_1$ and paired $L_2, L_3$. In the case of $L_2 \mapsto L_2$ this means that the sequence contains $\left\lceil \frac{L}{\alpha} \right\rceil$ and is thus always the same, and cyclic because $L_2$ repeats itself iff when that happens.

It is actually possible to uniformly use \(\lfloor (L+1)/\alpha \rfloor\) as the same element.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MathLuis
1424 posts
#6
Y by
Seeing this graphically and also trying examples does help a lot, in fact it's the main motivation/idea to make progress on this.
(i) is trivial because of bounded eventually, so for (ii) we consider a number line where $L$ is in "the middle" and numbers on the left are greater than $L$ and number from $L$ to the right are smaller than $L$ notice that from the left for any $x_i$ where jumping to the right started, the main observations to be made is that if in a process we go from left to right and right to left, next time we go left to right, the resulting number is decreased by exactly $1$ unit. This is because like if you had $\left \lfloor \frac{x_n}{\alpha} \right \rfloor=k \le L$ then $x_n$ lies on $((k+1)\alpha, k\alpha)$, but then $\lfloor \alpha k \rfloor$ is the first integer below the range of the $x_n$ (so it obviously lies on $(k \alpha, (k-1) \alpha)$ (which contains an integer at least as $\alpha>1$)) which would mean that when this number jumps to the right again (which has to because its smaller than the first one that jumped to the right) then it lands exactly on $k-1$, now if we never had a case where right jumps to right then $k$ would constsntly decreasing until becoming zero in which case period if $1$, so assume this doesn't happen, then whenever it first reaches an $l$ for which $\lfloor \alpha l \rfloor$ is still on the right, then you do process one again and then whatever is on the left still goes to the right as it is the result of launching something to the right by $\alpha$ minus some (mostly likely) small constant.
They key part is that this $l$ is unique because as we have seen previously, from some value $k$ taken after two steps it decreases by exactly one unit, however we have to verify that we don't need over $3$ steps to launch the value $l$ back to the left so first start by noticing that from the problem condition no value below $\left \lfloor \frac{\alpha}{\alpha-1} \right \rfloor \ge 1$ is taken for size reasons so notice $l$ is the first ever positive integer for which you have to jump twice which means that $\lfloor \alpha (l+1) \rfloor \ge L+1$, so if we suddently have that $L \ge \lfloor \alpha \lfloor \alpha l \rfloor \rfloor$, then notice that $l \ge \left \lceil \frac{L+1}{\alpha} \right \rceil-1$ so in fact from the definition of $l$ equality is true which then gives that $\left \lfloor \frac{L}{\alpha} \right \rfloor \ge \lfloor \alpha l \rfloor -1$, now let $\ell$ be a positive integer such that $\lfloor (\ell+1)\alpha \rfloor>L \ge \lfloor \ell \alpha \rfloor$ then $\ell \ge \left \lfloor \alpha \cdot  \left \lfloor \frac{L+1}{\alpha} \right \rfloor \right \rfloor \ge \lfloor \alpha \cdot \ell \rfloor$ as $L+1 \ge \lceil \alpha \ell \rceil$ which means that $\frac{1}{\alpha-1}>\ell$, but this can't be possible as we get that $\frac{\alpha^2}{\alpha-1}>(\ell+1)\alpha>L$ contradiction the problem condition, thus we are done :cool:.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
KuroNeko2007
46 posts
#7 • 1 Y
Y by Levieee
I don't understand how (i) is trivial if the sequence is bounded.
If we consider the sequence of digits of pi, each term is bounded, but the sequence is non-periodic since pi is irrational.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
lbh_qys
311 posts
#8
Y by
KuroNeko2007 wrote:
I don't understand how (i) is trivial if the sequence is bounded.
If we consider the sequence of digits of pi, each term is bounded, but the sequence is non-periodic since pi is irrational.

Because $x_{n+1}$ is integer and only need $x_n$
This post has been edited 1 time. Last edited by lbh_qys, Dec 19, 2024, 7:29 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awesomeming327.
1646 posts
#9
Y by
The sequence is eventually periodic because it is bounded by $\lfloor \max(x_1,\alpha L)\rfloor$, so it can only take on finitely many values. Call $x_i$ big if $x_i>L$ and small otherwise. Let $D$ be the smallest index such that $x_D$ is small. $D$ must exist otherwise $x_n$ is strictly decreasing, contradiction. Hereby assume $i>D$.

Claim: For all big numbers $x_i$, $x_{i+1}$ is small.
Let $i$ be the smallest index such that $x_i$ and $x_{i+1}$ are both big. Then, $x_{i-1}$ is small. We have
\[x_i=\lfloor \alpha x_i \rfloor<\alpha x_i\le \alpha L\implies x_{i+1}<\left\lfloor\frac{\alpha L}{\alpha} \right\rfloor\]so $x_{i+1}$ is small, contradiction.

Claim: If $x_i$ and $x_{i+2}$ are big, then $x_{i+2}<x_i$.
Note that $x_{i+1}$ is small. We have
\[x_{i+1}=\left\lfloor\frac{x_i}{\alpha} \right\rfloor<\frac{x_i}{\alpha}\implies x_{i+2}=\lfloor \alpha x_{i+1}\rfloor<\alpha x_{i+1}<x_i\]as desired.

Claim: There exists at most one value of $x_i$ that is small such that $x_{i-1}$ is big but $x_{i+1}$ is small.
We have $x_{i+1}\le L$. Since $x_{i}$ is small,
\[\lfloor \alpha x_{i} \rfloor\le L\implies \alpha x_{i} < L+1\implies x_{i} <\frac{L+1}{\alpha}\]Since $x_{i-1}$ is big,
\[x_{i-1}\ge L+1\implies x_i=\left\lfloor \frac{x_{i-1}}{\alpha}\right \rfloor > \frac{L+1}{\alpha}-1\]The difference between the strict upper and lower bounds of $x_i$ is one. Therefore, $x_i$ attains at most one value.

Claim: There does not exist any values $x_i$ that are small such that $x_{i-1}$ and $x_{i+1}$ are both small.
Assume that $i$ does exist and is minimal, then $x_{i-2}$ is big. Then $x_{i-1} =\frac{L+y}{\alpha}-1$ for some $y>1$ so
\[x_{i}>\left\lfloor \alpha x_{i-1}\right\rfloor=\left\lfloor \alpha \frac{L+y}{\alpha}-\alpha\right\rfloor=\left\lfloor L+y-\alpha\right\rfloor = L - \lceil \alpha-y \rceil > L-\lceil \alpha\rceil +1>L-\alpha+1\]This implies that
\[L\ge x_{i+2}>\alpha(L-\alpha+1)-1\]which ends up being a contradiction to the bound given in the problem.
Construct a colored directed graph over all the positive integers such that $x_i\to x_{i+1}$ is red if $x_i$ is big and blue if $x_i$ is small. We have already suggested that starting from any vertex and following the edges, the path eventually cycles. Note that if a cycle goes $\text{red}\to\text{blue}$ alternating only, then the source of all red edges decreases strictly, which cannot happen. Therefore, there must be at least one $\text{blue} \to \text{blue}$. By our previous two claims, there must be at most one $\text{blue}\to \text{blue}$. Therefore, each cycle alternates except at one point, so each cycle is the same odd cycle. We are done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Levieee
94 posts
#10 • 1 Y
Y by Lhaj3
>opens thread cuz found the sum too hard
>someone calls it trivial
>FML
This post has been edited 1 time. Last edited by Levieee, Jan 3, 2025, 10:09 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Fibonacci_math
37 posts
#11 • 1 Y
Y by Levieee
Let $S = [\lfloor (L+1)/\alpha\rfloor, \lfloor (L+1)\alpha\rfloor]\cap\mathbb{N}, \ A = [\lfloor (L+1)/\alpha\rfloor, L]\cap\mathbb{N}, \ B = [L+1, \lfloor (L+1)\alpha\rfloor]\cap\mathbb{N}$

Claim 1: if $x_1$ is greater than $\lfloor (L+1)\alpha\rfloor$, then there exists $k>1$ such that $\lfloor x_k/\alpha\rfloor\in B$.
Proof: Note that if $x_i>L$, then $x_{i+1}=\lfloor x_i/\alpha\rfloor<x_i$ (as $\alpha>1$). But, there are only finitely many integers between $L$ and $x_1$. Hence there must exist $n>1$ such that $x_n\le L$ and $x_{n-1}>L$. So, we get $x_{n-1}\le\lfloor (L+1)\alpha\rfloor$. So, $x_{n-1}\in B$.

Claim 2: if $x_1$ is lesser than $\lfloor (L+1)/\alpha\rfloor$, then there exists $k>1$ such that $\lfloor x_k/\alpha\rfloor\in A$.
Proof: Note that if $x_i<L$, then $x_{i+1}=\lfloor x_i\alpha\rfloor>x_i$ (as $\alpha>1$). But, there are only finitely many integers between $L$ and $x_1$. Hence there must exist $n>1$ such that $x_n\ge L+1$ and $x_{n-1}\le L$. So, we get $x_{n-1}>\lfloor (L+1)/\alpha\rfloor$. So, $x_{n-1}\in A$.

Observe that if $x_k\in A$, then $x_{k+1}\in B$; and if $x_k\in B$, then $x_{k+1}\in A$. Also, there are finitely many integers in $S=A\cup B$. So, $\{x_i\}$ must be eventually periodic.

Now consider the following bipartite graph with vertex sets as $A$ and $B$. We draw an edge directed from $a$ and $b$ if and only if $\exists \ i\ge 1$ such that $x_i=a$ and $x_{i+1}=b$. Clearly, there cannot be an edge between two elements of $A$ or two elements of $B$. Also, note that there is exactly one cycle in this directed bipartite graph as the sequence becomes eventually periodic. Since the graph is bipartite, the length of the cycle must be even. So, the fundamental period of the sequence, which is just 1 less than the cycle length, will be odd.
https://external-preview.redd.it/Vt8un6DvXelUjrQPqHsJXaIijhQIMDRU50RjKVXe2JM.jpg?auto=webp&s=fbd4da7e4d2893906b86cebbff64976f0e1c03e2
This post has been edited 1 time. Last edited by Fibonacci_math, Jan 4, 2025, 4:58 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Levieee
94 posts
#12
Y by
Fibonacci_math wrote:
Let $S = [\lfloor (L+1)/\alpha\rfloor, \lfloor (L+1)\alpha\rfloor]\cap\mathbb{N}, \ A = [\lfloor (L+1)/\alpha\rfloor, L]\cap\mathbb{N}, \ B = [L+1, \lfloor (L+1)\alpha\rfloor]\cap\mathbb{N}$

Claim 1: if $x_1$ is greater than $\lfloor (L+1)\alpha\rfloor$, then there exists $k>1$ such that $\lfloor x_k/\alpha\rfloor\in B$.
Proof: Note that if $x_i>L$, then $x_{i+1}=\lfloor x_i/\alpha\rfloor<x_i$ (as $\alpha>1$). But, there are only finitely many integers between $L$ and $x_1$. Hence there must exist $n>1$ such that $x_n\le L$ and $x_{n-1}>L$. So, we get $x_{n-1}\le\lfloor (L+1)\alpha\rfloor$. So, $x_{n-1}\in B$.

Claim 2: if $x_1$ is lesser than $\lfloor (L+1)/\alpha\rfloor$, then there exists $k>1$ such that $\lfloor x_k/\alpha\rfloor\in A$.
Proof: Note that if $x_i<L$, then $x_{i+1}=\lfloor x_i\alpha\rfloor>x_i$ (as $\alpha>1$). But, there are only finitely many integers between $L$ and $x_1$. Hence there must exist $n>1$ such that $x_n\ge L+1$ and $x_{n-1}\le L$. So, we get $x_{n-1}>\lfloor (L+1)/\alpha\rfloor$. So, $x_{n-1}\in A$.

Observe that if $x_k\in A$, then $x_{k+1}\in B$; and if $x_k\in B$, then $x_{k+1}\in A$. Also, there are finitely many integers in $S=A\cup B$. So, $\{x_i\}$ must be eventually periodic.

Now consider the following bipartite graph with vertex sets as $A$ and $B$. We draw an edge directed from $a$ and $b$ if and only if $\exists \ i\ge 1$ such that $x_i=a$ and $x_{i+1}=b$. Clearly, there cannot be an edge between two elements of $A$ or two elements of $B$. Also, note that there is exactly one cycle in this directed bipartite graph as the sequence becomes eventually periodic. Since the graph is bipartite, the length of the cycle must be even. So, the fundamental period of the sequence, which is just 1 less than the cycle length, will be odd.
https://external-preview.redd.it/Vt8un6DvXelUjrQPqHsJXaIijhQIMDRU50RjKVXe2JM.jpg?auto=webp&s=fbd4da7e4d2893906b86cebbff64976f0e1c03e2

waow :o :o :o :o
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
neon_paradox
27 posts
#13
Y by
$(i)$ is trivial by noting that $x_n$ is bounded. Let $d$ denote the maximal value that is at most $L$ that appears in the sequence. WLOG $x_1=d$. Note the bound on $L$ ensures that all elements of the sequence are positive.
Note that if we have $x_j\leq L,x_{j+1}>L$, then $x_j > \frac{\lfloor \alpha x_j\rfloor }{\alpha}> \frac{\alpha x_j - 1}{\alpha}>x_j - 1$ hence $x_{j+2}=\lfloor\frac{\lfloor \alpha x_j\rfloor }{\alpha}\rfloor = x_j-1$. Then, there must exist a minimal index $m$ with $x_3=d-1, x_5=d-2, \dots x_{2m+1}=d-m$ and $x_{2m+2}\leq L$. In this case, $d=x_1 \geq x_{2m+2} \geq x_{2m+1}$ implying that there is an index $1 \leq i \leq m$ s.t. $x_{2i+1}=x_{2m+2}$.
Check that $x_{2i+1}>x_{2i+3}> \dots >x_{2m+1}$ and $x_{2m+2}<x_{2m}< \dots <x_{2i+2}$ implying the value $x_{2i+1}$ does not appear again between these 2 occurrences, thus the sequence has fundamental period $(2m+2)-(2i+1)$.

Observe $x_{2m}=\lfloor (d-m+1) \alpha \rfloor > L, x_{2m+2} = \lfloor (d-m) \alpha \rfloor \leq L$ implies $d-m+1=\lceil \frac{L}{\alpha} \rceil$ and $x_{2i+1}=d-i=x_{2m+2}=\lfloor (\lceil \frac{L}{\alpha} \rceil - 1 ) \alpha \rfloor$ implying $m-i=(d-i)-(d-m)$ is only dependent on $\alpha$ and $L$, thus so is the fundamental period (which is clearly odd).
Z K Y
N Quick Reply
G
H
=
a