The Friendship Games has come around again, and Twilight Sparkle has been asked to help organise the upcoming Hoofball Tournament, pitting all manner of creatures with hooves against one another for international glory.
This year, however, owing to a frankly irresponsible error on the part of the Canterlot Tax Office, the Games has an incredibly large budget for the year and Twilight discovers, to her astonishment, that they are allowing even amateur teams to compete this year, partially to promote the unity theme going on, and partially because all that money needs to go somewhere. Even the Cutie Mark Crusaders managed to pull together a team with the intent of competing against grown adults for the cup.
By allowing just anypony and everypony to compete if they can get a team together, Twilight discovers that there are exactly 12,187 teams competing in the tournament this year. After the poor alicorn princess has managed to come around from fainting (by Spike waving a first edition copy of Jeremy Brenthoof's works under her muzzle), she now has to get started organising the matches.
The tournament is a simple knockout style competition, and with so many teams taking part, there's bound to be quite a lot of matches to play and little time to do it.
So, how many matches need to be played (byes do not counts as matches)?
Have one single massive battle royale where only one team remains standing at the end.
All i have figured out is each team plays13or14 matches in order to win the tournament
9210423
If you're trying to map this tournament out on paper, don't. It's so stupidly simple you'll kick yourself.
I doubt its that easy but
12186 matches, as thats how many we need to eliminate
9209814
Man this is harder to predict discord than actually plan a win,
you say 16 floors are done we hit luna's turn so far, meaning we have 9 left, if luna does 3, discord does 4 and then luna 1 and discord wins with 1, so not 3
If luna does 4, discord does 3 and we have the same end
If luna does 1,we have 8 left on discord's turn, im not sure witch is optimal for him so ill trial&error it
D does 1,L does 3,d does 4 and wins
D does 1, L does 1, d does 4 and we have 2 left on us so lose
So luna cant land with 9 on her turn
9211684
Quite the opposite. If Discord were going first, THEN it would be impossible.
Really?
12,186
Just subtract 1
12k186
Inefficient solution below:
One match to determine a winner, then 12 185 go to compete. By the time the last team gets to enter a competition it'll have 12 186 teams, which have taken a row in the table. So this last team will either lose its match or win them all and take the first row!
Thus it's 1 + 12 184 + 12 186 = 2 * 12 186 - 1 = 24 372 - 1 = 24 371 matches!
Maybe more efficient, but incomplete solution below:
Or could they split into 6 093 pairs and have just one match for all? Then the 6 093 winner teams would split into pairs, as would the loser teams? Then yet again? It would thus require n matches to lead it to a tournament of 2^n groups of teams each battling against another. One match splits them into 2 groups (winners of the match and losers thereof), the next will into 4 groups (winners of both, winners of the first, but losers of the second, losers of the first, but winners of the second, then losers of both).
If one could split 12 187 teams into the same amount of groups, one would determine the rows each team would have taken. If only team-vs-team battles are allowed, the number of matches will be log2 12 187 = 13,57.
13 matches split the teams into 2^13 = 1024 * 8 = 8192 groups, each consisting of 12 187 / 8 192 = 1,5 --> 1 team. There still are 12 187 - 8 192 = 3 995 teams left. Hm-m-m...
What would happen after 12 matches? 2^12 = 4096 groups, each 12 187 / 4 096 = 2, 12 187 - 8 192 = 3 995 teams left...
OK, then let's take 8192 (2^13) and 3995 teams and for each have simultaneous battles. 11 matches split each set of the teams into 2048 groups, and 3995 - 2048 = 1947 teams.
10 matches split into 1024 groups, and 1947 - 1024 = 923 teams.
2^9 = 512, 923 - 512 = 411.
2^8 = 256, 411 - 256 = 155.
2^7 = 128, 155 - 128 = 27.
2^4 = 16, 27 - 16 = 11.
2^3 = 8, 11 - 8 = 3.
2 = 2, 3 - 2 = 1.
So Twilight might want to split the teams into groups of: 8192, 2048, 1024, 512, 256, 128, 16, 8, 2 and 1 teams. Each group (except for the 1-teamed one) would have a match, splitting these groups into two. Now, the 1-team group would have to have a match with each of the other teams. After the first match it would have two teams to beat, which would require 2 more matches. As these matches were conducted, the 8-team group would have determined the leadership of each team within. Now the 1-team group would have to battle 8 more teams, if it lost all of the previous matches! As of now 3 matches had been conducted. One more match would determine the leadership within the 16-team group, so, when the 1-team group lost to each of the 8-team group's teams, the loser would have to battle 8 more teams!..
So, were there only 12 186 teams, it would be like this:
8192, 2048, 1024, 512, 256, 128, 16, 8, 2 teams;
Match 1: 2*4096, 2*1024, 2*512, 2*256, 2*128, 2*64, 2*8, 2*4, 2*1;
Match 2: 4*2048, 4*512, 4*256, 4*128, 4*64, 4*32, 4*4, 4*2, 2*1;
Match 3: 8*1024, 8*256, 8*128, 8*64, 8*32, 8*16, 8*2, 8*1 + 2*1, the last ten teams might have 8 more matches (or even 9);
Match 4: 16*512, 16*128, 16*64, 16*32, 16*16, 16*8, 16*1 + 8*1 + 2*1, the last 26 team would have... well, I am lost.
Any way, there've got to be at least 13 matches. Then... Who knows, what will happen?..