Last week I rather unexpectedly was waylaid by a math problem, which I spent 5 days working on to the exclusion of everything else — eating, sleeping, studying chess,… A college friend of mine sent me the following question, which he discovered 25 years ago when he was in grad school and was not able to solve. Here is the problem:
There are an even number of players in a chess club, and they are going to split at random into two teams who will play against each other. The rules of the competition are supposed to be that the top player on team 1 plays against the top player on team 2, the second player on team 1 plays against the second player on team 2, etc. However, one of the coaches decides to cheat and rearrange the order of players on his team. Is there a strategy that will give his team a higher expected win total than it would have by following the rules? If so, what is the best strategy?
[Some clarifications if you actually want to work on the problem yourself: For simplicity, assume that all the players have different strengths, and that the stronger player will always beat the weaker player. You could try to solve the problem using the actual Elo model, but that would make it much harder, and it’s already hard enough as it is. Also, note that the cheating coach has to decide on his players’ seeding order independent of who is on the teams. So, for example, if he decides to play them in the order 3-1-5-2-4, he has to stick with that order no matter who the players on the other team are. Or to put it in a different way, he has perfect information about the strength of the players on his team, but no information about the strength of the players on the other team. Except he knows the other coach will rank them honestly.]
For those who don’t want to spend 5 days thinking about it, I’ll give you some partial answers. Yes, the cheating coach can do better. For example, with 4 players on the team he should play them in the order 4-1-2-3. The intuitive idea behind this is that the match 4 (on his team) versus 1′ (on the other team) is almost a guaranteed loss, but the other three matches (1 versus 2′, 2 versus 3′, and 3 versus 4′) have fairly high probabilities of being won by the cheating team. When you crunch the numbers, you’ll find that the cheating team wins, on average, 164/70 or 2.34 games with this strategy, versus (of course) 2 games if they don’t cheat.
For a mathematician, of course, the fascinating question is: Does this work for all values of N? (Where N is the number of players on each team.) Using a computer, my friend worked out the optimal strategies all the way up to N=13 (which involves some really gigantic numbers). He conjectures that the optimal strategy is always to “throw” a small number of games (say, x games) by playing your weakest player against the other team’s strongest, your second weakest against the second strongest, etc. Then from the x+1-st position on, you put your players in the normal, uncheating order. For example, if there are 8 players on the team, the best cheating strategy is to play them in the order 8-7-1-2-3-4-5-6. In other words, you “throw” the top 2 games for a pretty good shot at winning most of the other 6.
However, my friend wasn’t able to prove that the optimal strategy has this form, and after 5 days of working on the problem I couldn’t prove it either. Hey, he’s had 25 years to think about it, and I’ve only had 5 days! Also, even if the optimal strategy is of this form, we still don’t know the optimal choice for x, the number of games to “throw.”
If any of you have ideas or even proofs, let me know!
By the way, it was really interesting to immerse myself totally in a math problem. I hadn’t done it to this extent for years — basically since I changed careers and became a writer. It reminded me of what is so exciting about doing mathematics. It’s a lot like reading a novel. If you’re working on a hard enough problem, it will constantly surprise you. You never know what’s coming next, a breakthrough or a setback.
It also made me realize (which is probably obvious) that chess is sort of a substitute for math for me, now that I no longer do mathematical research as a career. However, chess is really not a completely adequate replacement for math. The reason is that the “problems” you have to solve in chess simply do not have the depth of math problems. A really good chess position can keep you discovering new things for hours — but not for days, weeks, months, or even years the way a good math problem can.
I realize that I am risking the wrath of my readers by saying this! However, I want to emphasize that by no means am I saying that chess is “inferior” to math. It’s just different; similar in many respects, but ultimately different, and the kind of satisfaction you get from it is different.
