Return to Question

The lower bound is obtained by the following construction:

The green line four corners are of length $(\sqrt{3}-1)n/2$ entries. Using the similar argument above we can get $(\sqrt{3}-1)n+O(1)$ upper bound.

(update3: now $ r(n)\le n/\sqrt{2}+O(1)$)

The lower bound is obtained by the following construction:

The green line four corners are of length $(\sqrt{3}-1)n/2$ entries. Using the similar argument above we can get $(\sqrt{3}-1)n+O(1)$ upper bound.

Update 3: That friend, again, suggested a way: choose these entries in green, the lengths of the green lines in the four corners are $\frac{\sqrt{2}-1}{2}n$ (they are the diagonal of the square of side length $\frac{\sqrt{2}-1}{2}n$) and the central green square has diagonal length $(2-\sqrt{2})n$ These entries on the central square we give them a weight of $1/2$. So all the entries in the outside four triangles will point to weight two entries, the entries inside the central square will point to weight $1/2$ (one entry on the central square) and the rest will point to weight $1$ (two entries on the corner green lines, or two entries on the central square.) So the total weight of pointing will be $n^2+O(n)$. The total weight of green entries is $\sqrt{2} n+O(1)$, and by average, the number of entries pointed to a certain entry is at most $n/\sqrt{2}+O(1)$, so there must be one entry pointed by at most other $n/\sqrt{2}+O(1)$ entries.

The problem is as follows:

Suppose we filled a $n\times n$ square with one of the four arrows $\uparrow$, $\downarrow$, $\gets$, $\to$, like the following

$\begin{array}{|c|c|c|} \hline \downarrow & \downarrow & \gets\\ \hline \to& \to& \uparrow\\ \hline \to& \uparrow& \uparrow\\ \hline \end{array}$

We define entry $A$ (in $i$th column $j$th row) points to entry $B$ (in $k$th column $l$th row) if one of the four happens:

1. $A$ is filled with $\uparrow$ and $j> l$ and $i=k$
2. $A$ is filled with $\downarrow$ and $j< l$ and $i=k$
3. $A$ is filled with $\gets$ and $j= l$ and $i<k$
4. $A$ is filled with $\to$ and $j= l$ and $i>k$

(This is straightforward if you really fill them with arrows...)

For the example above, only the entry in first row, third entry points to the left upper corner. The right bottom corner entry points to the entry on the first row, third column and the entry on the second row, third column.

Let $r(n)$ be the maximum number such that there is a filling method such that every entry is pointed by at least $r(n)$ other entries.

Now we have a bound $\frac{2}{3}n+O(1)\le r(n)\le \frac{5}{6}n+O(1)$

(update: now $ r(n)\le \frac{3}{4}n+O(1)$)

(update2: now $ r(n)\le (\sqrt{3}-1)n+O(1)$)

The lower bound is constructed by the following:

We first split the grid into $3\times 3$ region (we ignore the remainders.) The red region is filled with $\to$, the green region is filled with $\downarrow$, The blue region is filled with $\gets$, the purple region is filled with $\uparrow$. The central square can filled with anything. One can proof that every entry are pointed by $\frac{2}{3}n+O(1)$ other entries.

On the other hand, counting the total number entries one entry can point to, there are at most $\frac{5}{6}n^3+O(n^2)$ (entry 1, entry 2) pairs that the first entry point to the second entry. So, in average, there is an entry pointed by at most $5/6n+O(1)$ other entries.

Now, the question is: can $2/3$ be raised and $5/6$ be smaller? I believe $2/3$ can be raised a little bit (for example, $0.01$) since the central $n/3\times n/3$ is not filled. But can it be substantially increased?

Any improvement is welcome and appreciated, even minor improvement with $2/3$ is welcome.

Update: a friend of mine gave me an $3/4n+O(1)$ upper bound. He considered the square connected the midpoints, where there are $2n$ entries. The entries inside the square points at most one entry on the square, and the entries outside the square points at most two. Thus, the number of entry points to the other entries is at most $1/2n^2+2\times 1/2n^2+O(n)=3/2n^2+O(n)$, and since there are $3n$ entries, averagely, one of the entries has at most $3n/4+O(1)$ entries points to it.

Update 2: That friend suggested another way: choose these entries in green

The green line four corners are of length $(\sqrt{3}-1)n/2$ entries. Using the similar argument above we can get $(\sqrt{3}-1)n+O(1)$ upper bound.

