All Guinea pigs move simultaneously at every step?

math90 wrote: All Guinea pigs move simultaneously at every step? Yep

If there exists one of the four directions such that the number of the Guinea pigs facing the direction exceeds $n^2$, then take all the Guinea pigs facing that direction. Otherwise, the number of the Guinea pigs of each direction is exactly $n^2$. Let a Guinea pig be black if its initial point $(x, y)$ satisfies $x+y\equiv 1\mod 2$; otherwise, it is white. If two Guinea pigs with different colors and their directions are perpendicular to each other, they won't move to the same endpoint in the same round or move to the startpoints of each other simultaneously. Let $u, d, l, r$ be the number of black Guinea pigs facing positive y, negative y, negative x, and positive x, respectively. If $u=l=r$, then $d\neq l$, otherwise $2\equiv 2n^2\equiv u+d+l+r\equiv 4u\equiv 0\mod 4$, contradiction. Therefore, there exists $(a, b)\in\{u, d\}\times\{l, r\}$ such that $a\neq b$. Because positive or negative direction of the same axis is equivalent, WLOG let $a=u, b=l$ If $u>l$, then take all black Guinea pigs facing positive y and all white Guinea pigs facing negative x (with number of $u+n^2-l>u+n^2-u=n^2$). If $u<l$, then take all white Guinea pigs facing positive y and all white Guinea pigs facing negative x (with number of $n^2-u+l>n^2-l+l=n^2$). Therefore, Jeff can always succeed.

We can assume WLOG that all Guinea pigs lie on $\mathbb Z/2n\mathbb Z\times\mathbb Z/2n\mathbb Z$. Call a Guinea pig black if its initial point $(i,j)$ satisfies $i+j\equiv 0\pmod{2}$; otherwise, it is white. This is a well-defined definition since $2n$ is even. Observe that two Guinea pigs which initially lie on points with different colors, will always do so. Moreover, two different Guinea pigs with the same direction will never collide. Choose a union of a maximal subset of black Guinea pigs with the same direction, and similarly for white. By what explained above, no two Guinea pigs collide. There are $2n^2$ black points and the same for white, so the total number of Guinea pigs we took is at least $$\left\lceil\frac{2n^2}{4}\right\rceil+\left\lceil\frac{2n^2}{4}\right\rceil=2\left\lceil\frac{n^2}{2}\right\rceil=n^2+1$$where in the last equality we use the fact that $n$ is odd.

math90 wrote: We can assume WLOG that all Guinea pigs lie on $\mathbb Z/2n\mathbb Z\times\mathbb Z/2n\mathbb Z$. Call a Guinea pig black if its initial point $(i,j)$ satisfies $i+j\equiv 0\pmod{2}$; otherwise, it is white. This is a well-defined definition since $2n$ is even. Observe that two Guinea pigs which initially lie on points with different colors, will always do so. Moreover, two different Guinea pigs with the same direction will never collide. Choose a union of a maximal subset of black Guinea pigs with the same direction, and similarly for white. By what explained above, no two Guinea pigs collide. There are $2n^2$ black points and the same for white, so the total number of Guinea pigs we took is at least $$\left\lceil\frac{2n^2}{4}\right\rceil+\left\lceil\frac{2n^2}{4}\right\rceil=2\left\lceil\frac{n^2}{2}\right\rceil=n^2+1$$where in the last equality we use the fact that $n$ is odd. This is flawed: two Guinea pigs on squares with different colors could still collide with each other if, say, they are on the same column with one facing upward and one facing downward. I don't see how one could immediately fix this.

No, I think they skip each other. Maybe there is an additional requirement I don't understand. Edit: Got it. I didn't take in account the requirement that no two ants can exchange positions in a round.

nonamefour0210 wrote: any two Guinea pigs will never move to the same endpoint in the same round, and will never move to the startpoints of each other simultaneously. Prove that Jeff can always succeed wherever the Guinea pigs initially face. The startpoints here means startpoints in that round. For example, the situation that a Guinea pig move from $(0,0)$ to $(0,1)$, while another move from $(0,1)$ to $(0,0)$ in the same round is not valid.

By the way, it can be proven that the number $n^2+1$ is optimal, i.e. if the Guinea pigs face appropriately, Jeff can only keep at most $n^2+1$ of them on the plane to avoid any collision.

The solution can be fixed as follows: Two Guinea pigs which are initially on different colors and are of opposite directions cannot collide. We claim that there exist two directions, maybe the same, which are not opposite of each other, such that if we pick all black Guinea pigs of one direction and all white Guinea pigs of the other direction, then the total number of picked Guinea pigs is at least $n^2+1$. Let $a_1,a_2,a_3,a_4$ be the number of black Guinea pigs which face leftwards, upwards, rightwards and downwards respectively. Similarly define $b_1,b_2,b_3,b_4$ for white Guinea pigs. If for some indices $(i,j)$ with $i-j\not\equiv 2\pmod 4$ the inequality $a_i+b_j\ge n^2+1$ holds, we win, so assume otherwise. Then for all $i$ we have $a_i+b_i\le n^2$. Summing up gives $\sum(a_i+b_i)\le 4n^2$. But $\sum(a_i+b_i)=4n^2$, so equality holds everywhere. Similaraly by using the inequalities $a_i+b_{i+1}\le n^2$ (taking the indices modulo $4$), we obtain $a_i+b_{i+1}=n^2$ for all $i$. Therefore $b_i=b_{i+1}$ for all $i$. Hence $b_1=b_2=b_3=b_4$. Since $b_1+b_2+b_3+b_4=2n^2$ we obtain $b_1=b_2=b_3=b_4=\frac{n^2}{2}$, which is not an integer since $n$ is odd.