Let n≥2 be an integer, and let O be the n×n matrix whose entries are all equal to 0. Two distinct entries of the matrix are chosen uniformly at random, and those two entries are changed from 0 to 1. Call the resulting matrix A.
Determine the probability that A2 = O, as a function of n.
The program below calculates the probability that the resulting square of A does not equal O.
But what was wanted is if it is equal to O.
clearvars,clc
for n=2:10
ct=0; hit=0;
for r1=1:n
for c1=1:n
for r2=1:n
for c2=1:n
if r2~=r1 || c2~=c1
A=zeros(n);
A(r1,c1)=1;
A(r2,c2)=1;
A2=A^2;
if ~isequal(A2,zeros(n))
hit=hit+1;
end
ct=ct+1;
end
end
end
end
end
fprintf('%2d %4d %4d %7s %13.11f
',n, hit, ct, sym(hit/ct), hit/ct)
end
finds
n hits cases prob
frac decimal
2 12 12 1 1.00000000000
3 60 72 5/6 0.83333333333
4 168 240 7/10 0.70000000000
5 360 600 3/5 0.60000000000
6 660 1260 11/21 0.52380952381
7 1092 2352 13/28 0.46428571429
8 1680 4032 5/12 0.41666666667
9 2448 6480 17/45 0.37777777778
10 3420 9900 19/55 0.34545454545
OEIS finds the hits column to be in 2*n*(n+1)*(2n+1). However n needs to be adjusted: 2*(n-1)*n*(2*n-1). To get the probability, this is divided by n^2 * (n^2 - 1):
2*(n-1)*n*(2*n-1) / (n^2 * (n^2 - 1))
which simplifies to
(4*n - 2)/(n*(n + 1))
so for the complementary probability that A^2 = O, use
1 - (4*n - 2)/(n*(n + 1))
The formula found originally is confirmed by
for n=2:10
fprintf('%2d %13.11f
',n,(4*n - 2)/(n*(n + 1)))
end
2 1.00000000000
3 0.83333333333
4 0.70000000000
5 0.60000000000
6 0.52380952381
7 0.46428571429
8 0.41666666667
9 0.37777777778
10 0.34545454545
Again these numbers should be subtracted from 1 to get the desired probability.
Modified to reverse the not equal, to equal.
Edited on September 3, 2023, 2:27 pm
|
|
Posted by Charlie
on 2023-09-03 12:13:26 |
computer solution (spoiler)
