probabiltiy

Question

5 integers randomly chosen from 1 to 2015. What is the probability that there is a pair of integers whose difference is a multiple of 4?

Answer 1

Don't know whether it is right or not ? You should check the answer !!

---

• If you take a number say 1, then other numbers can be 5,9,13,17,21............ as the diference between these number and 1 is a multiple of 4.
• Now, if you take 2, then other numbers can be 6,10,14,18,22........... as again difference is a multiple of 4.

Take an example of 5 distinct integers => 102 , 2014 , 517, 343 , 1009 

• Here, difference of 1009 - 517 = 492 which is offcourse a multiple of 4

Take another example => 555 , 1 , 960 , 1549 ,1968

• Here, difference of 1968 - 960 = 1008 which is also a multiple of 4.

Take one more example => 129 , 2015 , 17, 740 , 1796

• Difference between 1796 -  740 is a multiple of 4.

So, if something is divisible by 4, then remainder is 0 and if not, then remainder is either 1,2,3 . 

Now, I guess Dirichlet principle can be applied here also known as pigeonhole principle, 

You have 5 integer numbers (Pigeons) and 4 labelled blocks (Pigeonholes) . 

Now, take any 5 numbers and see their last digits and divide them by 4 and place them in the particular block , it will surely fall in the blocks labelled as 0 , 1 , 2 , 3 ( These blocks are made based on the remainder obtained by dividing the number by 4 ) 

• I took this example => 129 , 2015 , 17, 740 , 1796
• 129 drops into 1 
• 2015 drops into 3
• 17 drops into 1
• 740 drops into 0
• 1796 drops into 0 . 

Here, by the pigeonhole principle, there is definitely atleast one pair which falls in the same block.

Hence, the probability that there is a pair of integers whose difference is a multiple of 4 will be 1, that is you will always find a pair which belongs to same remainder block.

Comments

thanks @kapil,i got that

---

Is the answer right ?

---

yes,its absolutey right..can you tell me whts the answe if we would have taken 3 inteqad of 5 integers..will it be 1/4 ??

---

Thanku and Yes, Take 3 numbers dropping to the same block !!

---

@Kapil, @Akirti, How it is 1/4 ,  if we take 3 instead of 5 integers ?

I am getting 5/8.

And How does range of integers( randomly chosen from 1 to 2015 ) affects the ans --  ??

---

@Vijay, how 5 / 8  ?

---

@vijaycs You have to choose 3 different holes (remainders), so numerator of probability expression is $\binom43$ and denominator is 4*4. Order is important here since putting 1st number in hole 1 is different from putting the 2nd number in hole 1. Therefore $1/4$. Range of numbers will not affect the anser as long as you have enough numbers to choose from.

---

Denominator must be 4³ as each number can go to any of the 4 holes.

---

3 integers randomly chosen from 1 to 2015. What is the probability that there is no pair of integers whose difference is a multiple of 4?

---

@vijaycs

I am still getting 1/4 . what are you getting ?

---

3 integers randomly chosen from 1 to 2015. What is the probability that there is no pair of integers whose difference is a multiple of 4?

For the above one - 

P = (1) * (3/4) * ( 2/4)   // placing 3 different numbers having different remainders(0,1,2,3).

So, for -

3 integers randomly chosen from 1 to 2015. What is the probability that there is a pair of integers whose difference is a multiple of 4? 

P' = 1- P.

??

---

But, how did you got P as this ?

---

according to my logic.if we take first number,then it will go to the box with which it remainder matches,it will not go to any of the 4 holes available,so its probability is not 1/4,and then the next number to have same remainder as the previous number only can go to that previous hole,so its probabiltity will be 1/4.

hence,so far probabiltity is 1*1/4

and for 3rd digit,it can go to any of the holes as we have already got a pair now,but i dun know how to go further

---

P = (1) * (3/4) * ( 2/4)   // placing 3 different numbers having different remainders(0,1,2,3).

First number having remainder any among 0,1,2,3.  => p=1.

Second number having a remainder among 0,1,2,3 but not the same as the first remainder. =>3/4.

3rd number having a remainder among 0, 1, 2, 3 but not the same as the first or 2nd remainder. => 2/4.

---

@vijaycs,whats wrong with my logic??

---

@Akirti, your approach is correct. I have just stuck with my wrong approach.

Can you please check where I am going wrong ..

---

@vijascs,your approach also loooks correct to me.

i am now getting answer as 5/8 by this approach

 

So if there are three numbers, the first number can go to one of the 4 slots.. Can be done in 4C1 ways.

 

Suppose we don’t want second  number to go to same slot as first – we can do it in 3C1 ways.

 

Similarly if we don’t want third number to go to same slots as first two – we can do it in 2C1 ways.

 

So total ways (for each slot containing only one number) = 4 x 3 x 2 = 24

 

Total possible ways = 4^3= 64

 

Prob (we cannot find a pair) = 6/16

 

Prob(we can find a pair) = 1 – 6/16 = 5/8

---

When selecting less than less than or equal to 4 numbers, the answer depends on the range of numbers. If more than 4 can be selected then the probability is always 1 provided we have sufficient numbers to choose from. Check this program http://ideone.com/oMtXiY Just change the number on line number 10 to run it for different cases (choosing 3, 4, 5, ... numbers). To change the range of numbers change line number 37. This gives probability in all cases where we can select 5 or more numbers.

