DM-Sets,Relations and Functions-Q8

+2 votes

How many nonzero entries does the matrix representing the relation R on A = \{1, 2, 3, . . . , 1000\} consisting of the first 1000 positive integers have if R is \{(a, b) | a + b \leq 1001\}?

asked Jul 5 in Discrete Maths by gbeditor (15,310 points)
reshown Jul 6 by gbeditor

3 Answers

+3 votes
 
Best answer

matrix representation of \text{R} will contain 1000 \times 1000 cells.

a + b \leq 1001(a > 0, b > 0) 

can also write above equation with dummy variable c,

a + b + c =1001\left ( a > 0 , b > 0, c \geq 0 \right )

a + 1 + b + 1 + c = 1001

a + b + c = 999

\binom{999+3-1}{3-1} = \binom{1001}{2} = 500500

 

answered Jul 6 by tsutkarsh-mk84 (1,390 points)
selected Jul 9 by getgatebook
i have done  like this .
i also did the same...
me too
same ans
Can u tell me where i went wrong i approached this question in this way ,,

We have condition a+b<=1001 so possible equations are as follows
a+b=2    total cases here 2-1+2C2 =3C2 =3
a+b=3    total cases here 2-1+3C3 =4C3 =4
.....
.....
a+b=1001 total cases here 2-1+1001C1001 = 1002C1001=1002

if we sum all these we get 502500
bro i dont know how you are getting a+b =2 in 3 ways. a+b=2 only when a=1,b=1;
similarly a+b=2 only when(1,2) or (2,1) so only two ways. similarly for the rest.
your solution for a+b=x is wrong
thanks i think i missed the condition a>=1 and b>=1
hmm, you missed something. (a, b) can only be the given set A={1,2,...,1000}
Thanks bro it should be like this
it can be solved by using the concept of combinatories,
We have condition a+b<=1001 so possible equations are as follows
a+b=2    since a>=1 and b>=1 modfied eq is a+b=0 total cases here 2-1+0C0 =1C0 =1
a+b=3    similarly here it is a+b=1  and total cases are  2-1+1C1 =2C1 =2
.....
.....
a+b=1001  similarly here it is a+b=999  and total cases are  1000C999 =1000

total cases here 1 + 2 + 3 + 4     ..................... 1000

if we sum all these we get 500500
Yeah, we simply had to sum the numbers 1 upto 1000
0 votes
1000*1000-500*999
answered Jul 6 by tsnikhilsharmagate2018 (19,690 points)
please explain
0 votes

With the help of matrix rep of relation 

1) find out direct all 1 entry.(in first solutions)

2)find out zero entry and than complement 

1000*1000-500*999=500500

 

answered Jul 9 by tsnikhilsharmagate2018 (19,690 points)
Answer:
...