The problem is as follows:

Suppose we fill each cell of a $n\times n$ square with one of the four arrows $\uparrow$, $\downarrow$, $\gets$, $\to$, like the following

$\begin{array}{|c|c|c|} \hline \downarrow & \downarrow & \gets\\ \hline \to& \to& \uparrow\\ \hline \to& \uparrow& \uparrow\\ \hline \end{array}$

We define that entry $A$ (in $i$th column $j$th row) points to entry $B$ (in $k$th column $l$th row) if one of the four happens:

1. $A$ is filled with $\uparrow$ and $j> l$ and $i=k$
2. $A$ is filled with $\downarrow$ and $j< l$ and $i=k$
3. $A$ is filled with $\gets$ and $j= l$ and $i<k$
4. $A$ is filled with $\to$ and $j= l$ and $i>k$

(This is straightforward if you really fill them with arrows...)

For the example above, only the entry in first row, third column, points to the left upper corner. The right bottom corner entry points to the entry on the first row, third column and the entry on the second row, third column.

Let $r(n)$ be the maximum number such that there is a filling method such that every entry is pointed to by at least $r(n)$ other entries.

Now we have a bound $\frac{2}{3}n+O(1)\le r(n)\le \frac{5}{6}n+O(1)$

(update: now $ r(n)\le \frac{3}{4}n+O(1)$)

(update2: now $ r(n)\le (\sqrt{3}-1)n+O(1)$)

The lower bound is obtained by the following construction:

We first split the grid into the central $n/3\times n/3$ square surrounded by four regions as drawn. The red region is filled with $\to$, the green region is filled with $\downarrow$, The blue region is filled with $\gets$, the purple region is filled with $\uparrow$. The central square can be filled with anything. One can prove that every entry is pointed to by $\frac{2}{3}n+O(1)$ other entries.

On the other hand, counting the total number of entries one entry can point to, there are at most $\frac{5}{6}n^3+O(n^2)$ pairs (entry 1, entry 2) such that entry 1 points to entry 2. So, in average, an entry is pointed to by at most $5/6\; n+O(1)$ other entries.

Now, the question is: can the lower bound $2/3$ be raised and $5/6$ the upper bound be made smaller? I believe $2/3$ can be raised a little bit (for example, $0.01$) since the central $n/3\times n/3$ is not filled. But can it be substantially increased?

Any improvement is welcome and appreciated, even minor improvement with $2/3$ is welcome.

Update: a friend of mine gave me an $3/4\; n+O(1)$ upper bound. He considered the square connected the midpoints, where there are $2n$ entries. The entries inside the square point to at most one entry on the square, and the entries outside the square point to at most two. Thus, the number of entry points to the other entries is at most $1/2n^2+2\times 1/2n^2+O(n)=3/2n^2+O(n)$, and since there are $3n$ entries, averagely, one of the entries has at most $3n/4+O(1)$ entries points to it.

Update 2: That friend suggested another way: choose these entries in green

The green line four corners are of length $(\sqrt{3}-1)n/2$ entries. Using the similar argument above we can get $(\sqrt{3}-1)n+O(1)$ upper bound.

The problem is as follows:

Suppose we filled a $n\times n$ square with one of the four arrows $\uparrow$, $\downarrow$, $\gets$, $\to$, like the following

$\begin{array}{|c|c|c|} \hline \downarrow & \downarrow & \gets\\ \hline \to& \to& \uparrow\\ \hline \to& \uparrow& \uparrow\\ \hline \end{array}$

We define entry $A$ (in $i$th column $j$th row) points to entry $B$ (in $k$th column $l$th row) if one of the four happens:

1. $A$ is filled with $\uparrow$ and $j> l$ and $i=k$
2. $A$ is filled with $\downarrow$ and $j< l$ and $i=k$
3. $A$ is filled with $\gets$ and $j= l$ and $i<k$
4. $A$ is filled with $\to$ and $j= l$ and $i>k$

(This is straightforward if you really fill them with arrows...)

For the example above, only the entry in first row, third entry points to the left upper corner. The right bottom corner entry points to the entry on the first row, third column and the entry on the second row, third column.

Let $r(n)$ be the maximum number such that there is a filling method such that every entry is pointed by at least $r(n)$ other entries.

Now we have a bound $\frac{2}{3}n+O(1)\le r(n)\le \frac{5}{6}n+O(1)$  (now $ r(n)\le \frac{3}{4}n+O(1)$)

