Equal pairs in continuous function

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Equal pairs in continuous function

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

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

994 posts

#1 h Aug 6, 2018, 3:12 PM • 2 Y

Y by Adventure10, Mango247

Let $f(x)$ be an continuous function defined in $\text{[0,2015]},f(0)=f(2015)$
Prove that there exists at least $2015$ pairs of $(x,y)$ such that $f(x)=f(y),x-y \in \mathbb{N^+}$

Z K Y

The post below has been deleted. Click to close.

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

994 posts

#2 h Aug 7, 2018, 2:34 AM • 2 Y

Y by Adventure10, Mango247

Anyone???

Z K Y

The post below has been deleted. Click to close.

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

112 posts

#4 h Aug 27, 2018, 2:23 PM • 2 Y

Y by Adventure10, Mango247

Bump for solution.

Z K Y

The post below has been deleted. Click to close.

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

375 posts

#5 h Aug 27, 2018, 2:31 PM • 2 Y

Y by Adventure10, Mango247

I never took calculus (yet) so I can't write it down algebraicly but the solution is noticing that there will be at least 1 $x$ , for which $f(x)=f(x+1)$ , atleast 1 $x$ , for which $f(x)=f(x+2)$ ... and you can notice that by moving the function by $k$ ( $k=1,2,...,2015$ ) units, as long as $k \leq 2015$ there shall be a common point

This post has been edited 1 time. Last edited by me9hanics, Aug 27, 2018, 2:31 PM

Z K Y

The post below has been deleted. Click to close.

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

112 posts

#6 h Aug 27, 2018, 2:45 PM • 2 Y

Y by Adventure10, Mango247

misinnyo wrote:

I never took calculus (yet) so I can't write it down algebraicly but the solution is noticing that there will be at least 1 $x$ , for which $f(x)=f(x+1)$ , atleast 1 $x$ , for which $f(x)=f(x+2)$ ... and you can notice that by moving the function by $k$ ( $k=1,2,...,2015$ ) units, as long as $k \leq 2015$ there shall be a common point

I don’t think you are right. If $f(0)=f(2015)=0$ , and $f(x)>0$ when $0< x\leqslant 1007$ , $f(x)<0$ when $2015>x>1007$ , then there will be no solution when $k=2014$ .

This post has been edited 1 time. Last edited by hutu683, Aug 27, 2018, 2:46 PM

Z K Y

The post below has been deleted. Click to close.

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

112 posts

#8 h Aug 27, 2018, 3:20 PM • 2 Y

Y by Adventure10, Mango247

Sorry for the previous wrong solution.(deleted)
Prove by induction on $n$ (2015).
Sketch:
First show that there is some $t\in [0, n-1]$ such that $f(t)=f(t+1)$ .
Then denote $g(x)=f(x)$ when $0\leqslant x\leqslant t$ and $g(x)=f(x+1)$ when $t\leqslant x\leqslant n-1$ , and refer to the case of $n-1$ .

Z K Y

The post below has been deleted. Click to close.

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

CyclicISLscelesTrapezoid

372 posts

CyclicISLscelesTrapezoid

#10 h Jan 20, 2023, 8:50 PM • 2 Y

Y by CeuAzul, ihatemath123

Replace $2015$ with positive integer $n$ . We do induction on $n$ , with the base case of $n=1$ obvious. The following claim lets us do induction.

Claim: There exists a real number $a$ with $0 \le a \le n-1$ such that $f(a+1)=f(a)$ .

Proof: Suppose that there doesn't exist such $a$ , and assume WLOG that $f(1)>f(0)$ . If $f(2)<f(1)$ , then consider $f(x)$ and $g(x)=f(x+1)$ . Since $f(0)<g(0)$ and $f(1)>g(1)$ , there exists $a \in (0,1)$ such that $f(a)=g(a)$ by the intermediate value theorem. Thus, we have $f(2)>f(1)$ . Similarly, we have $f(2)<f(3),\ldots,f(n-1)<f(n)$ , so $f(0)<f(1)<\cdots<f(n).$ However, $f(n)=f(0)$ , a contradiction, so such $a$ must exist. $\square$

Now, we can induct. Choose $a$ such that $f(a)=f(a+1)$ , and consider the function $f'(x)=\begin{cases}f(x) & x \le a \\ f(x+1) & x>a\end{cases}.$ This function is continuous and $f'(n-1)=f'(0)$ , so there exist at least $n-1$ pairs $(x,y)$ such that $f'(x)=f'(y)$ and $x-y$ is a positive integer. Suppose that $x'=x$ if $x \le a$ and $x'=x+1$ if $x>a$ , and define $y'$ similarly. Notice that each pair $(x,y)$ converts to a pair $(x',y')$ such that $f(x')=f(y')$ and $x'-y'$ is a positive integer, so we have $n-1$ pairs. We also have the pair $(a,a+1)$ , so there are at least $n$ pairs and we are done. $\square$

