Polish MO finals, problem 2

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

Polish MO finals, problem 2

G H J

Reveal topic tags

algebra proposed

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.

19 posts

michaj

#1 h Apr 10, 2008, 6:35 PM • 2 Y

Y by Adventure10, Mango247

A function $f: R^3\rightarrow R$ for all reals $a,b,c,d,e$ satisfies a condition:

$f(a,b,c)+f(b,c,d)+f(c,d,e)+f(d,e,a)+f(e,a,b)=a+b+c+d+e$

Show that for all reals $x_1,x_2,\ldots,x_n$ ( $n\geq 5$ ) equality holds:

$f(x_1,x_2,x_3)+f(x_2,x_3,x_4)+\ldots +f(x_{n-1},x_n,x_1)+f(x_n,x_1,x_2)=x_1+x_2+\ldots+x_n$

Z K Y

The post below has been deleted. Click to close.

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

5850 posts

#2 h Apr 10, 2008, 10:16 PM • 1 Y

Y by Adventure10

For a given $n$ , add the equations for $(a,b,c,d,e) = (x_1, x_2, x_3, x_4, x_5)$ , $(a,b,c,d,e) = (x_1, x_2, x_3, x_4, x_6)$ , $\ldots$ , $(a,b,c,d,e) = (x_{n - 1}, x_n, x_1, x_2, x_3)$ , $(a,b,c,d,e) = (x_n, x_1, x_2, x_3, x_4)$ . Divide both sides by $5$ to get the desired equality.

Seems a bit easy.

EDIT: Yeah, you're right, I misread the problem. I'll rethink this and maybe post another reply.

This post has been edited 1 time. Last edited by MellowMelon, Apr 11, 2008, 1:23 AM

Z K Y

The post below has been deleted. Click to close.

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

66 posts

limsk1

#3 h Apr 11, 2008, 1:05 AM • 1 Y

Y by Adventure10

how to get rid of $f(x_4, x_5, x_1)$ that appear in the equation for $(a,b,c,d,e)=(x_1,x_2,x_3,x_4,x_5)$ ?

i think you misunderstood the problem

Z K Y

The post below has been deleted. Click to close.

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

1 post

#4 h Apr 21, 2008, 7:08 PM • 2 Y

Y by Adventure10, Mango247

f(0,0,0) + f(0,0,0) + f(0,0,0) + f(0,0,0) + f(0,0,0) = 0 + 0 + 0 + 0 + 0 <=>
f(0,0,0) = 0

f(a,0,0) + f(0,0,0) + f(0,0,0) + f(0,0,0) + f(0,0,0) = a + 0 + 0 + 0 + 0 <=>
f(a,0,0) = a

f(a,b,0) + f(b,0,0) + f(0,0,0) + f(0,0,0) + f(0,0,0) = a + b + 0 + 0 + 0 <=>
f(a,b,0) = a

f(a,b,c) + f(b,c,0) + f(c,0,0) + f(0,0,0) + f(0,0,0) = a + b + c + 0 + 0 <=>
f(a,b,c) = a

And then:

f(x1,x2,x3) + f(x2,x3,x4) + ... + f(xn,x1,x2) = x1 + x2 + ... + xn

Z K Y

The post below has been deleted. Click to close.

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

239 posts

#5 h Apr 22, 2008, 11:29 AM • 1 Y

Y by Adventure10

Dark Wind wrote:

f(0,0,0) + f(0,0,0) + f(0,0,0) + f(0,0,0) + f(0,0,0) = 0 + 0 + 0 + 0 + 0 <=>
f(0,0,0) = 0

f(a,0,0) + f(0,0,0) + f(0,0,0) + f(0,0,0) + f(0,0,0) = a + 0 + 0 + 0 + 0 <=>
f(a,0,0) = a

f(a,b,0) + f(b,0,0) + f(0,0,0) + f(0,0,0) + f(0,0,0) = a + b + 0 + 0 + 0 <=>
f(a,b,0) = a

f(a,b,c) + f(b,c,0) + f(c,0,0) + f(0,0,0) + f(0,0,0) = a + b + c + 0 + 0 <=>
f(a,b,c) = a

And then:

f(x1,x2,x3) + f(x2,x3,x4) + ... + f(xn,x1,x2) = x1 + x2 + ... + xn

Wrong , because the function $f(a,b,c)=\frac{a+b+c}{3}$ satisfies in this problem

Z K Y

The post below has been deleted. Click to close.

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

12167 posts

#6 h Apr 23, 2008, 3:45 AM • 2 Y

Y by Adventure10, Mango247

It would suffice inductively if we could prove the identity

$f(x_{n - 2}, x_{n - 1}, x_n) + f(x_{n - 1}, x_n, x_1) + f(x_n, x_1, x_2) - f(x_{n - 2}, x_{n - 1}, x_1) - f(x_{n - 1}, x_1, x_2) = x_n$ .

In other words, letting $x_{n - 2} = a, x_{n - 1} = b, x_n = c, x_1 = d, x_2 = e$ ,

