Sets With a Given Property

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

Sets With a Given Property

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Romania TST 2025 Day 1 P4

The post below has been deleted. Click to close.

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

1746 posts

oVlad

#1 h Apr 9, 2025, 2:32 PM • 2 Y

Y by nbasrl, cubres

Determine the sets $S{}$ of positive integers satisfying the following two conditions:

For any positive integers $a, b, c{}$ , if $ab + bc + ca{}$ is in $S$ , then so are $a + b + c{}$ and $abc$ ; and
The set $S{}$ contains an integer $N \geqslant 160$ such that $N-2$ is not divisible by $4$ .

Bogdan Blaga, United Kingdom

Z K Y

The post below has been deleted. Click to close.

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

internationalnick123456

135 posts

internationalnick123456

#2 h Apr 9, 2025, 3:48 PM • 1 Y

Y by bin_sherlo

Claim 1. $S$ contains least one element that is divisible by $4$ and at least $40$ .
Proof. If $4\mid N$ , then the statement is trivial.
Now, consider $N=2m+1$ with $m\geq 80$ . Since $N = m\cdot 1 + m\cdot1 + 1\cdot1$ , we must have $m$ and $m+2$ both in $S$ . If $m$ is even, then either $m$ or $m+2$ are divisible by $4$ and at least $80$ , satisfying the condition. Otherwise, both of them are odd, and one of them must be congruent to $1$ modulo $4$ . In that case, we again find an element in $S$ that is divisible by $4$ and at least $40$ .
Claim 2. If $n\in S$ and $4\mid n$ , then $n-4\in S$ .
Proof. Let $n=4a = (a-1)\cdot 2+(a-1)\cdot 2 + 2\cdot 2$ . Then $4(a-1)\in S$ , which implies $n-4\in S$ .
Claim 3. $4\mathbb N\subset S$ .
Proof. By Claim 1 and Claim 2 we get $40\in S$ . Now, suppose $8a\in S$ for some $a\geq 3$ . Then $(a-2)\cdot 4 + (a-2)\cdot 4 + 4\cdot 4\in S\Rightarrow 16(a-2)\in S$ . Since $8\cdot 5\in S$ , we can repeat this process indefinitely to generate larger and larger multiples of 8 in $S$ . This implies that $S$ contains arbitrarily large multiples of $4$ . Hence, by Claim 2, the desired result follows.
Claim 4. $S=\mathbb N$ .
Proof. By Claim 3, we have $2\cdot (a - 1) + 2\cdot (a-1) + 2\cdot 2\in S$ for any $a>1$
$\Rightarrow a+3 = a-1 + 2 + 2\in S,\forall a>1$ . Hence, $\mathbb N\cap [4,+\infty)\subset S$ .
We easily derive $S=\mathbb N$ . (qed)

Z K Y

The post below has been deleted. Click to close.

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

306 posts

nbasrl

#3 h Apr 9, 2025, 8:22 PM • 2 Y

Y by internationalnick123456, RaduAndreiLecoiu

The above is pretty much the official solution and the one I had submitted. Probably the best problem I've composed, though beauty is in the eye of the beholder isn't it? Still, I hope people in the contest enjoyed working on it.

I have a few remarks if anyone is interested. First, the origin of the problem is twofold:

For a long time I've had an idea for a problem along the following lines: if $E\in S$ then $F,G \in S$ where $F$ is "generally smaller" than $E$ and $G$ is "generally larger" than $E$ , so that you can go smaller and larger and possibly cover all of the domain.
I was looking at which positive integers can be written as a sum $ab+bc+ca$ , for some $a,b,c$ . More on this below.

This problem then eventually came out of these. Regarding the first point, the initial version of the problem had $ab+bc+ac\in S$ impliying $a,b,c,abc\in S$ instead of $a+b+c$ and $abc$ . The same steps apply in that case if $N$ is divisible by $4$ , however I haven't managed to prove it in general for all odd $N$ . If anyone has a solution for this modified version, I'd be interested to see it!

A couple more remarks:

The conclusion is still valid if $N<160$ except for $N\leq 37$ and $N\in \{41,43,49\}$ (as verified by a computer search) but I don't think a clean general argument can be made.
The condition $N\not\equiv 2\pmod{4}$ is crucial here and here's why a general argument for that case couldn't exist. Going back to the second point above, it can be proven that any number $N\geq 1$ can be written as a sum $N=ab+bc+ca$ except for at most $19$ numbers. These are: $1,2,6,10,22,30,42,58,70,78,102, 130, 190, 210, 330, 462$ . Note that all of them (except $1$ ) are $2$ mod $4$ . Now here's the most interesting part: there are $18$ numbers on that list and it's not known if the 19th exists. If the Generalized Riemann Hypothesis is true, then there is no 19th number. See here for more details.

Z K Y

The post below has been deleted. Click to close.

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

375 posts

#4 h Apr 13, 2025, 1:31 AM

Y by

So why is this problem proposed by someone from UK,not Romania?

Z K Y

The post below has been deleted. Click to close.

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

1746 posts

oVlad

#5 h Apr 13, 2025, 8:21 PM • 1 Y

Y by aidan0626

flower417477 wrote:

So why is this problem proposed by someone from UK,not Romania?

Rest assured, the author is a romanian person. But even if they weren't, what's the issue?

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a