CantonMathGuy wrote: Then, for every line $\ell$ in the plane which is horizontal, vertical, or has slope $+1$ or $-1$, she tells Bob the number of points of $S$ that lie on $\ell$. Does that means this: Call a line good if it is horizontal, vertical, or has slope $+1$ or $-1$, and if Bob picks a good line $\ell$ and asks Alice, then Alice tells Bob how many points of $S$ are inside $\ell$ ? (And Bob can keep doing this as long as he wants)

@above. I think so.

Clearly Bob can compute the number $N$ of points. The main claim is that: Claim: Fix $m$ and $n$ as in the problem statement. Among all sets $T \subseteq {\mathbb Z}^2$ with $N$ points, the set $S$ is the unique one which maximizes the value of \[ F(T):=\sum_{(x,y)\in T} (x^2+y^2)(m+n-(x^2+y^2)). \] Proof. Indeed, the different points in $T$ do not interact in this sum, so we simply want the points $(x,y)$ with $x^2+y^2$ as close as possible to $\frac{m+n}{2}$ which is exactly what $S$ does. $\blacksquare$ As a result of this observation, it suffices to show that Bob has enough information to compute $F(S)$ from the data given. (There is no issue with fixing $m$ and $n$, since Bob can find an upper bound on the magnitude of the points and then check all pairs $(m,n)$ smaller than that.) The idea is that he knows the full distribution of each of $X$, $Y$, $X+Y$, $X-Y$ and hence can compute sums over $T$ of any power of a single one of those linear functions. By taking linear combinations we can hence compute $F(S)$. Let us make the relations explicit. For ease of exposition we take $Z=(X,Y)$ to be a uniformly random point from the set $S$. The information is precisely the individual distributions of $X$, $Y$, $X+Y$, and $X-Y$. Now compute \begin{align*} \frac{F(S)}{N} &= \mathbb E\left[ (m+n)(X^2+Y^2) - (X^2+Y^2)^2 \right] \\ &= (m+n) \left( \mathbb E[X^2] + \mathbb E[Y^2] \right) - \mathbb E[X^4] - \mathbb E[Y^4] - 2 \mathbb E[X^2 Y^2]. \end{align*}On the other hand, \[ \mathbb E[X^2Y^2] = \frac{\mathbb E[(X+Y)^4] + \mathbb E[(X-Y)^4] - 2\mathbb E[X^4] - 2\mathbb E[Y^4]}{12}. \]Thus we have written $F(S)$ in terms of the distributions of $X$, $Y$, $X-Y$, $X+Y$ which completes the proof. Remark: [Mark Sellke] This proof would have worked just as well if we allowed arbitrary $[0,1]$-valued weights on points with finitely many weights non-zero. There is an obvious continuum generalization one can make concerning the indicator function for an annulus. It's a simpler but fun problem to characterize when just the vertical/horizontal directions determine the distribution. An obstruction to purely combinatorial arguments is that if you take an octagon with points $(\pm a,\pm b)$ and $(\pm b,\pm a)$ then the two ways to pick every other point (going around clockwise) are indistinguishable by Bob. This at least shows that Bob's task is far from possible in general, and hints at proving an inequality. A related and more standard fact (among a certain type of person) is that given a probability distribution $\mu$ on $\mathbb R^n$, if I tell you the distribution of all $1$-dimensional projections of $\mu$, that determines $\mu$ uniquely. This works because this information gives me the Fourier transform $\hat{\mu}$, and Fourier transforms are injective. For the continuum version of this problem, this connection gives a much larger family of counterexamples to any proposed extension to arbitrary non-annular shapes. Indeed, take a fast-decaying smooth function $f \colon {\mathbb R}^2 \to {\mathbb R}$ which vanishes on the four lines \[ x=0, \; y=0, \; x+y=0, \; x-y=0.\]Then the Fourier transform $\hat f$ will have mean $0$ on each line $\ell$ as in the problem statement. Hence the positive and negative parts of $\hat f$ will not be distinguishable by Bob.

