The answer is $\frac{(N-1)(3N-1)}{8}.$ Let's seed the players from $(N-1)$ to $0$, with numbers representing skill level (higher = better). Call any surprising match an upset . Barring an upset, every player would win the exact same number of games as their skill rating. Henceforth, we will use skill ratings to refer to players. Now, let's show that the maximal number of upsets possible is $\frac{(N-1)(3N-1)}{8}.$ First of all, to achieve this, for two players $a$ and $b$, let $a$ beat $b$ if $b-a$ mod $N$ is in the set $\{0, 1, \cdots, \frac{N-1}{2}\}.$ For example, $0$ beats $1$, $1$ beats $2$, $\cdots$, $N-1$ beats $0$. This is easily verified to achieve the claimed $\frac{(N-1)(3N-1)}{8}$ upsets and satisfies the condition since every team wins the same number of games ($\frac{N-1}{2}$). Now, we'll show the upper bound, i.e. that $\frac{(N-1)(3N-1)}{8}$ is optimal. Let $d_{N-1}, d_{N-2}, \cdots, d_0$ be the number of games won by $N-1, N-2, \cdots, 0,$ respectively. Let $e_{N-1}, e_{N-2}, \cdots, e_0$ be the number of upsets that $N-1, N-2, \cdots, 0$ is involved in. Lemma. $e_x \le (N-1) - |(N-1) - (x+d_x)|$, for $0 \le x \le N-1.$ Proof. Notice that $x$ can beat at most $d_x$ of the $N-1-x$ people better than him/her, and lose to at most $N-1-d_x$ of the $x$ people worse than him/her. Therefore, his upset total is capped at $$e_x \le \min (N-1-x, d_x) + \min(x, N-1-d_x) = (N-1) - |(N-1) - (x+d_x)|.$$$\blacksquare$ With the lemma, we've that the total number of upsets is $$\frac{e_0 + e_1 + \cdots + e_{N-1}}{2} \le \frac{N(N-1) - \sum_{i=0}^{N-1} |(N-1) - (i+d_i)|}{2}. \qquad (1)$$Since $0+d_0 < 1+d_1 < \cdots < (N-1) + d_{N-1}$ in view of $d_0 \le d_1 \le \cdots \le d_{N-1}$ (by the condition of the problem) and these integers sum to $(N-1)N$, we know that $\sum_{i=0}^{N-1} |(N-1) - (i+d_i)|$ is minimized when $0+d_0, 1+d_1, \cdots, (N-1) + d_{N-1}$ are equal to $\frac{N-1}{2}, \frac{N+1}{2}, \cdots, \frac{3N-3}{2}$ respectively. This gives us that $\sum_{i=0}^{N-1} |(N-1) - (i+d_i)| \ge \frac{N-1}{2} + \frac{N-3}{2} + \cdots + 1 + 0 + 1 + \cdots + \frac{N-1}{2} = 2 (1 + 2 + \cdots + \frac{N-1}{2}) = \frac{(N-1)(N+1)}{4}.$ Plugging this into $(1)$ then gives us that the number of upsets is at most $$\frac{N(N-1) - \frac{(N-1)(N+1)}{4}}{2} = \frac{(N-1)(3N-1)}{8},$$as desired. $\square$

This problem was proposed by Dominic Yeo from United Kingdom.

Let $N=2k+1$. The answer is $\frac{k(3k+1)}{2}$. Let the players in the initial row be $a_1, a_2, \dots, a_N$ and $a_1$ is the "strongest". Let $a_i$ beat $a_{i-1}, \dots , a_{i-k}$ ($a_{-1}=a_N, \dots , a_{-k} = a_{N+1-k}$). Let the number of wins of $a_i$ be $A_i$. The number of the not surprising matches is at least $A_1+(A_2-1)+(A_3-2)+\dots + (A_k-k+1)\ge (A_1+\dots +A_K)-(\frac{k(k-1)}{2})\ge \frac{k}{2k+1}\cdot \frac{(2k+1)2k}{2} - \frac{k(k-1)}{2} =\frac{k(k+1)}{2}$ Therefore the surprising matches are at most $\frac{(2k+1)2k}{2}-\frac{k(k+1)}{2}=\frac{k(3k+1)}{2}$