$f(a, b, c) + f(b, c, d) + f(c, d, e) = c + f(a, b, d) + f(b, d, e)$ .

Substituting the original condition gives

$a + b + d + e = f(d, e, a) + f(e, a, b) + f(a, b, d) + f(b, d, e)$ ,

so it suffices to prove the desired statement for $n = 4$ to prove it for all $n$ . I'll keep working.

Z K Y

The post below has been deleted. Click to close.

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

2 posts

#7 h Apr 23, 2008, 6:35 PM • 2 Y

Y by Adventure10, Mango247

For $n>5$ sum up all five term subsums of $f(x_1,x_2,x_3) ... f(x_n,x_1,x_2)$ .
Getting $n(f(x_1,x_2,x_3)+ ... +f(x_n,x_1,x_2)) = n(x_1+x_2+...x_n)$ .

Z K Y

The post below has been deleted. Click to close.

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

5850 posts

#8 h Apr 24, 2008, 12:59 PM • 5 Y

Y by Adventure10, Mango247, and 3 other users

Okay, I think I got this, finally.

Solution

Z K Y

The post below has been deleted. Click to close.

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

1179 posts

#9 h Jan 6, 2019, 5:35 AM • 1 Y

Y by Adventure10

Definition of cancer.

We claim that the result holds for $n=4$ . Plugging in $(a,a,a,a,a)$ gives $f(a,a,a)=a$ . Taking $(a,a,b,a,a)$ and invoking $f(a,a,a)=a$ gives
$\begin{align} f(a,a,b)+f(a,b,a)+f(b,a,a)=2a+b \end{align}$ Using $(1)$ , the pair $(b,a,a,b,a)$ gives
$\begin{align*} 2b+3a=[f(b,a,a)+f(a,a,b)+f(a,b,a)]+f(a,b,a)+f(b,a,b)=2a+b+f(a,b,a)+f(b,a,b), \end{align*}$ or $\begin{align*}\tag{2} f(a,b,a)+f(b,a,b)=a+b.\end{align*}$ Applying the pair $(d,a,b,a,b)$ and using $(2)$ admits $2a+2b+d=f(d,a,b)+[f(a,b,a)+f(b,a,b)] + f(a,b,d)+f(b,d,a)=a+b+f(d,a,b)+f(a,b,d)+f(b,d,a),$ which implies $f(d,a,b)+f(a,b,d)+f(b,d,a)=a+b+d$ , i.e. the result holds for $n=3$ .

Lemma: $f(d,a,a)+f(a,a,b)=a+f(d,a,b)$ .
Proof: Let us add $f(a,a,d)+f(a,d,a)+f(b,a,a)+f(a,b,a)$ to both sides. Grouping the LHS and using the result for $n=3$ , $[f(d,a,a)+f(a,a,d)+f(a,d,a)]+[f(a,a,b)+f(b,a,a)+f(a,b,a)]=4a+b+d,$ Simplifying the RHS using the pair $(d,a,b,a,a)$ along with the problem condition, $a+f(d,a,b)+f(a,b,a)+f(b,a,a)+f(a,a,d)+f(a,d,a)=4a+b+d$ as well. Since all our steps are reversible the lemma is established. $\square$

Plugging in the pair $(a,b,c,d,a)$ , we obtain $2a+b+c+d=f(a,b,c)+f(b,c,d)+f(c,d,a)+f(d,a,a)+f(a,a,b).$ Using the lemma, $a+b+c+d=f(a,b,c)+f(b,c,d)+f(c,d,a)+f(d,a,b)$ , which means the result holds for $n=4$ .

Now we shall prove the statement via induction on $n$ . The base case for $n=5$ is already done. Assume that $f(x_1, x_2, x_3) + f(x_2, x_3, x_4) + \cdots + f(x_{n-2},x_{n-1},x_n)+f(x_{n-1}, x_n, x_1) + f(x_n, x_1, x_2) = x_1 + x_2 + \cdots + x_n$ is valid. We wish to show $f(x_1, x_2, x_3) + f(x_2, x_3, x_4) + \cdots + f(x_{n-2},x_{n-1},x_n)+f(x_{n-1}, x_n, x_{n+1}) + f(x_n, x_{n+1}, x_1)+f(x_{n+1},x_1,x_2) = x_1 + x_2 + \cdots + x_{n+1}$ Note $f(x_1, x_2, x_3) + f(x_2, x_3, x_4) + \cdots + f(x_{n-2},x_{n-1},x_n)=x_1+x_2+\cdots+x_n-f(x_{n-1}, x_n, x_1)- f(x_n, x_1, x_2)$ , so it suffices to prove $f(x_{n-1}, x_n, x_{n+1}) + f(x_n, x_{n+1}, x_1)+f(x_{n+1},x_1,x_2)=x_{n+1}+f(x_{n-1}, x_n, x_1)+ f(x_n, x_1, x_2)$ Adding $f(x_1,x_2,x_{n-1})+f(x_2,x_{n-1},x_n)$ to both sides and using the given relation, we must show $x_{n-1}+x_n+x_{n+1}+x_1+x_2=x_{n+1}+f(x_{n-1}, x_n, x_1)+ f(x_n, x_1, x_2)+f(x_1,x_2,x_{n-1})+f(x_2,x_{n-1},x_n),$ which easily follows from the fact the relation holds for $n=4$ . All of our steps were reversible so the original equation must have been true.