This post has been edited 2 times. Last edited by CyclicISLscelesTrapezoid, Sep 5, 2023, 9:26 PM

Z K Y

The post below has been deleted. Click to close.

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

5001 posts

#11 h Jan 20, 2023, 10:17 PM

Y by

A very similar variation of this problem was apparently a China IMO camp problem. It's possible to solve the Chinese problem by specifically utilizing the fact that $f$ in that problem is a polynomial and solutions need not lie in $[0,n]$ , but there's a totally valid solution without.

Z K Y

The post below has been deleted. Click to close.

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

156 posts

Ritwin

#12 h Oct 25, 2023, 11:17 PM • 1 Y

Y by LLL2019

Hilarious problem, I love it

Solution

Z K Y

The post below has been deleted. Click to close.

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

2533 posts

#13 h Nov 25, 2023, 6:11 AM

Y by

We will prove this using strong induction. The base case $n=1$ is vacuous so we move towards the inductive step. Suppose our claim holds for all integers $n$ from $1$ to $k-1$ .

Claim: There exists some value of $t \in [0, n-1]$ such that $p(t) = p(t+1)$ .

Proof: Assume for the sake of contradiction that there is no such $t$ . Consider the set $\{p(1)-p(0), p(2)-p(1), \dots, p(n)-p(n-1)\}$ . Evidently, none of the elements in the set can be $0$ , but the cumulative sum is $0$ . This means that at some point, the elements will change sign. Denote $f(x) = p(x)-p(x-1)$ ; $f(x)$ is continuous and changes sign at some point, so it must equal $0$ at some point by the Intermediate Value Theorem, contradiction. $\square$

Consider the function $q(x)$ such that $q(x)=p(x)$ when $x = [0,t)$ and $q(x)=p(x+1)$ when $x = [t+1,n-1]$ . From the inductive claim, we know that $q(x)$ has at least $n-1$ pairs. Simply translate the pairs back to $p(x)$ and include $(t,t+1)$ to get the desired result. $\square$

Z K Y

The post below has been deleted. Click to close.

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

147 posts

#14 h Apr 21, 2024, 9:13 PM

Y by

Let $f(x)=p(x)-p(x-1).$ Note that
$\sum_{i=1}^{i=16}f(i)=0.$ We are trying to prove that there exists an $x$ such that $f(x)=0.$ Note that if there isn't an integer $i$ that works, then
at least one of $f(i)$ will be positive and at least one will be negative. Thus, by Intermediate Value Theorem, there has to exist such an $i.$
Delete the interval $[i-1, i].$ Note that the ends of the graph are the same, so the graph is still continuous, and that all $x-y$ are either unchanged or the value is increased by $1.$ Then simply continue as before $n-1$ more times, until you can't anymore. We succesefully have found $n$ different pairs, so we're done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

3446 posts

#15 h Aug 18, 2024, 1:15 AM • 2 Y

Y by peace09, cosmicgenius

oops i overcomplicated this :stretcher:

:stretcher:

i still think this solution is pretty nice, hopefully its not a fakesolve ?

