# Generalisation of a problem

I have a question which is

From a set of natural numbers ${1,2,3,...,100}$ , we have to choose a set of cardinality $k$ such that any two elements of that set do neither give thier sum nor their product divisible by $100$ .Find maximum value of $k$.

I encountered this problem as follows

Let we choose all $100$ numbers. Then we have some eliminations to satisfy the requirements.

First , we eliminate the numbers $51,52,53,...,100$ because they can give sum with other numbers which is divisible by $100$

Then we have to eliminate one of the numbers each from $(2,50),(4,25),(10,30),(10,40),(20,5)$ because their product is divisible by $100$

Total number of eliminations are $55$. Therefore maximum value of $k$ is $45$. And of course, this is correct.

Now it seems that this problem could be generalized

Suppose we have ${1,2,3,...,n}$ number. Then $n/2$ will get eliminated. Now from left numbers, we have to deal with the pairs which can give their product divisible by $n$.

This could be related to prime factorisation of $n$. Even though I couldn't find any generalisation.

Now I have two questions

$1.$ Is there any other elegant way to do this problem?

$2.$ Can we generalise this problem? If yes , then what should I do next ?

• Your approach does not seem to work as is. For example, if we eliminate $2$ from $(2,50)$ and $30$ from $(10,30)$, we still have $50\cdot 10$ as multiple of $100$. Also, removing only $10$ will satisfy both $(10,30)$ and $(10,40)$. Not to mention that "because they can give sum with other numbers" would equally apply to $1,2,\ldots,49$ (whereas it does not apply to $100$ – Hagen von Eitzen Dec 12 '17 at 7:22
• @HagenvonEitzen your comment is very reasonable, but I think maximum eliminations will favour the condition, also can you provide generalisation or alternative – Atul Mishra Dec 12 '17 at 7:43

For each $d\mid n$ let $A_d=\{\,x\mid 1\le x\le n, \gcd(n,x)=d\,\}$. Then the product condition reads:

If $n\mid dd'$ and we pick at least one element of $A_d$, then we must not pick any element of $A_{d'}$. (In the special case $d=d'$ we may pick at most one element from $A_d$)

In particular, we better avoid $A_n$.

As $x\in A_d$ implies $n-x\in A_d$ (except when $x=d=n$), the additive condition implies

We can pick at most half of the elements of $A_d$ (with the exception that we can pick $\frac{|A_d|+1}2$ elements if $|A_d|$ is odd.

Now the problem is less which numbers we pick, but rather from which classes (here concretely: $A_1,A_2,A_4,A_5,A_{10},A_{20},A_{25},A_{50}$ with $40, 20, 20, 8, 4, 4, 2,1$ elements, respectively) we pick (any) half. A greedy approach along the product condition seems to work:

• Pick $20$ of the elements of $A_1$; this spoils nothing (except that we must not pick from $A_{100}=\{100\}$)
• Pick $10$ of the elements of $A_2$; this spoils picking one element from $A_{50}$
• Pick $10$ elements of $A_4$; this spoils picking one element from $A_{25}$
• Pick $4$ elements of $A_5$; this spoils picking two element from $A_{20}$
• We can pick only one element from $A_{10}$

In total, that's 45 elements.

For general $n>2$, the number achieved by this strategy is

$$\frac12\sum_{d\mid n\atop d^2<n}\phi(n/d)+\begin{cases}1&\text{if }n\text{ is a perfect square}\\0&\text{otherwise}\end{cases}$$ (note that $\phi(n/d)$ will always be even because $n/d>2$), and it seems that this will always be the maximum.

• Actually, I am no longer confident that the above gives the max. I think the method makes wrong choices if $n=2^4\cdot 17$, say. Then again, I am also not sure if summing $\max\{\phi(d),\phi(n/d)\}$ would always work – Hagen von Eitzen Dec 12 '17 at 18:30