sets where each element does not divides other's sum

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 where each element does not divides other's sum

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: JBMO 2011 Shortlist C5

The post below has been deleted. Click to close.

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

30627 posts

#1 h Oct 14, 2017, 6:40 AM • 2 Y

Y by centslordm, Adventure10

A set $S$ of natural numbers is called good, if for each element $x \in S, x$ does not divide the sum of the remaining numbers in $S$ . Find the maximal possible number of elements of a good set which is a subset of the set $A = \{1,2, 3, ...,63\}$ .

Z K Y

The post below has been deleted. Click to close.

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

4071 posts

#2 h Oct 14, 2017, 10:59 AM • 4 Y

Y by me9hanics, centslordm, Adventure10, Mango247

Denote the sum of all elements of set $S$ by $s(S)$ .
Note that set $S$ is called good if and only if $x\nmid s(S)-x\Leftrightarrow x\nmid s(S)$ for all $x\in S$ .
It’s clear that $1\not\in S$ .
Also $\{ 2,3,...,63\}$ is not a good set. Hence the maximum possible number of elements of a good set $S$ is at most $61$ .
Note that $\{ 1,2,...,63\} -\{ 1,4\}$ is a good set, done.

Z K Y

The post below has been deleted. Click to close.

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

131 posts

#3 h Jun 2, 2021, 12:24 PM • 3 Y

Y by centslordm, Mango247, Mango247

Sorry, but dont we have to prove that $\{ 1,2,...,63\} -\{ 1,4\}$ is a good set??? Because if not, then it would be a really easy exarcise since the rest are simple.

Z K Y

The post below has been deleted. Click to close.

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

1481 posts

CT17

#4 h Jun 2, 2021, 12:26 PM • 1 Y

Y by centslordm

sttsmet wrote:

Sorry, but dont we have to prove that $\{ 1,2,...,63\} -\{ 1,4\}$ is a good set??? Because if not, then it would be a really easy exarcise since the rest are simple.

It's good because its sum, $2011$ , is prime.

Z K Y

The post below has been deleted. Click to close.

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

131 posts

#5 h Jun 7, 2021, 5:57 PM

Y by

CT17 wrote:

sttsmet wrote:

Sorry, but dont we have to prove that $\{ 1,2,...,63\} -\{ 1,4\}$ is a good set??? Because if not, then it would be a really easy exarcise since the rest are simple.

It's good because its sum, $2011$ , is prime.

Oh I understood now! Amazing solution.

This post has been edited 1 time. Last edited by sttsmet, Feb 20, 2022, 10:24 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a