GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
115 views

What is the minimum number of ordered pairs of non-negative numbers that should be chosen to ensure that there are two pairs (a, b) and (c, d) in the chosen set such that "a ≡ c mod 3" and "b ≡ d mod 5"

-------------------------------------------------------------------------------------------------------------------------------------------

Solution given is like this : 

a = c mod 3 (given) Thus, ‘a’ can be any one of these values : 0, 1, 2 
b = d mod 5 (given) Thus, ‘b’ can be any one of these values : 0, 1, 2, 3, 4 
Thus, ordered pair for (a, b) are : (0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4) 
Therefore, ordered pair (a, b) has 15 combinations and ordered pair (c, d) has 1 combination. Total combinations = 15 + 1 = 16 
 

-------------------------------------------------------------------------------------------------------------------------------------------

My doubt is cant it be acheived by having just two ordered pairs?? for example:  (2,1) and (8,6) ...so we can have 

a=2,b=1,c=8,d=6 ....and 

"2 ≡ 8 mod 3" and "1 ≡ 6 mod 5"

asked in Set Theory & Algebra by Junior (727 points)   | 115 views
@Anand . You are choosing the pairs blindly. The, in order to guarantee that both conditions are satisfied, what should be #pairs choosen?
i didn get you ....can u pls elaborate
I mean you need to choose pairs randomly without looking at the pairs.
is this wat the question means???

how many (minimum #)ordered pairs should be there in a set such that if we take any two ordered pairs (a,b) and (c,d) ....then the property holds....

then my set {(2,1),(8,6)} holds the property

Now imagine in this way.

You dont know the conditions to be met.

 

Now, you are supposed to select how many pairs to guarantee that after choosing the pairs(and then you are told the conditions), there will be pairs that meet the conditions?

now i get it .......very well explained ....thanx a lot..... :)

Please log in or register to answer this question.

Related questions

0 votes
1 answer
1
asked in Algorithms by Ketan Dhakate (109 points)   | 26 views
0 votes
0 answers
2
asked in DS by Bhargav Zantye 1 (21 points)   | 65 views


Top Users Jun 2017
  1. Bikram

    3912 Points

  2. Arnab Bhadra

    1526 Points

  3. Hemant Parihar

    1502 Points

  4. Niraj Singh 2

    1501 Points

  5. Debashish Deka

    1480 Points

  6. junaid ahmad

    1432 Points

  7. pawan kumarln

    1286 Points

  8. Rupendra Choudhary

    1242 Points

  9. rahul sharma 5

    1240 Points

  10. Arjun

    1232 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 26 - Jul 02
  1. pawan kumarln

    418 Points

  2. akankshadewangan24

    334 Points

  3. Arjun

    272 Points

  4. Debashish Deka

    234 Points

  5. Abhisek Das

    230 Points


23,433 questions
30,149 answers
67,606 comments
28,485 users