Let $ \phi $ be Euler's totient function. There is set of natural numbers $ |A| = n $. We know that there are at least 3 different two-element subsets A having this same sum (mod 50). What is the lowest possible n?

I have answers to choose for this

A) $ \phi(27) $

B) $17$

C) $15$

D) $\phi(21) + 3 $

I know how is modular arithmetic working nad how to find $ \phi(n) $ but I don't know why the correct answer here is C and D.

So we have set A containing 15 elements. Numbers with the same sum of $ (mod50) $ can be for example:

$ 50+100(mod 50) = 100+150(mod50) = 200+250 (mod50) = 300+350(mod50)$

So for this numbers my set A looks $A = {50,100,150,200,250,300,350} $

And we can have here 2-elements subsets like:

$\{50,100\} , \{150,200\}, \{250,300\}...$

I don't know that i am thinking about it correctly. So if there would be additional answer like

E) $10$

So E answer would be correct?

  • 1
    $\begingroup$ You are correct, in fact all you need is $3$ or $4$ elements that satisfy the sum condition and the three subset condition. But I guess, the question is asking to pick choices among the ones given. Perhaps they just want to check if you know C and D are exactly the same number. $\endgroup$ – Anurag A Jan 29 '17 at 23:42
  • $\begingroup$ Thank you for fast answer. $\endgroup$ – MatNovice Jan 29 '17 at 23:47

The question is a little bit ambiguous and vague, but I think it asks you to find the lowest possible number $n$, s.t. each set of $n$ elements has to have three distinct subsets of 2 elements having the same sum modulo $50$.

Here's why the answer is $15$. First if $n=15$, there are $\binom{15}{2} = 105$ subsets of 2 elements and therefore by Pigeonhole Principle at least three of them have to have the same sum modulo $50$, as there are $50$ different congruence classes modulo $50$.

Now it's enough to prove that there exists a set of $14$ elements, which doesn't satisfy the condition. As previously we have $\binom{14}{2} = 91$, so it's not impossible to find such a set, although generating one might not be an easy task.

| cite | improve this answer | |

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.