[unreality]

You played Three Games of Zarball and had to win two in a row... you made the right choices (but unfortunately lost).

Your second chance for freedom came with the Five Games of Zarball, in which you had to win at least one of three combinations. Again, you lost in a mistake up against the King.

However you won your freedom, and deserved it, in the intense Royal Zarball Tournament, where you made your way to victory.

Now you have taken the King's offer as the Supreme Dignifiably Appointed Royal Zarball Trainer of Excellence. and figured out the probability of hats being returned to the proper heads in The Royal Zarball Spectators crisis.

You are still the Supreme Dignifiably Appointed Royal Zarball Trainer of Excellence, and so the 1-on-1 game of speed, skill, strength and stamina is your job... now you are helping arrange the Village Zarball Tournament- but so many people want to play in the tournament, and with each new player, it's less and less likely you are going to have a perfect power of two number of players. So you cannot have a perfectly even tournament, so you've set up a system of byes.

There will be tryouts in which a villager's basic skill at the game is determined and seeded, so that the tournament can be arranged fairly, and the players that have more skill than the others in their round are given a "bye" to the next round- in other words, they get to skip this round without playing anybody.

(1 - Warmup Problem)

179 villagers showed up for the zarball tournament... what is the least number of total matches needed to find 1 winner?

Hint: there is an easy way to solve this and a harder way... the riddle is finding the easy way, though the hard way works too ;D

178 out of the 179 villagers must be eliminated in the tournament, so there must be 178 total matches

The easiest way to solve the hard way is to bye a single person when you have an odd number. So:

Have one person bye in the first round, leaving 178/2 = 89 games in the first round leaving 90 players in the game. 90/2 = 45 players, without byes. 89+45=134 games so far. Now you have 45 players. Bye one person and then have 22 matches to turn 44 into 22, with the byed person is 23 more players. 134+22=156 games so far. Bye one of the 23 to get 22 people playing against each other in 11 matches, so 11 players left, +1 byed person to 12. 156+11=167 matches so far. With 12 players you can play 6 games to get 6 players and then 3 games to get 3 players, that's a total of 9 more games to get the final three. 167+9=176. You have 3 more people, so bye one person, have the remaining two play one match (176+1=177 total matches so far), and now you are left with 2 people, who can determine a winner with one more match. 177+1 = 178 matches in the tournament.

It would be at this point that you think "hmmm, 178 matches to eliminate 178 players out of the 179 to get one winner... DUH!" and then smack yourself ;D lol. I told you there was an easier way

Don't post solutions to problem #1 in your post, as the answers are right here, just check your answers ;D unless you have a totally different solution of course, or want to discuss the answers. Now onto a harder problem:

(2)

The way that the tournament worked, with "byes" based on skill (not always bying only 1 person if there was an odd number, sometimes 3, sometimes 5), it ended up with a Final Five. Your friend, Perry, is in the Final Five, and these are the Final Five and Perry's chances of beating each of them:

Perry

Sanders 1/2

Dave 3/4

Xavier 1/3

Ella 7/8

Assume that chances of beating someone are relative and stand when other people are facing each other. For example, Perry has a 3/4 chance to beat Dave and a 1/3 chance to beat Xavier. Thus Xavier is twice as good as Perry (1/3 = 1:2) and Perry is three times as good as Dave (3/4 = 3:1) so Xavier is 6 times better than Dave, thus Xavier has a 6:1 or 6/7 chance to beat Dave.

Remember, you are the Supreme Dignifiably Appointed Royal Zarball Trainer of Excellence, so it's up to you to set up the system of byes and brackets and such. Each round you may have to end up rearranging the entire brackets to suit the tournament right.

So, anyway, it's down to these 5 people. You can arrange it any way you like using brackets and byes.

How can you make it fair so that each person has an equal likelihood OR AS CLOSE AS POSSIBLE to winning?

(3)

Problem 3 is like Problem 2 in every way except the objective. Now you want to arrange the brackets to give your friend Perry the highest possible chance of winning. In this problem, there can only be two byes (for example: 5, bye 1, 4/2=2, +1 = 3, bye 1, 2/2=1, +1 = 2, 2/2 = 1 winner) and the same person cannot be byed twice.

[unreality]

No takers?

[EventHorizon]

For part 2, What function are you using for "as close as possible"?

Difference between high and low probabilities? Ratio of high and low? mean square error? Greatest deviation from average? Most entropy? You are dealing with a probability mass function after all.

It doesn't seem to me to have a solution where all are equal.....but I could be wrong.

Here's a stab at part 3.

round 1:

Perry vs. Ella

Xavier vs. Sanders

Dave gets a bye

round 2:

Winner of Perry vs. Ella gets a bye

Winner of Xavier and Sanders vs. Dave

Final Round:

Remaining 2 zarballers.

((P vs E) vs ((X vs S) vs D))

