Integer Array With Avoidance

First note that the subsets of $\{ 1, ... , N \}$ can be labeled $S_1, ..., S_{2^N}$ such that $S_i \not\subset S_j$ for any $i<j$ .

(One way to do this is to define, on the power set of $\{ 1, ... , N \}$ , the one-to-one function $f(S)= \sum_{i\in S} 2^i$ and then label the subsets such that $f(S_i)$ is decreasing as a function of $i$ .)

For $N=7$ we can use the sets $S_1, ..., S_{100}$ . In particular, if for each pair $i,j$ we choose any

$a_{i,j} \in S_i - S_{i+j}$

if $i+j\le 100$ , or $a_{i,j} \in S_i$ if $i+j > 100$ then it follows that $a_{i,j}$ does not appear in the $(i+j)$ -th row, as desired.

Next we will assume that the condition holds and show that $N\ge 7.$ So we know that for any two rows, let's say $i$ and $k$ with $i<k$ , row $i$ contains at least one number that is not in row $k$ (namely $a_{ij}$ where $j=k-i$ ). Therefore, the total number of rows cannot be more than the number of nonempty subsets of $\{ 1, ... , N \}$ . That is to say, $100 \le 2^N-1$ , which means that $N\ge 7$ .

The solution is that for a table with dimension $d$ such that $2^{k-1} \le d \lt 2^{k}$ , it can be filled with symbols $1$ through $k$ , and no fewer.

This is one of those ones where you can understand the pattern easily but it takes a long time to put into proof form :) Here is a diagram to help ; the essence of it is that it is a fractal pattern, with triangles of side length $2^k-1$ repeating, for each $k$ . I have highlighted the main diagonals which are crucial to my argument below. Note that this is not the only possible solution.

I will prove by induction that no fewer symbols are possible for each $k$ and then give an explicit solution for each $d$ . When I refer to the cell $a,b$ below I mean the position in row $a$ , column $b$ , where the first row is row $1$ etc, and the cell $1,1$ is the top-left cell.

This is a slightly trickier induction than usual because my induction includes a supposition and thus establishes a necessary but not sufficient condition, but I think it is valid.

Induction Hypothesis: For a triangle of side length $2^n-1$ starting at $a,b$ , by which I mean its vertices are $(a,b), (a+2^n-2,b), (a,b+2^n-2)$ , then if it is filled with symbols $1$ through $n$ , then the main diagonal (i.e. the cells such that $i+j = a+b+2^n-2$ ) must contain all symbols $1$ through $n$ .

Initial Step: For $n=1$ , the "triangle" is a single cell and it can be filled with the symbol $1$ , and the main diagonal contains all symbols $1$ through $1$ .

Induction Step: Assume the hypothesis is true for $n=k$ . yellow triangle in my diagram . Consider row $a + 2^k-1$ , i.e. the first row that lies completely below the triangle. Because all values $1$ through $k$ are represented on cells such that $i+j = a + 2^k-1$ (that is part of the hypothesis), this row cannot contain any of those symbols.

Suppose that we now wish to fill the remainder of the triangle of side length $2^{k+1}-1$ starting at $a,b$ with symbols $1$ through $k+1$ , leaving unchanged the cells belonging to the contained triangle of side length $2^k-1$ that we assumed is already filled in.

Since the row we are considering cannot contain $1$ through $k$ , all of its cells that lie within the triangle must contain $k+1$ .

Now consider the triangle of side length $2^k-1$ starting at $a + 2^k$ . yellow triangle below another yellow triangle in my diagram It cannot contain the symbol $k+1$ because the presence of $k+1$ in every cell on the row above this triangle prevents this. However, by the induction hypothesis it is possible to fill this triangle with at most $k$ symbols. Therefore , by the induction hypothesis again, its main diagonal must contain all symbols $1$ through $k$ .

But the main diagonal of this triangle coincides with the main diagonal of the larger triangle of side length $2^{k+1}-1$ . So the main diagonal of this larger triangle must contain $1$ through $k$ , and also $k+1$ due to the row that contains only $k+1$ .

Since the row $a + 2^{k+1}-1$ cannot contain any member of that main diagonal, a new symbol is required for this row. This completes the proof that if there are at least $2^k$ rows then we require at least $k+1$ symbols.

Explicit Solution: Now we show that there is actually a solution with this number of symbols. For this solution, to simplify the language I will count cells from $0$ , so that the top-left cell is $0,0$ , and the value in cell $a,b$ must not occur in row $a+b+1$ .

This is the solution that appears in my diagram:

For the cell $a,b$ , write out $a$ and $b$ in binary, with extra zeroes at the left if required. Let $p$ be the first bit-position such that $a$ and $b$ both have a $0$ in that position, where bit number $1$ is the least significant bit. Then the symbol $p$ goes in the cell $a,b$ .

To show that this solution meets the problem conditions: note that this solution implies that row $a$ cannot contain any symbols corresponding to a bit-position where $a$ has a $1$ -bit.

Now consider any cell $i,j$ such that $i+j+1 = a$ . Suppose the symbol in that cell is $p$ . Then $i$ and $j$ must both contain a $0$ in bit-position $p$ , and there is no lesser bit-position where both $i,j$ contain a $0$ . Therefore the minimum possible value for $i+j$ has $0$ in position $p$ and $1$ in all other bit-positions to the right. Therefore $i+j+1$ must contain a $1$ in bit-position $p$ , so row $a$ meets the problem conditions.

Finally, the actual answer to the problem with $d=100 \lt 2^7$ is $\boxed{7}$ .

First, we have to ignore all the values of $i$ and $j$ that are more than 100, except $i=100,j=1$ . For all of these ignored entries, just fill in their value with any number earlier in the row(think about this, you'll see). Now we need to think about stacking from the bottom up. First the bottom row, then adding one row at time until we have 100. If you do it this way, you'll see that for every new line we add, each number corresponds to one of the other rows, and it must not match anything in that row. Now let's look at the first few lines:

First comes 1 Second comes 2 Third is 2 numbers, and can be 2,1 (the 2 corresponds to the 1 on line 1, and vice versa for line 2) Fourth is 3 numbers, and must introduce 3, so we might as well use 3,3,3

Now, the way that we are "forced" to add another number is when there is a line with all the numbers that we have so far. So in our example, line 3 had ${1,2}$ and therefore line 4(and any subsequent lines) had to include at least 1 number that wasn't 1 or 2. So the way that a 4 would need to be added is the line after ${1,2,3}$ . Now consider how many lines that will take after this 3 is added. Every line after must have a 3, and every line must have a different combination of numbers( because if 2 lines had the same combination, then the box in the higher one that corresponds to the other line cannot be filled.) There are $2^2$ combinations of 1 and 2, and one (1,2) is already on line 3 (that's what forced the 3 on line 4 to come out). So the first "forced" appearance of 4 is on line 8.

If you think about it, this argument will scale, and the answer for any size is the number of powers of 2 up to and including itself. So for any size from 64 through 127, the answer is 7.