Re: [math-fun] Some questions from the 2018 Putnam Exam
I never got a few things right in the statement of this problem, even on the second try. But now it's right: ----- A2 Let S_1, S_2, ..., S_(2^n−1) be the nonempty subsets of {1,2,...,n} in some order, and let M be the (2^n−1)×(2^n−1) matrix whose (i,j)th entry m(i,j) = 0 if S_i ∩ S_j is empty; m(i,j) = 1 otherwise. Calculate the determinant of this matrix. ----- Allan's point that if the order doesn't matter, the determinant must be 0 also occurred to me. But maybe they're looking for an answer of the form ±[expression] ??? In any case, if the answer doesn't turn out to be too trivial, this is a very cool problem. —Dan
The hypothesis that the determinant is zero can be checked, and possibly refuted, by an explicit calculation for small n. -- Gene On Friday, December 7, 2018, 12:24:43 PM PST, Dan Asimov <dasimov@earthlink.net> wrote: I never got a few things right in the statement of this problem, even on the second try. But now it's right: ----- A2 Let S_1, S_2, ..., S_(2^n−1) be the nonempty subsets of {1,2,...,n} in some order, and let M be the (2^n−1)×(2^n−1) matrix whose (i,j)th entry m(i,j) = 0 if S_i ∩ S_j is empty; m(i,j) = 1 otherwise. Calculate the determinant of this matrix. ----- Allan's point that if the order doesn't matter, the determinant must be 0 also occurred to me. But maybe they're looking for an answer of the form ±[expression] ??? In any case, if the answer doesn't turn out to be too trivial, this is a very cool problem. —Dan
Gene therapy! Yes, for n = 1 and n = 2, the answer is +/- 1. When I listed the subsets in an obvious "binary" order, the matrix I got had the contradiagonal and everything below it all 1. This suggested a proof sketch for all n, as follows: Arrange the subsets so that all the elements containing 1 are listed first, followed by all the ones that don't. The resulting matrix is all 1 on and above the main contradiagonal, because subsets containing 1 have nonempty intersection. Now the "sketch" part: it was very easy to use standard determinant-invariant operations to clear the other triangle of all 1s, after which one could just read off the determinant as 1. On Fri, Dec 7, 2018 at 3:32 PM Eugene Salamin via math-fun < math-fun@mailman.xmission.com> wrote:
The hypothesis that the determinant is zero can be checked, and possibly refuted, by an explicit calculation for small n.
-- Gene
On Friday, December 7, 2018, 12:24:43 PM PST, Dan Asimov < dasimov@earthlink.net> wrote:
I never got a few things right in the statement of this problem, even on the second try. But now it's right:
----- A2 Let S_1, S_2, ..., S_(2^n−1) be the nonempty subsets of {1,2,...,n} in some order, and let M be the (2^n−1)×(2^n−1) matrix whose (i,j)th entry m(i,j) = 0 if S_i ∩ S_j is empty; m(i,j) = 1 otherwise.
Calculate the determinant of this matrix. -----
Allan's point that if the order doesn't matter, the determinant must be 0 also occurred to me. But maybe they're looking for an answer of the form
±[expression]
??? In any case, if the answer doesn't turn out to be too trivial, this is a very cool problem.
—Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I don't think the "+-, therefore 0" argument works. It requires that permuting the Si change the sign of the determinant. But the problem seems to require that the row ordering of Si is the same as the column ordering. If you swap two rows of the matrix, you must also swap two corresponding columns. The determinant changes by (-1)(-1), i.e. not at all. Any permutation can be built from swaps, so the ordering of Si doesn't matter. (Does the Putnam use trap questions?) I don't know if this matters for a proof, but M is symmetric. Rich ---- Quoting Dan Asimov <dasimov@earthlink.net>:
I never got a few things right in the statement of this problem, even on the second try. But now it's right:
----- A2 Let S_1, S_2, ..., S_(2^n?1) be the nonempty subsets of {1,2,...,n} in some order, and let M be the (2^n?1)×(2^n?1) matrix whose (i,j)th entry m(i,j) = 0 if S_i ? S_j is empty; m(i,j) = 1 otherwise.
Calculate the determinant of this matrix. -----
Allan's point that if the order doesn't matter, the determinant must be 0 also occurred to me. But maybe they're looking for an answer of the form
±[expression]
??? In any case, if the answer doesn't turn out to be too trivial, this is a very cool problem.
?Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Allan Wechsler -
Dan Asimov -
Eugene Salamin -
rcs＠xmission.com