The lower bound is constructed by the following:

We first split the grid into $3\times 3$ region (we ignore the remainders.) The red region is filled with $\to$, the green region is filled with $\downarrow$, The blue region is filled with $\gets$, the purple region is filled with $\uparrow$. The central square can filled with anything. One can proof that every entry are pointed by $\frac{2}{3}n+O(1)$ other entries.

On the other hand, counting the total number entries one entry can point to, there are at most $\frac{5}{6}n^3+O(n^2)$ (entry 1, entry 2) pairs that the first entry point to the second entry. So, in average, there is an entry pointed by at most $5/6n+O(1)$ other entries.

Now, the question is: can $2/3$ be raised and $5/6$ be smaller? I believe $2/3$ can be raised a little bit (for example, $0.01$) since the central $n/3\times n/3$ is not filled. But can it be substantially increased?

Any improvement is welcome and appreciated, even minor improvement with $2/3$ is welcome.

Update: a friend of mine gave me an $3/4n+O(1)$ upper bound. He considered the square connected the midpoints, where there are $2n$ entries. The entries inside the square points at most one entry on the square, and the entries outside the square points at most two. Thus, the number of entry points to the other entries is at most $1/2n^2+2\times 1/2n^2+O(n)=3/2n^2+O(n)$, and since there are $3n$ entries, averagely, one of the entries has at most $3n/4+O(1)$ entries points to it.

The problem is as follows:

Suppose we filled a $n\times n$ square with one of the four arrows $\uparrow$, $\downarrow$, $\gets$, $\to$, like the following

$\begin{array}{|c|c|c|} \hline \downarrow & \downarrow & \gets\\ \hline \to& \to& \uparrow\\ \hline \to& \uparrow& \uparrow\\ \hline \end{array}$

We define entry $A$ (in $i$th column $j$th row) points to entry $B$ (in $k$th column $l$th row) if one of the four happens:

1. $A$ is filled with $\uparrow$ and $j> l$ and $i=k$
2. $A$ is filled with $\downarrow$ and $j< l$ and $i=k$
3. $A$ is filled with $\gets$ and $j= l$ and $i<k$
4. $A$ is filled with $\to$ and $j= l$ and $i>k$

(This is straightforward if you really fill them with arrows...)

For the example above, only the entry in first row, third entry points to the left upper corner. The right bottom corner entry points to the entry on the first row, third column and the entry on the second row, third column.

Let $r(n)$ be the maximum number such that there is a filling method such that every entry is pointed by at least $r(n)$ other entries.

Now we have a bound $\frac{2}{3}n+O(1)\le r(n)\le \frac{5}{6}n+O(1)$ 

(update: now $ r(n)\le \frac{3}{4}n+O(1)$)

(update2: now $ r(n)\le (\sqrt{3}-1)n+O(1)$)

The lower bound is constructed by the following:

We first split the grid into $3\times 3$ region (we ignore the remainders.) The red region is filled with $\to$, the green region is filled with $\downarrow$, The blue region is filled with $\gets$, the purple region is filled with $\uparrow$. The central square can filled with anything. One can proof that every entry are pointed by $\frac{2}{3}n+O(1)$ other entries.

On the other hand, counting the total number entries one entry can point to, there are at most $\frac{5}{6}n^3+O(n^2)$ (entry 1, entry 2) pairs that the first entry point to the second entry. So, in average, there is an entry pointed by at most $5/6n+O(1)$ other entries.

Now, the question is: can $2/3$ be raised and $5/6$ be smaller? I believe $2/3$ can be raised a little bit (for example, $0.01$) since the central $n/3\times n/3$ is not filled. But can it be substantially increased?

Any improvement is welcome and appreciated, even minor improvement with $2/3$ is welcome.

Update: a friend of mine gave me an $3/4n+O(1)$ upper bound. He considered the square connected the midpoints, where there are $2n$ entries. The entries inside the square points at most one entry on the square, and the entries outside the square points at most two. Thus, the number of entry points to the other entries is at most $1/2n^2+2\times 1/2n^2+O(n)=3/2n^2+O(n)$, and since there are $3n$ entries, averagely, one of the entries has at most $3n/4+O(1)$ entries points to it.

Update 2: That friend suggested another way: choose these entries in green

The green line four corners are of length $(\sqrt{3}-1)n/2$ entries. Using the similar argument above we can get $(\sqrt{3}-1)n+O(1)$ upper bound.