v_Enhance wrote: Clearly Bob can compute the number $N$ of points. How can he find the number of points? I mean, yes, they are finitely many but by trying, let's say, a lot of horizontal lines, how can he be sure he has been through every point?

TwoTimes3TimesSeven wrote: How can he find the number of points? I mean, yes, they are finitely many but by trying, let's say, a lot of horizontal lines, how can he be sure he has been through every point? Note that in the phrasing of the question, one sees this is not a turn-based game; Alice tells Bob the data of all (infinitely many) lines at once.

v_Enhance wrote: TwoTimes3TimesSeven wrote: How can he find the number of points? I mean, yes, they are finitely many but by trying, let's say, a lot of horizontal lines, how can he be sure he has been through every point? Note that in the phrasing of the question, one sees this is not a turn-based game; Alice tells Bob the data of all (infinitely many) lines at once. :oooo So he basically is told how many points there are on every line?

Yes! $\quad$

@v_Enhance very elegant solution!

v_Enhance wrote: Now compute \begin{align*} \frac{F(S)}{N} &= \mathbb E\left[ (m+n)(X^2+Y^2) - (X^2+Y^2)^2 \right] \\ &= (m+n) \left( \mathbb E[X^2] + \mathbb E[Y^2] \right) - \mathbb E[X^4] - \mathbb E[Y^4] - 2 \mathbb E[X^2 Y^2]. \end{align*}On the other hand, \[ \mathbb E[X^2Y^2] = \frac{\mathbb E[(X+Y)^4] + \mathbb E[(X-Y)^4] - 2\mathbb E[X^4] - 2\mathbb E[Y^4]}{12}. \]Thus we have written $F(S)$ in terms of the distributions of $X$, $Y$, $X-Y$, $X+Y$ which completes the proof. I wanna figure out what does the $\mathbb{E}[X]$ mean.. Does it stand for the expectation?

A beautiful solution

@photaesthesia. Yes,it is.

How should I start learning the method of expectation?

I thought I'd share how I solved this problem in contest. Mathematically it's the same as the official solution but I frame it as an invariant rather than expected value. The perpendicular axis theorem about angular momentum, which might be in a high school physics course, also provides some motivation. (I think some people got partial credit on this problem for thinking about angular momentum!) Say two distinct sets of lattice points are indistinguishable if they give the same information to Bob, i.e. for any line in the four directions, both sets contain an equal number of points. Note that Bob can bound the set of points and brute-force all possibilities, so we need to show that no set is indistinguishable from $S$. For a set of lattice points $A$, let \[f(A)=\sum_{(x, y)\in A}(x^2+y^2-m)(x^2+y^2-n).\]Claim. If $A$ and $B$ are indistinguishable, $f(A)=f(B)$. Proof. The condition that $A$ and $B$ are indistinguishable implies the following equalities of multisets: \begin{align*} \{x\mid (x, y)\in A\} &= \{x\mid (x, y)\in B\} \\ \{y\mid (x, y)\in A\} &= \{y\mid (x, y)\in B\} \\ \{x+y\mid (x, y)\in A\} &= \{x+y\mid (x, y)\in B\} \\ \{x-y\mid (x, y)\in A\} &= \{x-y\mid (x, y)\in B\} \end{align*}We have \begin{align*} f(A) &=\sum_{(x, y)\in A}[(x^2+y^2)^2-(m+n)(x^2+y^2)+mn] \\ &=\sum_{(x, y)\in A}\big[\tfrac{1}{6}(x+y)^4+\tfrac{1}{6}(x-y)^4+\tfrac{2}{3}x^4+\tfrac{2}{3}y^4-(m+n)(x^2+y^2)+mn\big]. \end{align*}Then in the above expression for $f(A)$, we can break it up into $7$ different sums in the obvious way and convert them all to sums over $B$ because they are summing over the same multiset. Therefore $f(A)=f(B)$. $\square$ Now suppose $S$ is indistinguishable from a set $T$. Cancel out the common points between $S$ and $T$. Then $S$ only contains points in the annulus $m\leq x^2+y^2\leq n$ and $T$ only contains points which are not in that annulus. (Since $S$ and $T$ have equal cardinality and are not the same set, $T$ must contain at least one point outside the annulus.) However, it is clear from the definition of $f$ that $f(S)\leq 0$ and $f(T) > 0$, contradicting the claim.