For integers $k$ with $0 \leq k \leq n-1$ , define $g_k : [0, 1) \to \mathbb R$ as $g_k (x) = f(x+k)$ . Now plot these functions all at once; each intersection point counts as one of the pairs $(x,y)$ with $x-y \in \mathbb N$ such that $f(x)=f(y)$ . We will show there are at least $n-1$ intersection points (none of the intersection points will count the pair $(x,y) = (0,n)$ , so this is the $n$ th pair).
$[asy] unitsize(0.6cm); path p = (0,0)..(1,2)..(2,3)..(3,2.5)..(4,1.5)..(5,1)..(6,2)..(7,1)..(8,0); draw(shift((12,0))*p, mediumred+linewidth(1.5)); draw(shift((10,0))*p, deepgreen+linewidth(1.5)); draw(shift((8,0))*p, royalblue+linewidth(1.5)); draw(shift((6,0))*p, orange+linewidth(1.5)); fill((0,-0.5)--(12,-0.5)--(12,4.5)--(0,4.5)--cycle, white); fill((14,-0.5)--(20.1, -0.5)--(20.1,4.5)--(14, 4.5)--cycle, white); draw((12,-0.5)--(12,4.5), black+linewidth(1.5)); draw((14,-0.5)--(14,4.5), black+linewidth(1.5)); draw(p, black+linewidth(1.5)); label("becomes", (9.5,1), fontsize(9)); label("$1$", (1,-1), fontsize(9)+mediumred); draw(brace((0.1,-0.3),(1.9,-0.3),-0.4),mediumred+linewidth(1.5)); label("$2$", (3,-1), fontsize(9)+deepgreen); draw(brace((2.1,-0.3),(3.9,-0.3),-0.4),deepgreen+linewidth(1.5)); label("$3$", (5,-1), fontsize(9)+royalblue); draw(brace((4.1,-0.3),(5.9,-0.3),-0.4),royalblue+linewidth(1.5)); label("$4$", (7,-1), fontsize(9)+orange); draw(brace((6.1,-0.3),(7.9,-0.3),-0.4),orange+linewidth(1.5)); [/asy]$
If any $i$ and $j$ exist for which $g_i (0) = g_j (0)$ , we can nudge $f$ by a negligible amount at certain points so that this is no longer the case – evidently, this only decreases the number of intersection points. Note that, now, $g_0 (0), g_1 (0), \dots, g_{n-1} (0)$ is a permutation of $g_0 (1), g_1 (1), \dots, g_{n-1} (1)$ . (Well, $g_i(1)$ is not defined, but we can take the limiting value.) Each inversion in this permutation corresponds to an intersection point, so it suffices to prove the following lemma:

Claim: A permutation of $1, 2, \dots, n$ with one component has at least $n-1$ inversions.
Proof: Call an element of the permutation a "gamechanger" if it is greater than all the elements to its left. Let the gamechangers be $y_1 < y_2 < \cdots < y_k$ , and let their indices be $x_1 < x_2 < \cdots < x_k$ . Clearly, we have $x_{i+1} < y_{i}$ for all $i$ – in particular, $y_1 > 1$ . As such, each gamechanger $y_i$ comes before $y_{i-1}+1, y_{i-2}+1, \dots, y_i-1$ . If $i > 1$ , this gamechanger also comes before some number from $1$ to $y_{i-1} - 1$ since there are only $x_i - 1 < y_{i-1} - 1$ numbers before the gamechanger in the permutation.

Altogether: the first gamechanger is the larger element of $y_1-1$ inversions while for $i > 1$ , the gamechanger $y_i$ is the larger element of at least $y_i - y_{i-1}$ elements. Since the largest game changer is $n$ , we have a total of at least $n-1$ inversions.

This post has been edited 3 times. Last edited by ihatemath123, Aug 18, 2024, 1:35 AM

Z K Y

The post below has been deleted. Click to close.

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

CyclicISLscelesTrapezoid

372 posts

CyclicISLscelesTrapezoid

#16 h Sep 16, 2024, 1:27 AM

Y by

We solve the following problem (half of the solution is copied from my previous post in this thread):

Generalization of China TST Quiz 2001/1/1 wrote:

Let $a$ be a positive real number, and let $f \colon [0,a] \to \mathbb{R}$ be a continuous function with $f(0)=f(a)$ . Find the minimum possible number of pairs of real numbers $(x,y)$ such that $f(x)=f(y)$ and $x-y$ is a positive integer.

The answer is $a$ if $a$ is an integer and $0$ otherwise.

If $a$ is an integer, then $f(x)=\tfrac{a}{2}-|x-\tfrac{a}{2}|$ works: for a positive integer $n \le a$ , the only pair $(x,y)$ such that $f(x)=f(y)$ and $x-y=n$ is $(\tfrac{a+n}{2},\tfrac{a-n}{2})$ , so there are $a$ pairs. If $a$ is not an integer, then construct $f$ by shifting a function with period $1$ by a nonconstant linear function:
$f(x)=\cos(2\pi x)-1+\frac{1-\cos(2\pi a)}{a}x.$ Notice that $f(0)=f(a)=0$ . For a positive integer $n$ , we have $f(x+n)-f(x)=\tfrac{1-\cos(2\pi a)}{a}n>0$ , so there are $0$ pairs.

It remains to prove that there are at least $a$ pairs if $a$ is an integer.

Claim: There exists a real number $b$ with $0 \le b \le a-1$ such that $f(b+1)=f(b)$ .