Interesting problem... Let's suppose players are ranked $1, 2,..., N$ where $N = 2n + 1$. For any player ranked $p \leq n$, player could have beaten at most $p - 1$ player that are ranked better. From this we obtain that top $n$ ranked players could have made at most $\sum_{p=1}^n(p - 1) = \frac{n(n-1)}{2}$ $suprising$ wins. Obviously, average score of $N$ players is $n$, so average score of bottom $n + 1$ players is at most $n$. From there bottom $n + 1$ players could have at most $n(n + 1)$ wins. From this total number of $suprising$ wins are $$\frac{n(n-1)}{2} + n(n+1) = \frac{n(3n + 1)}{2} = \frac{(N - 1)(3N - 1)}{8}$$

Um, I guess the matches where the stronger player looses is called surprising, so the answer is $\binom{N}{2}-\frac{(N-1)(3N-1)}{8}$ ? I think you guys counted the matches which were not surprising.

Let $N$ be an odd number, $N\geq 3$. $N$ tennis players take part in a championship. Before starting the championship, a commission puts the players in a row depending on how good they think the players are. During the championship, every player plays with every other player exactly once, and each match has a winner. A match is called suprising if the winner was rated lower by the commission. At the end of the tournament, players are arranged in a line based on the number of victories they have achieved. In the event of a tie, the commission's initial order is used to decide which player will be higher. It turns out that the final order is exactly the same as the commission's initial order. What is the maximal number of suprising matches that could have happened. Let $N=2n-1$. Order players as $a_1,a_2,a_3,...,a_{2n-1}$ where index shows their row number, the bigger the better. It is well known that for $N$ players there are $\frac{N(N-1)}{2}$ matches. Now, we will focus on player $a_1$. The reason is, all the wins of $a_1$ counts as suprising match and if we optimize its wins, we can maximize suprising matches. Claim 1. $a_1$ at most can win $M=\frac{N-1}{2}$ times. If $a_1$ wins $c$ times, other players must win at least $c$ times. Since if they win less than $a_1$, their row order will change. Therefore they will have at least $cn$ wins.Then $$\frac{N(N-1)}{2} \ge Nc$$ Must be true. Which immediatly gives the thing we want. Claim 2. the $suprising$ matches are maximized when $a_1$'s win matches are maximized. Which is $M$. First of all. note that if $a_1$ wins $M$ times, others must win the exact same amount. If $a_1$ wins less than $M$, since sum of wins must equal to number of matches, other player's wins will increase. For example, if $a_1$ wins $M-1$ times, $a_{N}$ must win $N+1$ times. if $a_1$ wins $M-2$ times, either $a_N$ wins $M+2$ times or $a_{N-1},a_N$ wins $M+1$ times. And second of all, any wins of $a_N$ can't be $suprising$ match. Hence $a_N$'s wins must stuck on $M+1$. Then as wins of $a_1$ decreases, wins of $a_N,a_{N-1},...,a_2$ will increase. Which decreases $suprising$ matches. Hence wins of $a_1$ equals to $M$. Now, we have to choose who wins to against with to maximize $suprising$ matches. For $a_i,i \in [1,\frac{N+1}{2}]$., let them win against $a_j,j \in [i+1,\frac{N-1}{2}+i]$ This makes total of $\frac{(N+1)(N-1)}{4}$ suprising matches. For $a_i, i \in [\frac{N+3}{2},N]$, let them win against the $a_j, j \in [i+1,\frac{N-1}{2}+i]$, but they still left $i-\frac{N+1}{2}$ games to win, we can choose low row order players that losed to them( since we already choose who will win for low order players). This means $a_i$ will have $N-i$ $suprising$ matches. Therefore it will make total of : $$\sum_{\frac{N+3}{2}}^N N-i=\frac{N(N-1)}{2}-\left( \frac{N(N+1)}{2}-\frac{(\frac{N+1}{2}+1)(\frac{N+1}{2})}{2}\right)=\frac{(N-1)(N-3)}{8}$$ Observe that if wins of $a_1 \neq M$, we can't make this construction. adding both the resuls we get $\frac{(N-1)(3N-1)}{8}$ $\blacksquare$ I think my proof for Claim 2 is sketchy, but hey!Got the same answer as others