One liner: $(n-x^2-y^2)(x^2+y^2-m) = -nm + (n+m)(x^2+y^2) - \left(x^4 + y^4 + \frac{(x+y)^4+(x-y)^4 - 2x^4 - 2y^4}{6} \right)$

After 2023 USEMO #5, missing out on this one is a sin! Fix positive integers $m$ and $n$. Let \[ \sigma(S) := \sum_{(x, y) \in S} (x^2+y^2-m)(x^2+y^2-n). \]Note that $\sigma(S)$ has a minima at \[ S_0 = \{(x, y) \in \mathbb{Z}^2 \mid m \le x^2 + y^2 \le n\}. \]We rewrite $(x^2+y^2-m)(x^2+y^2-n)$ as \[ (x^2+y^2-m)(x^2+y^2-n) = \left(\frac{2}{3} \cdot (x^4+y^4) + \frac{1}{6} \cdot ((x+y)^4+(x-y)^4)\right) - (x^2+y^2)(m+n) + mn. \]Observe that Bob knows the value of \[ \sum_{(x, y) \in S} C \cdot f(x, y)^k \]where $f(x, y) \in \{x, y, x+y, x-y\}$. Using the rewritten form computed earlier, Bob knows the value of $(x^2+y^2-m)(x^2+y^2-n)$, and thus the value of $\sigma(S)$ as well. Claim: For any set $A$ of lattice points, the number of points on each line do not always match for $A$ and $S_0$. Proof. Assume otherwise. Note that \[ \sigma(A) = \sigma(A \setminus (S_0 \cap A)) + \sigma(S_0 \cap A) > \sigma(A \setminus (S_0 \cap A)) + \sigma(S_0). \]Since all points in $A \setminus (S_0 \cap A)$ are outside of $S_0$, its $\sigma$ must be positive, so $\sigma(A) > \sigma(S_0)$. Per our previous discussion, $\sigma(A) = \sigma(S_0)$, so we have a contradiction. By the claim, $S_0$ is the unique point set at which $\sigma$ is minimized, which means that Bob can win.

Same solution as everyone else, after using a hint to consider minimizing / maximizing $S$. Going to note that an alternative to fixing the number of points is instead to consider $f(x,y) = (x^2 + y^2 - (m - \varepsilon))(x^2 + y^2 - (n + \varepsilon))$.

Let the points have coordinates $(x_i, y_i)$ for $0\le i\le N$. Because Bob knows the number of times each value occurs in $(x_i)$ and $(y_i)$, he can find $\sum_{i=0}^N x_i^4+y_i^4$. Because he knows the number of times each value occurs in $(x_i+y_i)$ and $(x_i-y_i)$, he can find $\sum_{i=0}^N (x_i+y_i)^4+(x_i-y_i)^4 = \sum_{i=0}^N 2x_i^4 + 2y_i^4 + 12x_i^2y_i^2$. So, Bob can find $\sum_{i=0}^N x_i^2y_i^2$. By the rearrangement inequality, Alice's configuration is the only way to match the terms of $x_i^2$ and $y_i^2$ to get the minimum value of $\sum_{i=0}^N x_i^2y_i^2$. So, Bob knows how $x_i^2$'s and $y_i^2$'s are matched, so he knows all of the values of $x_i^2+y_i^2$, which uniquely determines $S$.