I didn't run any numbers....but this looks like it may be the best you can get with only 2 byes.

If there weren't a limit on byes, then my approach would be (((X vs S) vs D ) vs E) vs P) which essentially gives the better players more chances to lose before a final match with Perry.

[Guest]

theres an even easyer way to do this, put them all in one ring and have them maush pit it, making one battle

[Guest]

I got the strength table as--

It is clear that X>P=S>D>E

For Part 2

I dont think there is any equall chance...becoz, If Xavier had to play against all the opponents to be champion, then his chance of winning is 0.3555 which is still better than Ella's best game winning probability against Dave which is 0.3.....So, equal chance is not possible...

Nearest chance may be....With Rule twist

[Round 1]Perry VS Xavier, Rest 3 are BYE

If Perry wins...

[Round 2] Sanders VS Dave, Perry and Ella are BYE [as I am the supreme authority, I can make two Byes]

If Xavier wins...

[Round 2] Sanders VS Xavier, Dave and Ella are BYE [as I am the supreme authority, I can make two Byes]

[Round 3] Ella is BYE, winner VS other_bye(Dave/Perry) of round 2.

[Round 4] Ella VS winner_round3

#Without Rule twist

[Round 1]Perry VS Xavier, Rest 3 are BYE

If Perry wins...

[Round 2] Sanders VS Dave, Perry VS Ella

If Xavier wins...

[Round 2] Sanders VS Xavier, Dave VS Ella

[Round 3] Winners of round 2

For Part 3

With Rule twist

Take Perry to the final by BYEing, then he has the minimum probability of winning 1/3 and maximum 7/8.

Without Rule twist

[Round 1] Sanders VS Xavier . Perry , Ella and Dave BYE

[Round 2] winner R1 VS Dave. Perry VS Ella

[Round 3] Winners of Round 2

[EventHorizon]

The closest in probability happens when the bracket is ((((S vs X) vs P) vs D) vs E)

p(P) = .255208

p(S) = .109375

P(D) = .141667

P(X) = .355555

P(E) = .138194

This tournament bracket happened to win "as close to equal" using every metric I stated previously (and a couple I didn't...).

Using the rules as stated, the bracket (((S vs X) vs D) vs (P vs E)) will give Perry a probability of winning approximately equal to .393229.

This is the guess I initially ventured. Notice that the rules state that nobody can bye twice consecutively.

If you allow Perry to bye twice consecutively, then (P vs ((S vs X) vs (D vs E))) is the best with a probability of about .44316.

If you allow any number of byes with any amount being consecutive, the bracket (P vs (E vs (D vs (S vs X)))) is the best for Perry with a probability of about .488455. I also guessed this in my previous reply.

I coded this up....and if anyone is supremely interested I could post the code.

[Guest]

I coded this up....and if anyone is supremely interested I could post the code.

What language?

[EventHorizon]

What language?

c++, using visual studio .net 2003

I wrote it to output a comma separated value file, and then used excel to help interpret it.

Edited March 18, 2008 by EventHorizon

[Guest]

c++, using visual studio .net 2003

I wrote it to output a comma separated value file, and then used excel to help interpret it.

Sure, I only have command line, not GUI though. But it should be able to be extracted to command line easily, unless you made a super fancy GUI

[EventHorizon]

Sure, I only have command line, not GUI though. But it should be able to be extracted to command line easily, unless you made a super fancy GUI

I don't make too many GUIs. I wrote this to be commandline. It is most definitely a bit cryptic...I could explain certain parts if you want.

To interpret the match-ups....you look at the remaining players and count from left to right (starts with P, S, D, X, E). The winner of the match is placed at the position of the player in the match furthest left.

So lets say the line was 1vs2, 0vs1, 1vs2, 0vs1. This means the bracket would be as follows

1vs2 -> S vs D

remaining = P, (S vs D), X, E

0vs1 -> P vs (S vs D)

remaining = (P vs (S vs D)), X, E

1vs2 -> X vs E

remaining = (P vs (S vs D)), (X vs E)

Ovs1 -> ((P vs (S vs D)) vs (X vs E))

I didn't write it to figure out the number of byes needed....I just sorted based on the metric then evaluated them until I found a valid one.

zarball.zip

[unreality]

To clarify: by "AS CLOSE AS POSSIBLE" I mean where each person is as close as possible to 0.2 chances of winning. If you want to get specific, where the total (absolute value) deviation of each person's chances from 0.2 is as close as possible to 0

[EventHorizon]

To clarify: by "AS CLOSE AS POSSIBLE" I mean where each person is as close as possible to 0.2 chances of winning. If you want to get specific, where the total (absolute value) deviation of each person's chances from 0.2 is as close as possible to 0

Using the metric "the sum over all players of the absolute value of the difference between the players probability and .2", the answer I gave previously still minimizes this. (of course, S and P are interchangeable in the answer, but I chose the one that favors Perry)