Combinatorics problem

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

Combinatorics problem

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Azerbaijan IMO TST 2020

The post below has been deleted. Click to close.

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

378 posts

EmilXM

#1 h Sep 29, 2020, 8:45 AM

Y by

A finite number of stones are good when the weight of each of these stones is less than the total weight of the rest. It is known that arbitrary $n-1$ of the given $n$ stones is good. Prove that it is possible to choose a good triple from these stones.

Z K Y

The post below has been deleted. Click to close.

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

678 posts

#2 h Sep 29, 2020, 9:31 AM

Y by

All TST problems are from ISL2019 , so don't post them

Z K Y

The post below has been deleted. Click to close.

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

378 posts

EmilXM

#3 h Sep 29, 2020, 9:34 AM

Y by

Kamran011 wrote:

All TST problems are from ISL2019 , so don't post them

This problem is not in ISL2019. That is why I posted it

Z K Y

The post below has been deleted. Click to close.

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

4872 posts

#5 h Sep 29, 2020, 10:28 AM

Y by

Let $a_1 \leq a_2 \leq... \leq a_n$ are weights.
From condition follows $a_1+...+a_{n-2}>a_n$
Let $s_i=a_1+...+a_i$

Let there are not good triples. Then $a_i>a_{i-1}+a_{i-2}, 3 \leq i \leq n$
$s_{n-2}>a_n>a_{n-1}+a_{n-2} \to s_{n-3}>a_{n-1}>a_{n-2}+a_{n-3} \to s_{n-4}>a_{n-2} \to ... \to s_2>a_4 \to a_1+a_2>a_3 \to$ contradiction

Z K Y

The post below has been deleted. Click to close.

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

661 posts

#6 h Aug 9, 2023, 10:50 AM • 1 Y

Y by erkosfobiladol

Similar solution.
Let $a_1 \leq a_2 \leq ... \leq a_n$ and $S=a_1+a_2+...+a_n$
$a_1,...,a_{n-2},a_n$ is good so we have $a_n<a_1+a_2+...+a_{n-2}=S-a_n-a_{n-1}$
$\implies \boxed{2a_n+a_{n-1}<S}$
Assume that there is no good triplet.
$x\leq y\leq z \implies a_x<a_y+a_z$ and $a_y<a_x+a_z$ so $a_z \geq a_x+a_y.$
We have
$a_n \geq a_{n-1}+a_{n-2}$
$a_{n-1} \geq a_{n-2}+a_{n-3}$
$...$
$a_3 \geq a_{2}+a_{1}$
By adding these inequalities we get $a_n \geq (a_{n-2}+a_{n-3}+...+a_1)+a_2=S-a_n-a_{n-1}+a_2$
$\implies 2a_n+a_{n-1} \geq S+a_2$
$\implies S>2a_n+a_{n-1} \geq S+a_2$ Contradiction

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a