We need more birds

Probability Level 2

True or false?

Any of set of 501 numbers from (1, 2, 3, ... , 1000) contains two that are coprime.

Image Credit: Wikimedia McKay .
This question makes no sense True False There is insufficient information

Pi Han Goh by Pi Han Goh , 30, Malaysia

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Satyajit Mohanty
Jul 24, 2015

By Pigeon-Hole Principle, it's obvious that if we choose any of the 501 numbers from (1,2,3, ... ,1000), then there will be atleast one pair of numbers which would be consecutive. Therefore, those two consecutive numbers would be co-prime. Hence, the answer.

3 Helpful 0 Interesting 0 Brilliant 0 Confused

The question should state 'atleast', shouldn't it?

Vishnu Bhagyanath - 5 years, 10 months ago

Log in to reply

Yeah! @Pi Han Goh , what do you think about it?

Satyajit Mohanty - 5 years, 10 months ago

Log in to reply

It's not needed. There exist 2 that are coprime. I'm not saying that are exactly 2 that are coprime.

Pi Han Goh - 5 years, 10 months ago
Raghav Chaudhary
Jul 24, 2015

In the list of 1000 integers from 1,2,3,......1000, there will be 500 even integers and 500 odd integers. Hence, if we prepare a list of 501 elements, there is bound to be a pair of even and odd integers.

For example: Suppose we choose the first 500 elements as all the even integers, the 501st element will definitely be odd. Similarly, if we choose first 500 elements as all the odd integers, the 501st element will be even. And it is always true that an even and an odd integer are always co-prime.

1 Helpful 0 Interesting 0 Brilliant 0 Confused

CORRRRRRECT

Pi Han Goh - 5 years, 10 months ago

Who told you this?

"And It is always true that an even and an odd integer are always co-prime".

What about 6 and 9 ?? Even and Odd Integer, are they coprime?

Satyajit Mohanty - 5 years, 10 months ago

Log in to reply

OH haha, you're right. This solution is almost correct.

Pi Han Goh - 5 years, 10 months ago

SLACK SLACK SLACK SLACK!!!!

Pi Han Goh - 5 years, 10 months ago

Yeah you are right . Actually, what is true is that when you create a list of 500 even numbers, the 501st number will be odd. This 501st odd number will definitely be consecutive to some even number, and these two consecutive numbers will constitute a pair of co-prime numbers. Same can be extended for the case when a list of odd numbers is prepared.

I apologize for the horrible oversight committed earlier. I was actually in a hurry to write the solution down. Got to be more careful next time.

Raghav Chaudhary - 5 years, 10 months ago
Mohit Gupta
Jul 24, 2015

An easy example of Pigeon-Hole Principle

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...