Elegant primes?

Probability Level 1

True or False?

If 51 distinct integers are chosen within 1 to 100 (inclusive), then there exists at least 2 of these numbers such that they must be coprime.

False True

2 solutions

Jessica Wang
Jul 20, 2017

Relevant wiki: Pigeonhole Principle

Divide the numbers into $50$ sets: $\left \{ 1,2 \right \}$ , $\left \{ 3,4 \right \}$ , $...$ , $\left \{ 99,100 \right \}$ .

Then, by the Pigeonhole Principle, the $51$ chosen integers must contain two numbers in the same set.

Since those two numbers are adjacent integers, they must be coprime , this is because:

$\gcd{(n,n+1)}=\gcd{(n,1)}=1$ , by the Euclidean Algorithm .

Oh. I see i see. Thanks for the solution. :D

It states that for $k$ sets given, if you choose $k + 1$ things in the sets given, it is guaranteed that 2 numbers was in the same set.

Am I right somewhat? :D

Christian Daang - 3 years, 10 months ago

What is the largest number of distinct integers we can choose from 1 to 100 inclusive, such that no 2 of them are coprime?

Calvin Lin Staff - 3 years, 10 months ago

50; as we can pick 2, 4, 6, 8 ..... 100.

Siva Budaraju - 3 years, 10 months ago

Christian Daang
Jul 20, 2017

Some sort of logic I think.

If you choose the 50 even integers from 1 to one hundred and try to get one odd prime, then, there is always a chance that there is 2 numbers that are coprime, like for example.

{2, 4, 6, 8, 10, ..., 50, 11} ( cause 11 and 12 are coprime. :) )

Hence, the answer. :)

I think, the other solution for this is pigeon-hole principle? But I don't know how to apply it here. HAHA.

Elegant primes?

2 solutions

0 pending reports