Z K Y

The post below has been deleted. Click to close.

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

578 posts

#10 h Sep 12, 2019, 1:40 AM • 1 Y

Y by Adventure10

I think that this problem is not that terrible, as it can be reasonably solved in half an hour if we work backwards from the inductive hypothesis. In other words, the inductive step reduces to an equality in five variables, and so we can use the given condition to continually reach equivalent statements with less variables until we can eventually just prove them.

We will use $abc$ as shorthand for $f(a, b, c)$ . We will use $P(a, b, c, d, e)$ to denote the assertion in the problem.

Lemma 1. $ccc = c$ for any $c \in \mathbb{R}$ .

Proof. Trivial by $P(c, c, c, c, c).$

$\blacksquare$

Lemma 2. $cec + ece = e+c$ for any $e, c \in \mathbb{R}$ .

Proof. By $P(e, e, c, c, c)$ and Lemma $1$ we obtain:

$(cce + cee + eec + ecc) = 2e + 2c.$
By $P(e, c, c, c, c) + P(c, e, e, e, e)$ and Lemma $1$ we obtain:

$(cce + cee + eec + ecc) + cec + ece = 3e + 3c.$
Subtracting the above two equations finishes.

$\blacksquare$

Lemma 3. $bce + c = bcc + cce$ for any $b, c, e \in \mathbb{R}.$

Proof. By $P(b, c, e, c, e) - P(b, c, c, c, e)$ we know that:

$bcc + ccc + cce - c = bce + (cec + ece) - e.$
By Lemmas $1, 2$ , we get:

$bcc + c + cce - c = bce + (e + c) - e \Rightarrow bcc + cce = bce + c,$
as desired.

$\blacksquare$

Lemma 4. $bce + cef + efb + fbc = b+c+e+f$ for any $b, c, e, f \in \mathbb{R}.$

Proof. By $P(c, e, f, b, c)$ we know:

$cef + efb + fbc = c+e+f+b+c - (bcc + cce).$
By Lemma $3$ , we can rewrite the RHS as:

$c+e+f+b+c - (bce + c) = c+e+f+b - bce,$
and so therefore we have

$cef + efb + fbc = c+e+f+b - bce \Leftrightarrow bce + cef + efb + fbc = c+e+f+b,$
as desired.

$\blacksquare$

Lemma 5. For any $b, c, e, f \in \mathbb{R}$ , function $g: \mathbb{R} \rightarrow \mathbb{R}$ given by $g(x) = bcx + cxe + xef - bce - cef$ for each $x \in \mathbb{R}$ is identical to the identity function (i.e. $g(x) \equiv x$ ).

Proof. First of all, we know from $P(b, c, x, e, f) - P(b, c, 0, e, f)$ that:

$g(x) - g(0) = x.$
Therefore, it suffices only to show that $g(0) = 0$ , i.e. that:

$bc0 + c0e + 0ef = bce + cef.$
From $P(b, c, 0, e, f)$ and Lemma $4$ we have:

$bc0 + c0e + 0ef = b+c+e+f - efb - fbc = bce + cef,$
as desired.

$\blacksquare$

We are now ready to solve the problem. We will prove it by induction on $n.$ If $n = 5$ , we are done by the condition of the problem. Suppose that it holds when $n = k$ , for some $k \ge 5.$ When $n = k +1$ , we know from Lemma $5$ that $f(x_1, x_2, x_3) + f(x_2, x_3, x_4) + f(x_3, x_4, x_5) - f(x_1, x_2, x_4) - f(x_2, x_4, x_5) = x_3.$ Therefore, adding this to the equality obtained when we apply the inductive hypothesis on $(x_1, x_2, x_4, x_5, x_6, \cdots, x_{k+1})$ , the induction is complete.

$\square$

Z K Y

The post below has been deleted. Click to close.

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

141 posts

#11 h Nov 15, 2022, 9:52 PM

Y by

The error in this solution is that the problem was not interpreted correctly, here for example

Dark Wind wrote:

f(a,0,0) + f(0,0,0) + f(0,0,0) + f(0,0,0) + f(0,0,0) = a + 0 + 0 + 0 + 0 <=>
f(a,0,0) = a

the correct equality (assuming $(a,b,c,d,e)=(a,0,0,0,0)$ ) would be $f(a,0,0)+f(0,0,0)+f(0,0,0)+f(0,0,a)+f(0,a,0)=a+0+0+0+0=a$

This post has been edited 1 time. Last edited by TheKagas, Nov 15, 2022, 11:31 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a