A set S of natural numbers is called good, if for each element x∈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∤ 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.