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\}$.
Problem
Source: JBMO 2011 Shortlist C5
Tags: JBMO, combinatorics, Sets
14.10.2017 13:59
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.
02.06.2021 15:24
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.
02.06.2021 15:26
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.
07.06.2021 20:57
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.