2
$\begingroup$

I have a few questions about monotone finite sequences. My motivating problem is the following:

Sixteen players participated in a round-robin tennis tournament. Each of them won a different number of games. How many games did the player finishing sixth win?

I struggled with this problem until I realized that there's only one way to order the corresponding finite sequence (the answer ended up being 10). Is there a way to approach this problem that doesn't require listing out the entire sequence and experimenting until you get to one that adds up to ${16 \choose 2}=120$, or at very least is there a way of knowing whether the sequence is forced like the question above was? Furthermore, do you guys know of any good resources for information about monotone finite sequences?

$\endgroup$
  • $\begingroup$ I'm not sure I understood the question. Are you interested in counting strictly monotone finite sequences $x_1 < x_2 < \ldots < x_n$, subject to certain bounds $x_1 \geq A, x_n \leq B$, $x_1 + \ldots + x_n = C$? In your proposed problem, $n$ would be $16$, $A = 0, B = 15, C = 240$. $\endgroup$ – Pedro M. Mar 28 '13 at 17:12
  • $\begingroup$ Yes, that's it. It wasn't even clear to me that $B=15$ until I found the sequence. What I'd like to know is a way, if possible, to gain more information about the sequence before I go into testing cases, because it doesn't seem like it would be practical just to test cases generally. $\endgroup$ – Charles Mar 28 '13 at 21:49
  • $\begingroup$ The only thing I recall that's vaguely related to the problem is partitions of a certain number. If $A = 1$, we are essentially counting the number of partitions of $C$ into distinct parts, each one less than or equal to $B$. en.wikipedia.org/wiki/… $\endgroup$ – Pedro M. Mar 29 '13 at 12:56
  • $\begingroup$ I worried that that would be the case. Math's like that sometimes. Thank you for the link and your time. $\endgroup$ – Charles Mar 29 '13 at 15:22
1
$\begingroup$

There are $16$ possible winning number for each player i.e. $0,1,\dots,15$. And the number for each player are all different. So it must be: the one in the first place has $15$ wins, and followed by $14$ wins, etc.

$\endgroup$
  • $\begingroup$ Well, I agree, but could you just see that the only way it'll sum to 120 is if the sequence is like that? I couldn't so it took me a long time to figure it out. I had resort to testing cases, and the answer came from there. My question is about method. $\endgroup$ – Charles Mar 28 '13 at 0:32

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.