---

but can you tell the probability for 3 intgers if we have given enough integers??

---

if the range is from 1 to 8 and we can select 3 numbers, probability is 0.4286, I have also printed the combinations where no pair has a difference which is multiple of 4. check the link in my previous comment. dont run it for very large values as it has exponential complexity so it will take very long time.

---

but the probabilty is 1/4, right ? If we are given the same range as given in the question.

---

@kapil,now even i am confused with 1/4 because i am finding @vijascs approach to be correct also if we do by complement method.

can you explain how you are getting 1/4??

---

I took last slot also into account. My Bad !! Right then it should be 5/18 .

---

@kapil Unfortunately that cant be verified with my program but I feel all solutions that dont take the range of numbers into consideration are incorrect. The reason is that the numbers are being put into holes on the basis of their remainder with 4 and not randomly. And the count of numbers belonging to a particular hole depends on the range given. Consider the range 1 to 6. Numbers in hole 0 = {4}, numbers in hole 1= {1, 5}, numbers i hole 2 = {2, 6}, numbers in hole 3 = {3}. Now consider the range 1, to 7, Numbers in hole 0 = {4}, numbers in hole 1= {1, 5}, numbers i hole 2 = {2, 6}, numbers in hole 3 = {3, 7}. This proves that the denominator can not be 4^3.

PS: The above points are for the case where we choose less than or equal to 4 numbers from a given range.

---

i did not get you..how are you getting 5/8 as answer??by same approach as a described above??

but i have one confusion,should'nt the probability for first integer be 1/4 because as integer's remainder will match with only one of the slots?and then for second integer,it should be 1/4 again as it has to match with the same slot in which previous was matched and for 3rd variable,it can match with any slot.

so,prob should be 1/4 * 1/4..

i am very much confused now..

---

@Arjun Sir, 

Can you please check these 2 questions !!

3 integers randomly chosen from 1 to 2015. What is the probability that there is no pair of integers whose difference is a multiple of 4?

3 integers randomly chosen from 1 to 2015. What is the probabiliy that there is a pair of integers whose difference is a multiple of 4?

---

@air1,denominator will be 4^3 only because each integer has 4 slot choices

---

@AKriti. My bad.

If they are asking for no pair has difference 4, then it should be like this:

P(First element going to any hole) *  P(2nd elemnt going to remaining 3 holes)

* p(3rd elemnt going to remaining 2  holes)

= 1 *  3/4 * 2/4

= 3/8

Now, atleast 1 pair has difference of 4 = 1 - 3/8 = 5/8

=========================================

I think my approach is wrong for the following example Air1 gives.

---

EDITED

What is the answer for "choosing 3 integers from 1 to 4 such that there is a pair whose difference is a multiple of 3"?

---

i just have one doubt here,

how is the prob of first element be 1.It should be 1/4 because an integer can onle be placed in 1 remainder slot,it cannot occupy any slot.so favourable case should be 1 only.so,prob should be 1/4

pls correct me..thanks1

---

@Akriti. Yes. But, for it to not collide to with anyone, which slot should it go? Any slot will do, right? so, probablity that it doesnt collide is 4/4 or 1, right?

---

@air1 ,i think it is 1/3 because only pair is (1,4) which will be mapped to slot with remainder 1

---

if you are thinking wrt to collision ,then it is 4/4 but i am thiking w.r.t how many options it has .

anyways,thanks for help

---

@sushant gokhale,how will u solve it without complement mehtod??

---

What is the answer for "choosing 3 integers from 1 to 4 such that there is a pair whose difference is a multiple of 3"?

according to my code, the cases where none of the difference is a multiple of 3 are {1, 2, 3} and {2, 3, 4} and the total ways to choose 3 integers from 4 is $\binom43$ = $4$, so the answer is 0.5., final answer is complement of this ie 0.5

for "choosing 2 integers from 1 to 4 such that there is a pair whose difference is a multiple of 3"?

none of the difference is a multiple of 3 = {1, 2}, {1, 3}, {2, 3}, {2, 4} and {3, 4}. total ways  = $\binom42$ = 6. final answer = 1 -  5/6 = 1/6 = 0.16

---

what is 1/4 here??

can you tell me how will u solve it without complement mehtod??

---

@Air1. You need to compute permutations bcause I can even have {4,3,2} ,right?

---

for "choosing 2 integers from 1 to 4 such that there is a pair whose difference is a multiple of 3"?

none of the difference is a multiple of 3 = {1, 2}, {1, 3}, {2, 3}, {2, 4} and {3, 4}. total ways  = $\binom{4}{2}$ = 6. final answer = 1 -  5/6 = 1/6 = 0.16 the only favorable case is {1, 4}.

We have seen all possibilities here so the answer is obviously correct for this case. Now someone please add some explanation about how to get this answer.

---

I was just curious to know the way how it will be solved without complement,,:-)

---

Choosing N numbers from a range 1 to R has $\binom{n}{r}$ possibilities, order isnt important.

---

@Air1. You are right. Let me think from your example.

---

@Air1 and Akriti. Sorry. I am not able to think. I will edit my answer in the comment.