GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
135 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 (883 points)   | 135 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

+1 vote
0 answers
1
asked in Operating System by Parker12 (21 points)   | 28 views
0 votes
1 answer
2
asked in Algorithms by Ketan Dhakate (109 points)   | 47 views
0 votes
0 answers
3
asked in DS by Bhargav Zantye 1 (21 points)   | 101 views


Top Users Aug 2017
  1. Bikram

    5034 Points

  2. ABKUNDAN

    4730 Points

  3. akash.dinkar12

    3488 Points

  4. manu00x

    3296 Points

  5. rahul sharma 5

    3178 Points

  6. makhdoom ghaya

    2530 Points

  7. just_bhavana

    2428 Points

  8. stblue

    2240 Points

  9. Tesla!

    2076 Points

  10. joshi_nitish

    1830 Points


25,032 questions
32,178 answers
74,991 comments
30,218 users