Back

Math and Logic

Is There a Simpler Way?

Some problems become much simpler if we look at them a different way. Let's look at a single-elimination tournament with 3232 teams. If we want to find out how many games there will be in the tournament, we could begin by thinking through the whole thing.

All the teams play, the winners advance, and this repeats until only one team is left.

Since there are 3232 teams, we must have 1616 games in the first round, 88 in the second, 44 in the third, then 2,2, and then 11 final game. Adding all of these up, we get 16+8+4+2+1=3116+8+4+2+1=31. So, it takes 3131 games to finish a single-elimination tournament with 3232 teams.

But wait… we could have done this differently. Our reasoning could have been as simple as this:

There must be 3131 games so that every team except the tournament winner can lose exactly once.

No further calculation needed.

Here are the relevant facts used in this analysis:

  • Each game produces exactly one winner and one loser.
  • Every team — except the tournament winner — has to lose exactly once.
  • 3131 teams get eliminated.

Therefore, there must be 3131 games so that every team but the tournament winner can lose exactly once.

The problem below is extremely tedious to calculate step by step. However, if you can come up with a way to think about it differently, it will unravel in much the same way as the tournament problem above.

Today's Challenge

Compute

210002999299820.\large 2^{1000}-2^{999}-2^{998} - \cdots -2^{0} .

×

Problem Loading...

Note Loading...

Set Loading...