1sir 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
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 ;)
-
UP 0 DOWN 0 0 55
55 Answers
1
62no this part is ok.. that P(row)=P(column)
but then this should not be the answer for the final P
1ok
my approach itself was totally wrong
the fact that both these events are dependent itself says it all
sorry to waste ur time bhaiya
62Dont worry, it is not about wasting time :)
It is about learning new things..
1the 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 ?
62Statement 1: Precisely Correct
Statement 2: Think
Conclusion: For the first time you are thinking in the right direction ;)
:D
62Ok 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.....
1for 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}}}
62there are 2n-1 elements... you have taken care of only 2n-1...
WHata bout the one element left at the extereme diagonal corner.?
11No - 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.
11Soory - 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.
62I 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
62Soumik 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!
62wow.. i guess I will finally have to give the complete logic...???
Bhargav.. you want to give the complete answer?
39ok 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
62Good work bhargav..
I will have to try and put it in a simpler way i guess :P
11so 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?
1exactly soumik !
how can u prove the diagonal element is going to satisfy both prod of rows and columns to be <0?
1i think one must use strong induction to prove
@bhaiya tried a lot can u please take efforts to post that part of solution
62See 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]