Proof: Assume WLOG that $f(1) \ge f(0)$ , and let $g(x)=f(x+1)$ . Since $f(0)=f(a)$ , there exists $n \in \{1,2,\ldots,a-1\}$ such that $f(n-1) \le f(n)$ and $f(n) \ge f(n+1)$ . This means $f(n-1) \le g(n-1)$ and $f(n) \ge g(n)$ , so there exists $b \in [n-1,n]$ such that $f(x)=g(x)$ by the intermediate value theorem, as desired. $\square$

Now, we induct on $a$ . For the base case, the pair $(1,0)$ works for $a=1$ . For the inductive step, choose $b$ such that $f(b)=f(b+1)$ , and consider the function
$f_1(x)=\begin{cases} f(x) & x \le b \\ f(x+1) & x>b \end{cases}.$ This function is continuous and $f_1(a-1)=f_1(0)$ , so there exist at least $a-1$ pairs $(x,y)$ such that $f_1(x)=f_1(y)$ and $x-y$ is a positive integer. Suppose that $x'=x$ if $x \le b$ and $x'=x+1$ if $x>b$ , and define $y'$ similarly. Notice that each pair $(x,y)$ converts to a pair $(x',y')$ such that $f(x')=f(y')$ and $x'-y'$ is a positive integer, so we have $a-1$ pairs by the inductive hypothesis. We also have the pair $(b,b+1)$ , so there are at least $a$ pairs and we are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

112 posts

#17 h Oct 12, 2024, 12:32 PM

Y by

Wow what a problem, i loved it

I prove the desired result with strond induction, while replacing 2015 with $n$

Claim: There is some value $t \in [0, n-1]$ such that $p(t+1)=p(t)$

Proof: Assume FTSOC that there is no such value. Upon considering the set $\{p(1)-p(0), p(2)-p(1), \cdots, p(n)-p(n-1)\}$ , we get that none of the elements of the set can be zero, but by the condition the total sum is 0, and hence some time in the list it switches signs. But if we consider the function $q(x)=p(x+1)-p(x)$ , we get a contradiction by the intermediate value theorem.

Now by the claim we take a value $r$ such that $f(r+1)=f(r)$ and remove it from the interval $[0,n]$ , and consider the two remaining intervals together which finishes by strong induction

Z K Y

The post below has been deleted. Click to close.

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

112 posts

#18 h Oct 13, 2024, 11:37 AM

Y by

Oopsies one small error in mine, we musnt use strong inductionand instead shift the part of $f$ above $r+1$ down and induct, and then all the pairs will be preserved and then we shift back to get the extra pair $(r,r+1)$ , which solves the problem, noting that the shifting preserves continuity as $f(r+1)=f(r)$

Z K Y

The post below has been deleted. Click to close.

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

391 posts

#19 h Jan 4, 2025, 3:43 AM

Y by

We prove this works for any $n,$ by induction. First, if $n=1$ then $p(0)=p(1)$ so we are done. Suppose this holds until some $n=i.$ For $i+1,$ Let $q(x)=p(x+1),$ and let $r(x)=p(x+1)-p(x).$ If $r(x)$ is always zero then we are done. If not, observe $\int_{0}^{i} r(x)=0,$ so if $r$ is positive at some point, it must also be negative at some point. By the IVT, there must be some point $t$ where $r(t)$ is $0.$ Suppose this point is $t.$ Then $p(t)=p(t+1).$ Now consider
$s(x)= \begin{cases} p(x) & x \in (-\infty,t] \\ p(x+1) & x \in (t, +\infty) \end{cases}$ this function is clearly continuous as $p(x)$ is continuous and $p(t)=p(t+1).$ Then $s(0)=p(0)=p(n)=s(n-1)$ so there are $i$ such pairs in function $s.$ If they exist in function $s,$ they must exist in function $p$ too. Therefore adding the extra $(t+1,t)$ pair yields a total of $i+1$ pairs, and we are done by induction.

Z K Y

The post below has been deleted. Click to close.

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

611 posts

#20 h Apr 12, 2025, 3:02 AM

Y by

We show this for any continuous function $g$ . We can induct. If $n = 1,$ this fact is obviously true.

Now, let $k\in\{0, \dots, n - 1\}$ denote the integer such that $f(k) > f(k - 1), f(x) > f(k + 1)$ or the inequalities are swapped. By extremal value theorem, this must exist. By IVT, there exists $t\in[0, j]$ such that $f(t) = f(t + 1).$

Define $\overline{g}\colon[0, n - 1]\to\mathbb R$ to be a continuous function such that $\overline{g}(x) = \begin{cases*} g(x) & x < t \\ g(x - 1) & g > t \end{cases*}$ This is obviously continuous. By inductive hypothesis, this also finishes.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a