Mathematics desk
< May 15	<< Apr \| May \| Jun >>	May 17 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

May 16

Magic square type Combinatorics Problem

The problem is:

In how many ways can you put 1 and -1 in the 16 places of a 4*4 square so that the product of any row or column is -1.

I figured out that -1 can be written by the product of 1s and -1s in only two ways:

-1 = 1 * 1 * 1 * -1 or -1 = -1 * -1 * -1 * 1

But I cannot figure out the solution. Any help appreciated. Solomon7968 (talk) 09:46, 16 May 2013 (UTC)[reply]

There are 2^16 = 65536 ways to distribute minuses in the the 4*4 square. The probability that any row or column multiplies to -1 is 50%. There are 4 rows and 4 columns. The probability that they all multiply to -1 is 2^(-8). So the answer to your question is probably (2^16)*(2^(-8))=2^8=256. Bo Jacoby (talk) 10:40, 16 May 2013 (UTC).[reply]

I am new to combinatorics. Will you explain how you got the 50% thing? Solomon7968 (talk) 10:43, 16 May 2013 (UTC)[reply]

Consider any row or column. There are 4 places. Each place can contain either +1 or -1. The sixteen possibilities are ++++ +++- ++-+ ++-- +-++ +-+- +--+ +--- -+++ -++- -+-+ -+-- --++ --+- ---+ ----. Eight out of these sixteen possibilities have an odd number of minuses and so multiplies to minus. (Namely +++- ++-+ +-++ +--- -+++ -+-- --+- ---+ ). So the probability that a random row multiplies to minus is 8/16=1/2=50%. Bo Jacoby (talk) 10:51, 16 May 2013 (UTC).[reply]

There's 512 ways. You can put any combination of +1 and -1 into the first 3x3 places. Then just place a +1 or -1 as appropriate into the last row or column to make the produce -1. The product of the three end columns will be te same as the three rows as they are determined by the product of all 9 numbers so there is no confusion about the last end number to put in. Dmcq (talk) 10:58, 16 May 2013 (UTC)[reply]

...and this is consistent with Bo's probabilistic approach once you take into account the fact that the 8 row/column products are not independent - once you know any 7 of them then the 8th is determined by the contraint that product of row products = product of column products. Correcting this in Bo's formula gives 2^16 / 2^7 = 2^9 = 512. Now for bonus points determine how many arrangements there are if reflections and rotations of an arrangement are not counted as distinct. Gandalf61 (talk) 13:07, 16 May 2013 (UTC)[reply]