28-04-10: Probability

This one is a question someone asked me a few days back.. I guess it is from a ISI paper... (I may be wrong!)

There is a matrix which is NxN

Each element is filled with either 1 or -1 with an equal probability.

What is the probability that the product of all the elements of each row and of each column in the matrix is -1?

**(As always, for students only ;)

55 Answers

1
student ·

sir i have taken care of all the elements

my only claim is

that for every random arrangement there exists one unique arrangment that satisfies the condition

1
student ·

the symmetry is a possible reason

P(row) =P(coloumn)

62
Lokesh Verma ·

no this part is ok.. that P(row)=P(column)

but then this should not be the answer for the final P

1
student ·

ok

my approach itself was totally wrong

the fact that both these events are dependent itself says it all

sorry to waste ur time bhaiya

62
Lokesh Verma ·

Dont worry, it is not about wasting time :)
It is about learning new things..

1
student ·

the number of ways of doing such that our comdition is satisfied is same no.of ways of filling (N-1)*(N-1) matrix with 1 and -1

but how is that ?

62
Lokesh Verma ·

Statement 1: Precisely Correct

Statement 2: Think

Conclusion: For the first time you are thinking in the right direction ;)

:D

1
student ·

can u please post the solution ?

62
Lokesh Verma ·

Ok the hint first....

Lets fill the first n-1 x n-1 matrix randomly.....
SO what is left is the last row and the last column.....

Now think.....

1
student ·

for every random arrangment
the last row and coloumn can be filled in a unique way such that the product is -1

so total arrangments is

2n-12

hence the answer is
\frac{2^{^{n-1}^{2}}}{2^{n^{2}}}

62
Lokesh Verma ·

there are 2n-1 elements... you have taken care of only 2n-1...

WHata bout the one element left at the extereme diagonal corner.?

11
Devil ·

No - see this, I just segregate 1 row and 1 column, and fill the others ramdomly in 2(n-1)2 ways - and to make the prod negative, I shall likewisely fill the segregated row and column.

1
student ·

thast what i told soumik

11
Devil ·

Soory - did not see u.

I was actually quite excited having suddenly got the idea and did not have patience to go thru all the stuff.

11
Devil ·

OK - now got it.

62
Lokesh Verma ·

I get ur claim.. but then have you proved it?

I could on the contrary claim that this is never possbile reducing the probability to zero..

I mean you need to give some justification of your claim

11
Devil ·

What I did is ok or not?

62
Lokesh Verma ·

Soumik I dont knwo if you yourself have any clue of what you are saying.. Do you ever read posts by others?!!

REad post 47 bt me... What is the proof of what you are saying.. MOst of your posts today have make me wonder if you are thinking at all today!

1
harsh jindal ·

NISHANT SIR , SOUMIK needs rest

62
Lokesh Verma ·

wow.. i guess I will finally have to give the complete logic...???

Bhargav.. you want to give the complete answer?

39
Dr.House ·

ok here is my solution

without loss of generality remove the first row and first coloumn and what u have is a (n-1)x(n-1) matrix

fill this (n-1)x(n-1) matrix in any way u want

now what u do is

come to the element a1-2 that is 1st row 2ound coloumn element

now multiply all the elements of the coloumn below it

if the product of elements in that coloumn is is -1 , let this a1-2 be 1 and if their product is 1 , let this a1-2 be -1

similarly for the a1-3 element , look at the coloumn below it .. if product of all the elements in that coloumn is 1, let this a1-3 be -1 and if their product is -1 , let this a1-3 be 1

similarly fill all elements of this first row

use a similar process for first coloumn from a2-1 onwards

for a2-1 , if u have product of all the elements in the row beside it as -1 , let this a2-1 be 1 and of their product is 1, let this a2-1 be -1

fill all elements of this first coloumn similarly

now we r left with a1-1

now u see that all remaining elements in the 1st row and first coloumn can be uniquely determined depending on the aarrangement of the (n-1)x(n-1) matrix

so the product of all remaining elements in 1st row and 1st coloumn will be the same (test it out on a matrix if u want to see for it yourself)

then u can accordingly put a1-1 as 1 or -1

if the product of remaining elements (except a1-1) in first row is -1 , then product of remaining elements(except a1-1) in the first coloumn will also be -1 .. then u keep a1-1 as 1

in the other case u keep a1-1 as -1

hence u can always make it as prooduct equal to -1

the probability hence comes out to be 2(n-1)2/2n2

62
Lokesh Verma ·

Good work bhargav..

I will have to try and put it in a simpler way i guess :P

39
Dr.House ·

all the best :D

11
Devil ·

so the product of all remaining elements in 1st row and 1st coloumn will be the same (test it out on a matrix if u want to see for it yourself) - I did not get this.

How do u prove the diagonal element is going to satisfy both prod of rows and columns to be <0?

1
student ·

exactly soumik !

how can u prove the diagonal element is going to satisfy both prod of rows and columns to be <0?

62
Lokesh Verma ·

That part is not very difficult.. If you think closely :)

1
student ·

i think one must use strong induction to prove

@bhaiya tried a lot can u please take efforts to post that part of solution

62
Lokesh Verma ·

See the question is simple the product of each element in the last column (except the corner one) is equal to the product of elements in the (n-1)x(n-1) matrix

similarly the product of each element in the last row (except the corner one) is equal to the product of elements in the (n-1)x(n-1) matrix

Hence the product of elements in the last row (barrring the corner) is equal to the product of the elements in the last column (barring the corner)

[1]

1
harsh jindal ·

i agree with Nishant SIr about Soumik

62
Lokesh Verma ·

we take each row or column seperately...

Your Answer

Close [X]