12
$\begingroup$

There are 7 different medals in the Arstotzkan army, which may be awarded multiple times to indicate glory. For any two distinct collections of medals, one is decisively more glorious than the other. However, the bureaucratic rules for determining exactly which of the two is more glorious is unreasonably complicated. All you know is that "more glorious" is a transitive relation, and that earning another medal will always render you more glorious than you were before.

Prove that every (potentially infinite) regiment of Arstotzkan soldiers has a least glorious member.

$\endgroup$
  • 1
    $\begingroup$ For each soldier, is the collection of medals that they have always finite? $\endgroup$ – justhalf Jul 7 at 4:17
  • $\begingroup$ Also, if every soldier has the same collection of medals, then all of them will be part of the least glorious member, right? $\endgroup$ – justhalf Jul 7 at 4:22
  • 2
    $\begingroup$ Indeed, each soldier has a finite number of medals. In the event that two soldiers share the same set of medals, they should be considered equally glorious—or equally least glorious, as the case may be. $\endgroup$ – Feryll Jul 7 at 4:47
  • 5
    $\begingroup$ This follows immediately from Dickson's Lemma $\endgroup$ – Magma Jul 7 at 13:00
  • $\begingroup$ @Magma I see you've found one mathematical theorem that's equivalent to this problem—personally I crafted it from Hilbert's basis theorem as applied to custom monomial orders (see: Grobner basis stuff). $\endgroup$ – Feryll Jul 8 at 15:33
10
$\begingroup$

For there to be no least glorious soldier in a regiment, we need an infinite sequence of less glorious soldiers. Assume for contradiction we have such a sequence $(S_n)_{n \in \mathbb{N}}$.

Number the medal types from 1 to 7, and denote the number of medals of type $k$ a soldier $S$ has as $m_k(S)$. The sequence $(m_1(S_n))_{n \in \mathbb{N}}$ of type-1 medal counts of the $S_n$ soldiers is an infinite sequence of nonnegative integers, and thus must contain an infinite non-decreasing subsequence. Let $(S_n^1)_{n \in \mathbb{N}}$ be a subsequence of $(S_n)_{n \in \mathbb{N}}$ with non-decreasing numbers of type-1 medals.

Similarly, $(S_n^1)_{n \in \mathbb{N}}$ must contain an infinite subsequence $(S_n^2)_{n \in \mathbb{N}}$ with non-decreasing numbers of type-2 medals (and non-decreasing numbers of type-1 medals, as it's a subsequence of $(S_n^1)_{n \in \mathbb{N}}$), and $(S_n^2)_{n \in \mathbb{N}}$ must contain an infinite subsequence $(S_n^3)_{n \in \mathbb{N}}$ with non-decreasing type-3 medals, and so on all the way up to $(S_n^7)_{n \in \mathbb{N}}$, which has non-decreasing numbers of every type of medal.

However, for one soldier to be less glorious than another, the first soldier must have less of at least one medal type than the other. $(S_n^7)_{n \in \mathbb{N}}$ was constructed as a subsequence of a sequence of successively less glorious soldiers, but its soldiers cannot be successively less glorious.

This is a contradiction, so the original regiment cannot have an infinite sequence of less glorious soldiers, and it must thus have a least glorious soldier.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Ahh, nice. This is the proof I was working towards. Nice use of that subsequence. $\endgroup$ – justhalf Jul 7 at 13:14
  • $\begingroup$ My inner Bourbakist is satisfied. Nice. $\endgroup$ – Jeremy Dover Jul 7 at 13:20
4
$\begingroup$

Here is another try using induction on the number of medals. Assume that for $n$ medals and all possible notions of gloriousness there is always a soldier with least glory (which is clear for $n=1$). Now look at the situation with $n+1$ medals. Pick one soldier $x$. Then for each soldier $y$ with less glory than $x$ ($y<x$), there is a medal number $i$ such that $y$ has less medals of type $i$ than $x$ (written $y_i<x_i$), as otherwise $y$ has at least as many medals of each type as $x$ given $y$ at least the same glory as $x$. Define $$ S_i:= \{ y : \ y<x, \ y_i<x_i\}. $$ Now each $S_i$ has a soldier with least glory: For each number $j\in \{0\dots x_i-1\}$ of medals of type $i$, there is (per induction assumption) a soldier of least glory among those with $j$ medals of type $i$: We can define a modified glory-function on these soldiers: it is the original glory applied to a set of $n$ types (not of type $i$) of medals plus $j$ medals of type $i$. This modified glory depends only on the number of types of $n$ medals, and satisfies the assumption of the OP. So we can apply the induction hypothesis.
Of this $x_i$-many there is a soldier of least glory, giving us the soldier of least glory in $S_i$ for each $i=1\dots n+1$. Of these $n+1$ many, there is a soldier of least glory, which is the soldier of least glory of the whole army.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I think your proof suffers from the same flaw as Deusovi's: the assumption that the induction hypothesis applies to a subset of people with a fixed number of one medal, and n other medals. This does not seem obvious to me, except to the extent that the whole thing is "obvious" by well-ordering. $\endgroup$ – Jeremy Dover Jul 7 at 7:34
  • $\begingroup$ @JeremyDover This can be repaired by assuming the induction hypothesis is true for all gloriousness functions according to the OP. (Instead of the induction hypotheses is true for the one given function) $\endgroup$ – daw Jul 7 at 9:07
  • $\begingroup$ I marked the edits to reflect this by italic letters. $\endgroup$ – daw Jul 7 at 9:07
  • $\begingroup$ I think this basically works, though my inner Bourbakist remains unsatisfied. I would change the definition of $S_i$ to use $<=$ instead of $<$. As it stands some of your $S_i$ can be empty. Allowing equality ensures $x$ is in each $S_i$. If $x$ is the least element, your proof may fail due to all $S_i$ being empty. $\endgroup$ – Jeremy Dover Jul 7 at 11:32
2
$\begingroup$

An answer without using induction:

Let's introduce a partial ordering on the set of medal sets. Define that a set A precedes another set B if and only if some (including zero) medals can be added to A to form B. Obviously, the least glorious set in a regiment cannot be preceded by any distinct set of that regiment, so we can pick all soldiers that are not preceded by others, and since this subset of soldiers must be finite, we can select the least glorious one of them which would be the least glorious of the entire regiment.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Hm, one key point: Why must that subset you speak of be finite? As well, you seem to suggest that this subset is initial with respect to precedence; clearly enough one can see this must be the case, since an infinitely descending chain is impossible. $\endgroup$ – Feryll Jul 7 at 6:20
  • 1
    $\begingroup$ That's the part where I'm stuck: how to prove that infinitely descending chain is impossible. $\endgroup$ – justhalf Jul 7 at 12:27
  • $\begingroup$ An infinitely descending chain of precedence (not gloriousness; that's the entire problem!) being impossible is easy: The sum total of medals decreases each time. That's the sense that I meant. $\endgroup$ – Feryll Jul 7 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.