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.

|improve this question
$\endgroup$
  • $\begingroup$ The title says something different $\endgroup$ – Beastly Gerbil Oct 29 '16 at 14:09
  • $\begingroup$ @BeastlyGerbil Better now? $\endgroup$ – Robin Ekman Oct 29 '16 at 14:35
  • $\begingroup$ Can you clarify the question concerning $n$? I'm a tad bit confused. $\endgroup$ – greenturtle3141 Oct 29 '16 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$ – Robin Ekman Oct 29 '16 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 '16 at 22:13
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

|improve this answer
$\endgroup$
  • $\begingroup$ ...at least if I interpreted the question correctly? $\endgroup$ – Jonathan Allan Oct 29 '16 at 17:46
  • 2
    $\begingroup$ I dont understand the question at all, so +1 for trying $\endgroup$ – Beastly Gerbil Oct 29 '16 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$ – Robin Ekman Oct 29 '16 at 18:47
  • $\begingroup$ Ohh, just the two main diagonals? I have made a small alteration that satisfies that. $\endgroup$ – Jonathan Allan Oct 29 '16 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.

|improve this answer
$\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.