1
$\begingroup$

This question is inspired by the game Quarto.

On a $2^k$ by $2^k$ grid, arrange the $2k$-digit binary numbers. Are there any, and if so, how many, configurations such that there is no row, column, (optionally: also diagonal) where all numbers have the $n$:th bit in common, for any $n$?

For example, for $k$ $=$ $1$ there are no solutions: without loss of generality, put 00 in the top left. Then 11 must go in every other space, which is impossible.

$\endgroup$
6
  • $\begingroup$ The title says something different $\endgroup$ Oct 29, 2016 at 14:09
  • $\begingroup$ @BeastlyGerbil Better now? $\endgroup$ Oct 29, 2016 at 14:35
  • $\begingroup$ Can you clarify the question concerning $n$? I'm a tad bit confused. $\endgroup$ Oct 29, 2016 at 17:39
  • $\begingroup$ @greenturtle3141 The first bit is not the same for all numbers, the second bit is not the same for all numbers, and so on. $\endgroup$ Oct 29, 2016 at 17:40
  • $\begingroup$ For example, for k=1 it is 00, 11 // 11, 00 (without satisfying an optional requirement for diagonals). $\endgroup$
    – CiaPan
    Oct 29, 2016 at 22:13

2 Answers 2

4
$\begingroup$

For what it's worth

Here is an arrangement for $k=2$ satisfying the row and column constraints, and the constraint for the two main diagonals.

    1111    0100    0111    1001
    1010    0001    0101    1000
    1101    1011    0010    0110
    0000    1110    1100    0011

$\endgroup$
4
  • $\begingroup$ ...at least if I interpreted the question correctly? $\endgroup$ Oct 29, 2016 at 17:46
  • 2
    $\begingroup$ I dont understand the question at all, so +1 for trying $\endgroup$ Oct 29, 2016 at 18:02
  • $\begingroup$ I think you interpreted it correctly. This is a solution for $k =2$ without the diagonals constraint: in one diagonal the first bit is always 1 and in the other diagonal the fourth bit is always 1. +1 $\endgroup$ Oct 29, 2016 at 18:47
  • $\begingroup$ Ohh, just the two main diagonals? I have made a small alteration that satisfies that. $\endgroup$ Oct 29, 2016 at 18:49
2
$\begingroup$

I haven't tried to count solutions (which seems likely to be extremely difficult in any case where the number isn't proved to be zero), but

when $n>1$ there is always a solution, even with the diagonal constraint.

Proof:

Let's begin by writing the numbers in order, starting with $0^{2k}$ at top left and proceeding along rows. Then on every row, each of the bottom $k$ bits is $0$ exactly $2^{k-1}$ times and $1$ exactly $2^{k-1}$ times; and on every column, the same goes for the top $k$ bits. Unfortunately, the high bits are constant on each row and the low bits are constant on each column.

Now

reverse the main diagonal, so that e.g. with $k=3$ instead of going 000000,001001,010010,011011,100100,101101,110110,111111 it goes 111111,...,000000. Note that this is exactly equivalent to complementing all the bits on the main diagonal. This changes only one item on any row or column and hence can't break the "good" property for the low bits on the rows or the high bits on the columns; but because it flips all the bits for one entry on each row and for one entry on each column, it necessarily kills the "bad" property for the high bits on the rows and the low bits on the columns.

The diagonals

are also good. The main diagonal, as seen above, has every $k$-bit number appearing once in its low bits and once in its high bits; the process above changes the order of appearance of these entries but not what they are. The other diagonal also has every $k$-bit number appearing once in its low bits and once in its high bits; the difference is that now the low and high bits are complements of one another.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.