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 ?

Please help !!!

  • 1
    $\begingroup$ 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$ $\endgroup$ – Hagen von Eitzen Dec 12 '17 at 7:22
  • $\begingroup$ @HagenvonEitzen your comment is very reasonable, but I think maximum eliminations will favour the condition, also can you provide generalisation or alternative $\endgroup$ – 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.

  • 1
    $\begingroup$ 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 $\endgroup$ – Hagen von Eitzen Dec 12 '17 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.