Euro2024-inspired scoring problem

Question

Motivation. The Euro 2024 soccer football championship is in full swing, and the male part of my family are avid watchers. Right now the championship is in the group stage where every group member plays against every other member exactly once. I got the impression that the games in the groups get more attractive over time.

More precisely, suppose we have 3 Teams $A, B, C$, and the "attractivity scores" are $s(A) = 0, s(B) = 1, s(C) = 2$. (A higher score indicates a "more attractive" team.) The attractivity of a game is determined by the sum of the attractivity of the two teams partaking. So $\newcommand{\attr}{\text{attr}}\attr(\{A,B\}) = s(A) + s(B) = 1$, and $\attr(\{A,C\}) = 2$, and finally $\attr(\{A,C\}) = 3$. Because the "game attractivities" $\attr(\cdot)$ are all distinct, it makes it easy to arrange the games so that the games get more and more attractive over time.

Formalization and generalization. For any set $X$, let $[X]^2=\big\{\{x,y\}:x\neq y \in X\big\}$. Let $\newcommand{\N}{\mathbb{N}}\N=\{0,1,\ldots,\}$ and let $s:\N\to\N$ be a function (corresponding to the scoring function from the motivational part of this post). To $s$ we associate a map $\attr_s:[\N]^2\to [\N]$ with $$p\in[\N]^2 \mapsto s\big(\min(p)\big) + s\big(\max(p)\big).$$ We call the map $s:\N\to\N$ good if $\attr_s$ is injective. An example of a good map is $s:\N\to\N$ defined by $n\mapsto 2^n$.

Questions.

1. Is there a good map $s:\N\to\N$ such that $\text{im}(\attr_s) = \N\setminus\{0\}$?

2. Is there a good map $s_0:\N\to\N$ such that for every good map $s:\N\to\N$ and all $n\in\N$ we have $s_0(n) \leq s(n)$?

Answer 1

Q1: No. We can see this by attempting to construct $s$. Without loss of generality we can assume $s$ is strictly increasing.

We must have $s(0)=0$ and $s(1)=1$, otherwise no game has attractivity $1$. At this point the only attractivity is $0+1 = 1$.

We next need a game of attractivity $2$. The only possibility is $s(2)=2$. At this point we have three games of attractivities $1,2,3$.

We next need a game of attractivity $4$. We cannot have $s(3)=3$ (it would break injectivity since $0+3 = 1+2$). We must have $s(3)=4$. At this point we have attractivities $1,2,3,4,5,6$.

We next need a game of attractivity $7$. We cannot have $s(4)=5$ or $s(4)=6$ (would break injectivity), so $s(4)=7$. At this point we have attractivities $1,2,3,4,5,6,7,8,9,11$.

We next need a game of attractivity $10$. We cannot have $s(5)=8$, $9$ or $10$ (each breaks injectivity). And $s(5) \ge 11$ means we fail to make a game of attractivity $10$. No suitable $s$ is possible.

---

Q2: To make the question interesting, let us add the requirement that a good map must be strictly increasing. Otherwise the question becomes moot, because for any $i \in \mathbb{N}$ there is a good map that has $s(i)=0$, for example, $s(i)=0$ and $s(n)=2^n$ for $n \ne i$; so clearly there cannot be a good map $s_0$ fulfilling $s_0(n) \le s(n)$ for every $s$ and $n$.

Even with the added requirement, the answer is no.

Let's say that a $k$-prefix is a strictly increasing function $a : \{1,2,\ldots,k\} \to \mathbb{N}$, and it is good if all pairwise sums $a(i)+a(j)$ (with $i<j$) are distinct. We can write a $k$-prefix as a tuple of $k$ natural numbers.

It is always possible to extend a good $k$-prefix into a good $(k+1)$-prefix by making $a(k+1)$ sufficiently large, because the pairwise sums of the $k$-prefix are a finite set. Let's say such an extension is greedy if $a(k+1)$ is as small as possible.

Starting from any good prefix, we can recursively extend it greedily ad infinitum, obtaining a good map. Starting from the empty prefix $()$ we thus obtain a good map (which is OEIS A010672): $$ u = (0,1,2,4,7,12,20,29,38,\ldots) $$ Starting from the prefix $(0,2)$ we obtain another good map: $$ v = (0,2,3,4,8,13,20,27,41,\ldots) $$ Note that $v(8)=27 < u(8)=29$. Thus $u$ cannot be the $s_0$ being sought.

On the other hand, any good map other than $u$ cannot be $s_0$ either, because $u$ was defined greedily; every element is as small as possible, given the prefix before it. (In more detail, let $s_0$ be a good map such that $s_0 \ne u$. Let $i$ be the smallest index where $s_0(i) \ne u(i)$. Because $u$ is greedy, $u(i)$ is as small as possible for the $(i-1)$-prefix, thus we cannot have $s_0(i) < u(i)$. Thus $s_0(i) > u(i)$, which means $s_0$ does not fulfill the condition $s_0(n) \le s(n)$ for every $s$ and $n$.)

Thus no such $s_0$ exists.