What's new
Fantasy Football - Footballguys Forums

Welcome to Our Forums. Once you've registered and logged in, you're primed to talk football, among other topics, with the sharpest and most experienced fantasy players on the internet.

Math Puzzles (from FiveThirtyEight - new puzzle every Friday) (1 Viewer)

OK, here are a few trial results. Anyone care to verify they look valid?

Candidate A prefers [A, C, B, E, D]Candidate B prefers [B, A, E, D, C]Candidate C prefers [C, A, B, D, E]Candidate D prefers [D, E, B, C, A]Candidate E prefers [E, A, D, B, C]Round 4: [A, B, C, D] vs EPossible winners: [E, A, B]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1: [A, B]Round 1 results: [A]Overall winner is A-----------------------------Candidate A prefers [A, B, E, C, D]Candidate B prefers [B, C, E, D, A]Candidate C prefers [C, A, B, E, D]Candidate D prefers [D, B, C, E, A]Candidate E prefers [E, D, B, A, C]Round 4: [A, B, C, D] vs EPossible winners: [E, B, C]Round 3 irrelevant; D cannot winRound 2: vs CRound 1 irrelevantOverall winner is B-----------------------------Candidate A prefers [A, D, B, E, C]Candidate B prefers [B, A, D, E, C]Candidate C prefers [C, D, E, B, A]Candidate D prefers [D, A, B, E, C]Candidate E prefers [E, B, C, D, A]Round 4: [A, B, C, D] vs EPossible winners: [D, E, A, B]Round 3: [A, B] vs DRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is D-----------------------------If my algorithm is accurate, the results from 10,000 trials indicate it's good to be E:

Code: 
Wins for A: 1828 (18.28%)Wins for B: 1771 (17.71%)Wins for C: 1832 (18.32%)Wins for D: 1912 (19.12%)Wins for E: 2657 (26.57%)
 
Last edited by a moderator:
heckmanm said:
OK, here are a few trial results. Anyone care to verify they look valid?

...

If my algorithm is accurate, the results from 10,000 trials indicate it's good to be E:
Click to expand...
I agree with the results of the three trials you posted, but disagree with your overall results. Not sure exactly where our methods diverge. It seems like from the trials you posted, the only way E can win is if he would beat everyone in the final round. Otherwise some other candidate will filter his way down to be the winner. So how do you come up with E winning a relative majority of the time?

 
Ignoratio Elenchi said:
heckmanm said:
OK, here are a few trial results. Anyone care to verify they look valid?

...

If my algorithm is accurate, the results from 10,000 trials indicate it's good to be E:
Click to expand...
I agree with the results of the three trials you posted, but disagree with your overall results. Not sure exactly where our methods diverge. It seems like from the trials you posted, the only way E can win is if he would beat everyone in the final round. Otherwise some other candidate will filter his way down to be the winner. So how do you come up with E winning a relative majority of the time?
Click to expand...
I can provide a larger set of results (unfortunately google docs is blocked at work), but I'll try to summarize my algorithm. In general, the principle is that if a candidate cannot win, he will vote for his most preferred competitor who can.

  • Round 4: Run each candidate against E, generating a list of possible winners. If that list has only 1 entry, it must be E, and E is the overall winner; otherwise, continue.
  • Round 3: If D can win round 4*, run any of (A, B, C) who could also win against E, against D, generating a list of possible winners. If the list has one entry** then run him against E to get the overall winner. Otherwise, continue.
  • Round 2: If C can win round 3*, run any of (A, B) who could also win against D, against C, generating a list of possible winners. If the list has one entry** then run him against D, and the winner against E to get the overall winner. Otherwise, continue
  • Round 1: Run A against B, and the winner against C, then the winner of that against D, and the winner of that against E to get the overall winner.
*For round 3, if D cannot win, then there is no point in running anyone against him, because anyone who doesn't want E to win will vote for A/B/C vs D, and a vote for D is a vote for E. The same logic applies for C in round 2.

**For any round, if the result set contains only 1 member, then the prior voting rounds are irrelevant, as the field will collapse to that one candidate.

 
50 trials

Code: 
Candidate A prefers [A, B, D, E, C]Candidate B prefers [B, A, E, C, D]Candidate C prefers [C, D, E, A, B]Candidate D prefers [D, E, B, A, C]Candidate E prefers [E, D, A, C, B]Round 4: [A, B, C, D] vs EPossible winners: [D, E]Round 3: []  vs DRound 2 irrelevant; C cannot winRound 1: A vs BRound 1 results: [A]Overall winner is D-----------------------------Candidate A prefers [A, C, B, D, E]Candidate B prefers [B, E, C, D, A]Candidate C prefers [C, D, E, A, B]Candidate D prefers [D, B, C, A, E]Candidate E prefers [E, B, A, C, D]Round 4: [A, B, C, D] vs EPossible winners: [D, E, B, C]Round 3: [B, C]  vs DRound 2: [B] vs CRound 1 irrelevantOverall winner is B-----------------------------Candidate A prefers [A, B, D, E, C]Candidate B prefers [B, C, A, D, E]Candidate C prefers [C, A, D, B, E]Candidate D prefers [D, A, B, E, C]Candidate E prefers [E, C, D, A, B]Round 4: [A, B, C, D] vs EPossible winners: [D, E, A, B]Round 3: [A, B]  vs DRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is A-----------------------------Candidate A prefers [A, E, B, D, C]Candidate B prefers [B, E, C, A, D]Candidate C prefers [C, A, E, B, D]Candidate D prefers [D, C, B, E, A]Candidate E prefers [E, D, A, B, C]Round 4: [A, B, C, D] vs EPossible winners: [E]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is E-----------------------------Candidate A prefers [A, D, E, B, C]Candidate B prefers [B, A, D, E, C]Candidate C prefers [C, D, B, A, E]Candidate D prefers [D, E, B, C, A]Candidate E prefers [E, D, A, B, C]Round 4: [A, B, C, D] vs EPossible winners: [D, E, A]Round 3: [A]  vs DRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is D-----------------------------Candidate A prefers [A, C, D, E, B]Candidate B prefers [B, D, E, A, C]Candidate C prefers [C, D, A, E, B]Candidate D prefers [D, C, A, B, E]Candidate E prefers [E, C, B, D, A]Round 4: [A, B, C, D] vs EPossible winners: [D, E, A, C]Round 3: [A, C]  vs DRound 2: [] vs CRound 1: A vs BRound 1 results: [A]Overall winner is C-----------------------------Candidate A prefers [A, B, E, D, C]Candidate B prefers [B, D, E, A, C]Candidate C prefers [C, A, D, E, B]Candidate D prefers [D, C, A, B, E]Candidate E prefers [E, A, C, B, D]Round 4: [A, B, C, D] vs EPossible winners: [D, E, A, B]Round 3: [A, B]  vs DRound 2 irrelevant; C cannot winRound 1: A vs BRound 1 results: [A]Overall winner is A-----------------------------Candidate A prefers [A, E, D, B, C]Candidate B prefers [B, D, E, A, C]Candidate C prefers [C, B, A, D, E]Candidate D prefers [D, E, A, C, B]Candidate E prefers [E, D, A, B, C]Round 4: [A, B, C, D] vs EPossible winners: [D, E]Round 3: []  vs DRound 2 irrelevant; C cannot winRound 1: A vs BRound 1 results: [A]Overall winner is D-----------------------------Candidate A prefers [A, B, C, D, E]Candidate B prefers [B, A, D, E, C]Candidate C prefers [C, E, D, B, A]Candidate D prefers [D, B, C, E, A]Candidate E prefers [E, C, A, B, D]Round 4: [A, B, C, D] vs EPossible winners: [D, E, B, C]Round 3: [B, C]  vs DRound 2: [B] vs CRound 1 irrelevantOverall winner is B-----------------------------Candidate A prefers [A, C, D, B, E]Candidate B prefers [B, A, C, D, E]Candidate C prefers [C, A, B, D, E]Candidate D prefers [D, B, E, A, C]Candidate E prefers [E, D, B, A, C]Round 4: [A, B, C, D] vs EPossible winners: [D, A, B, C]Round 3: [A, B, C]  vs DRound 2: [A] vs CRound 1 irrelevantOverall winner is A-----------------------------Candidate A prefers [A, C, B, E, D]Candidate B prefers [B, A, E, D, C]Candidate C prefers [C, A, B, D, E]Candidate D prefers [D, E, C, A, B]Candidate E prefers [E, B, D, A, C]Round 4: [A, B, C, D] vs EPossible winners: [E, A, B]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1: A vs BRound 1 results: [A]Overall winner is A-----------------------------Candidate A prefers [A, B, C, D, E]Candidate B prefers [B, C, D, E, A]Candidate C prefers [C, B, D, A, E]Candidate D prefers [D, E, B, A, C]Candidate E prefers [E, C, A, B, D]Round 4: [A, B, C, D] vs EPossible winners: [D, E, B, C]Round 3: [B, C]  vs DRound 2: [B] vs CRound 1 irrelevantOverall winner is B-----------------------------Candidate A prefers [A, B, D, E, C]Candidate B prefers [B, D, A, E, C]Candidate C prefers [C, E, B, A, D]Candidate D prefers [D, E, B, C, A]Candidate E prefers [E, B, D, A, C]Round 4: [A, B, C, D] vs EPossible winners: [D, E]Round 3: []  vs DRound 2 irrelevant; C cannot winRound 1: A vs BRound 1 results: [B]Overall winner is E-----------------------------Candidate A prefers [A, C, D, E, B]Candidate B prefers [B, D, C, E, A]Candidate C prefers [C, D, B, A, E]Candidate D prefers [D, E, C, A, B]Candidate E prefers [E, B, D, C, A]Round 4: [A, B, C, D] vs EPossible winners: [D, E, C]Round 3: [C]  vs DRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is D-----------------------------Candidate A prefers [A, C, E, D, B]Candidate B prefers [B, D, A, E, C]Candidate C prefers [C, B, E, A, D]Candidate D prefers [D, A, B, C, E]Candidate E prefers [E, A, D, B, C]Round 4: [A, B, C, D] vs EPossible winners: [E, A, B, C]Round 3 irrelevant; D cannot winRound 2: [A, B] vs CRound 1: A vs BRound 1 results: [A]Overall winner is A-----------------------------Candidate A prefers [A, B, D, C, E]Candidate B prefers [B, E, A, D, C]Candidate C prefers [C, A, D, E, B]Candidate D prefers [D, C, A, E, B]Candidate E prefers [E, D, B, A, C]Round 4: [A, B, C, D] vs EPossible winners: [D, E, A, C]Round 3: [A, C]  vs DRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is A-----------------------------Candidate A prefers [A, E, B, D, C]Candidate B prefers [B, D, E, A, C]Candidate C prefers [C, E, D, A, B]Candidate D prefers [D, E, A, C, B]Candidate E prefers [E, A, B, C, D]Round 4: [A, B, C, D] vs EPossible winners: [E]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is E-----------------------------Candidate A prefers [A, B, C, E, D]Candidate B prefers [B, D, A, E, C]Candidate C prefers [C, B, D, E, A]Candidate D prefers [D, A, C, E, B]Candidate E prefers [E, A, C, B, D]Round 4: [A, B, C, D] vs EPossible winners: [D, A, B, C]Round 3: [A, B, C]  vs DRound 2: [B] vs CRound 1 irrelevantOverall winner is C-----------------------------Candidate A prefers [A, D, B, E, C]Candidate B prefers [B, C, D, A, E]Candidate C prefers [C, E, D, A, B]Candidate D prefers [D, B, C, A, E]Candidate E prefers [E, B, D, C, A]Round 4: [A, B, C, D] vs EPossible winners: [D, A, B, C]Round 3: [A, B, C]  vs DRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is D-----------------------------Candidate A prefers [A, E, C, B, D]Candidate B prefers [B, A, D, E, C]Candidate C prefers [C, E, B, A, D]Candidate D prefers [D, C, B, E, A]Candidate E prefers [E, D, B, C, A]Round 4: [A, B, C, D] vs EPossible winners: [E]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is E-----------------------------Candidate A prefers [A, E, C, D, B]Candidate B prefers [B, E, D, A, C]Candidate C prefers [C, D, B, E, A]Candidate D prefers [D, E, C, A, B]Candidate E prefers [E, C, B, D, A]Round 4: [A, B, C, D] vs EPossible winners: [E]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is E-----------------------------Candidate A prefers [A, C, E, B, D]Candidate B prefers [B, E, A, C, D]Candidate C prefers [C, E, D, B, A]Candidate D prefers [D, C, E, B, A]Candidate E prefers [E, A, D, C, B]Round 4: [A, B, C, D] vs EPossible winners: [E, C]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is C-----------------------------Candidate A prefers [A, E, C, B, D]Candidate B prefers [B, D, A, E, C]Candidate C prefers [C, E, A, B, D]Candidate D prefers [D, B, E, C, A]Candidate E prefers [E, A, B, D, C]Round 4: [A, B, C, D] vs EPossible winners: [E]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is E-----------------------------Candidate A prefers [A, D, C, B, E]Candidate B prefers [B, D, C, E, A]Candidate C prefers [C, B, A, D, E]Candidate D prefers [D, C, B, A, E]Candidate E prefers [E, C, D, B, A]Round 4: [A, B, C, D] vs EPossible winners: [D, A, B, C]Round 3: [A, B, C]  vs DRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is D-----------------------------Candidate A prefers [A, B, D, C, E]Candidate B prefers [B, E, D, C, A]Candidate C prefers [C, A, E, D, B]Candidate D prefers [D, C, A, B, E]Candidate E prefers [E, C, B, A, D]Round 4: [A, B, C, D] vs EPossible winners: [E, A, B, C]Round 3 irrelevant; D cannot winRound 2: [A, B] vs CRound 1 irrelevantOverall winner is E-----------------------------Candidate A prefers [A, B, D, E, C]Candidate B prefers [B, E, D, C, A]Candidate C prefers [C, A, D, B, E]Candidate D prefers [D, E, C, B, A]Candidate E prefers [E, B, D, C, A]Round 4: [A, B, C, D] vs EPossible winners: [D, E, B]Round 3: [B]  vs DRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is B-----------------------------Candidate A prefers [A, C, D, B, E]Candidate B prefers [B, E, A, D, C]Candidate C prefers [C, E, D, A, B]Candidate D prefers [D, A, B, C, E]Candidate E prefers [E, C, B, A, D]Round 4: [A, B, C, D] vs EPossible winners: [E, B, C]Round 3 irrelevant; D cannot winRound 2: [B] vs CRound 1 irrelevantOverall winner is C-----------------------------Candidate A prefers [A, D, B, C, E]Candidate B prefers [B, D, E, A, C]Candidate C prefers [C, D, A, E, B]Candidate D prefers [D, E, A, B, C]Candidate E prefers [E, C, B, D, A]Round 4: [A, B, C, D] vs EPossible winners: [D, E]Round 3: []  vs DRound 2 irrelevant; C cannot winRound 1: A vs BRound 1 results: [A]Overall winner is D-----------------------------Candidate A prefers [A, B, E, C, D]Candidate B prefers [B, E, A, C, D]Candidate C prefers [C, B, A, E, D]Candidate D prefers [D, B, E, A, C]Candidate E prefers [E, A, B, C, D]Round 4: [A, B, C, D] vs EPossible winners: [E, B]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is B-----------------------------Candidate A prefers [A, B, D, E, C]Candidate B prefers [B, A, D, C, E]Candidate C prefers [C, A, E, B, D]Candidate D prefers [D, A, C, E, B]Candidate E prefers [E, A, C, D, B]Round 4: [A, B, C, D] vs EPossible winners: [D, E, A, C]Round 3: [A, C]  vs DRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is A-----------------------------Candidate A prefers [A, C, E, D, B]Candidate B prefers [B, A, D, C, E]Candidate C prefers [C, B, E, A, D]Candidate D prefers [D, A, B, C, E]Candidate E prefers [E, C, B, A, D]Round 4: [A, B, C, D] vs EPossible winners: [E, A, B, C]Round 3 irrelevant; D cannot winRound 2: [A, B] vs CRound 1: A vs BRound 1 results: [B]Overall winner is C-----------------------------Candidate A prefers [A, E, B, D, C]Candidate B prefers [B, C, A, D, E]Candidate C prefers [C, B, A, E, D]Candidate D prefers [D, C, E, B, A]Candidate E prefers [E, A, C, D, B]Round 4: [A, B, C, D] vs EPossible winners: [E, A, C]Round 3 irrelevant; D cannot winRound 2: [A] vs CRound 1 irrelevantOverall winner is C-----------------------------Candidate A prefers [A, C, E, B, D]Candidate B prefers [B, E, C, D, A]Candidate C prefers [C, D, B, E, A]Candidate D prefers [D, A, C, B, E]Candidate E prefers [E, A, C, D, B]Round 4: [A, B, C, D] vs EPossible winners: [E, B, C]Round 3 irrelevant; D cannot winRound 2: [B] vs CRound 1 irrelevantOverall winner is C-----------------------------Candidate A prefers [A, C, D, B, E]Candidate B prefers [B, D, E, A, C]Candidate C prefers [C, B, E, D, A]Candidate D prefers [D, A, E, B, C]Candidate E prefers [E, A, C, D, B]Round 4: [A, B, C, D] vs EPossible winners: [D, E, B]Round 3: [B]  vs DRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is D-----------------------------Candidate A prefers [A, D, B, E, C]Candidate B prefers [B, A, D, E, C]Candidate C prefers [C, D, B, A, E]Candidate D prefers [D, E, C, B, A]Candidate E prefers [E, A, C, B, D]Round 4: [A, B, C, D] vs EPossible winners: [D, E, A, B]Round 3: [A, B]  vs DRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is A-----------------------------Candidate A prefers [A, C, B, E, D]Candidate B prefers [B, D, C, E, A]Candidate C prefers [C, A, B, E, D]Candidate D prefers [D, C, A, B, E]Candidate E prefers [E, A, C, D, B]Round 4: [A, B, C, D] vs EPossible winners: [E, A, B, C]Round 3 irrelevant; D cannot winRound 2: [A, B] vs CRound 1 irrelevantOverall winner is C-----------------------------Candidate A prefers [A, C, B, D, E]Candidate B prefers [B, D, E, C, A]Candidate C prefers [C, E, D, B, A]Candidate D prefers [D, A, E, B, C]Candidate E prefers [E, C, D, B, A]Round 4: [A, B, C, D] vs EPossible winners: [D, E]Round 3: []  vs DRound 2 irrelevant; C cannot winRound 1: A vs BRound 1 results: [B]Overall winner is E-----------------------------Candidate A prefers [A, B, D, C, E]Candidate B prefers [B, C, A, D, E]Candidate C prefers [C, A, E, D, B]Candidate D prefers [D, B, C, A, E]Candidate E prefers [E, A, B, C, D]Round 4: [A, B, C, D] vs EPossible winners: [D, A, B, C]Round 3: [A, B, C]  vs DRound 2: [A, B] vs CRound 1: A vs BRound 1 results: [A]Overall winner is C-----------------------------Candidate A prefers [A, B, C, D, E]Candidate B prefers [B, A, E, D, C]Candidate C prefers [C, E, B, D, A]Candidate D prefers [D, C, E, B, A]Candidate E prefers [E, B, D, A, C]Round 4: [A, B, C, D] vs EPossible winners: [E, C]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is E-----------------------------Candidate A prefers [A, C, B, E, D]Candidate B prefers [B, A, C, D, E]Candidate C prefers [C, D, B, E, A]Candidate D prefers [D, C, A, B, E]Candidate E prefers [E, D, B, C, A]Round 4: [A, B, C, D] vs EPossible winners: [D, A, B, C]Round 3: [A, B, C]  vs DRound 2: [] vs CRound 1: A vs BRound 1 results: [B]Overall winner is C-----------------------------Candidate A prefers [A, B, E, C, D]Candidate B prefers [B, A, C, D, E]Candidate C prefers [C, B, D, E, A]Candidate D prefers [D, C, B, A, E]Candidate E prefers [E, D, C, A, B]Round 4: [A, B, C, D] vs EPossible winners: [D, A, B, C]Round 3: [A, B, C]  vs DRound 2: [B] vs CRound 1 irrelevantOverall winner is C-----------------------------Candidate A prefers [A, C, B, E, D]Candidate B prefers [B, C, E, A, D]Candidate C prefers [C, E, A, D, B]Candidate D prefers [D, A, C, B, E]Candidate E prefers [E, B, A, C, D]Round 4: [A, B, C, D] vs EPossible winners: [E, B, C]Round 3 irrelevant; D cannot winRound 2: [B] vs CRound 1 irrelevantOverall winner is C-----------------------------Candidate A prefers [A, E, D, B, C]Candidate B prefers [B, A, C, D, E]Candidate C prefers [C, E, A, D, B]Candidate D prefers [D, E, B, A, C]Candidate E prefers [E, B, D, C, A]Round 4: [A, B, C, D] vs EPossible winners: [E]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is E-----------------------------Candidate A prefers [A, C, D, E, B]Candidate B prefers [B, E, D, A, C]Candidate C prefers [C, D, E, A, B]Candidate D prefers [D, E, A, B, C]Candidate E prefers [E, C, D, B, A]Round 4: [A, B, C, D] vs EPossible winners: [D, E]Round 3: []  vs DRound 2 irrelevant; C cannot winRound 1: A vs BRound 1 results: [A]Overall winner is D-----------------------------Candidate A prefers [A, E, C, B, D]Candidate B prefers [B, D, C, E, A]Candidate C prefers [C, B, A, E, D]Candidate D prefers [D, E, A, B, C]Candidate E prefers [E, C, D, B, A]Round 4: [A, B, C, D] vs EPossible winners: [E]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is E-----------------------------Candidate A prefers [A, E, D, C, B]Candidate B prefers [B, A, E, D, C]Candidate C prefers [C, D, A, B, E]Candidate D prefers [D, B, A, E, C]Candidate E prefers [E, B, C, D, A]Round 4: [A, B, C, D] vs EPossible winners: [E, A, B]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1: A vs BRound 1 results: [B]Overall winner is E-----------------------------Candidate A prefers [A, E, C, D, B]Candidate B prefers [B, E, D, A, C]Candidate C prefers [C, E, A, B, D]Candidate D prefers [D, E, A, B, C]Candidate E prefers [E, B, A, C, D]Round 4: [A, B, C, D] vs EPossible winners: [E]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is E-----------------------------Candidate A prefers [A, B, E, D, C]Candidate B prefers [B, E, D, A, C]Candidate C prefers [C, B, A, D, E]Candidate D prefers [D, C, A, E, B]Candidate E prefers [E, A, B, D, C]Round 4: [A, B, C, D] vs EPossible winners: [E, A, B]Round 3 irrelevant; D cannot winRound 2 irrelevant; C cannot winRound 1: A vs BRound 1 results: [A]Overall winner is A-----------------------------Candidate A prefers [A, D, E, C, B]Candidate B prefers [B, E, A, C, D]Candidate C prefers [C, D, A, B, E]Candidate D prefers [D, B, E, C, A]Candidate E prefers [E, A, D, C, B]Round 4: [A, B, C, D] vs EPossible winners: [D, E, B]Round 3: [B]  vs DRound 2 irrelevant; C cannot winRound 1 irrelevantOverall winner is D-----------------------------Candidate A prefers [A, B, D, E, C]Candidate B prefers [B, C, D, E, A]Candidate C prefers [C, E, B, D, A]Candidate D prefers [D, A, E, C, B]Candidate E prefers [E, A, C, B, D]Round 4: [A, B, C, D] vs EPossible winners: [D, E]Round 3: []  vs DRound 2 irrelevant; C cannot winRound 1: A vs BRound 1 results: [A]Overall winner is D-----------------------------Wins for A: 9 (18.0%)Wins for B: 5 (10.0%)Wins for C: 12 (24.0%)Wins for D: 11 (22.0%)Wins for E: 13 (26.0%)
 
Yeah, I have a bug somewhere. I have a scenario where A, B, and C, would all beat E, and E would beat D. D hates E so much that he will vote for any other candidate over himself just to block E from winning, and yet my algorithm has E winning overall, even though D cannot possibly win round 3.

:kicksrock:

ETA: I think my flaw is that when I get to "Run A against B, and the winner against C, then the winner of that against D, and the winner of that against E to get the overall winner.", those are reverting to overall preferences, and not taking the strategic votes into account.

 
Last edited by a moderator:
Don't know exactly how your code works, it does look like a somewhat different method than mine (though basically accomplishing the same things). I think your approach probably makes sense though, if your basic algorithm is:

Starting at the last round:

- Compute a list of possible winners in this round

- If the list has only one element, that's the winner

- Otherwise go back one round and do it again

 
OK, sanity check.

I'm trying to work out how to represent "adjusted" preferences for round n, after determining those who cannot win round n+1

If A's initial preference is: A-D-B-E-C, and then we determine that only D and E could win round 4, then any vote for A, B, or C is effectively a vote for E. Since A would prefer D to E, his effective new preference would be D-A-B-E-C, right?

Eliminating candidates who cannot possibly win, this reduces to D-E, so that is A's preference in round 3.

In round 3, E is not participating, so A should vote for D over any opponent.

 
How does this distribution look?

Wins for A: 1271 (12.71%)
Wins for B: 2091 (20.91%)
Wins for C: 2512 (25.12%)
Wins for D: 2825 (28.25%)
Wins for E: 1301 (13.01%)
 
heckmanm said:
How does this distribution look?

Wins for A: 1271 (12.71%)

Wins for B: 2091 (20.91%)

Wins for C: 2512 (25.12%)

Wins for D: 2825 (28.25%)

Wins for E: 1301 (13.01%)
Click to expand...
Not like mine. :)

I came up with A/B with the highest chance of winning, C closely behind, D a little further behind and E way behind everyone else.

This matched the distribution some guy posted on Twitter so I think it's right (or we both made the same exact mistakes). Looks like you may have fixed whatever was wrong with E, but just shifted the error to now credit a bunch of extra wins to D.

 
heckmanm said:
OK, sanity check.

I'm trying to work out how to represent "adjusted" preferences for round n, after determining those who cannot win round n+1

If A's initial preference is: A-D-B-E-C, and then we determine that only D and E could win round 4, then any vote for A, B, or C is effectively a vote for E. Since A would prefer D to E, his effective new preference would be D-A-B-E-C, right?

Eliminating candidates who cannot possibly win, this reduces to D-E, so that is A's preference in round 3.
Click to expand...
I didn't think of it in terms of adjusting preferences. No one's preferences change during the election. I thought of it as adjusting the candidates.

If E would beat B in the final round, then any vote for B is really a vote for E. So whenever I'm considering a matchup between B and _ in any round, I just replace B with E and then evaluate everyone's preferences to see who would win.

 
Ignoratio Elenchi said:
heckmanm said:
OK, sanity check.

I'm trying to work out how to represent "adjusted" preferences for round n, after determining those who cannot win round n+1

If A's initial preference is: A-D-B-E-C, and then we determine that only D and E could win round 4, then any vote for A, B, or C is effectively a vote for E. Since A would prefer D to E, his effective new preference would be D-A-B-E-C, right?

Eliminating candidates who cannot possibly win, this reduces to D-E, so that is A's preference in round 3.
Click to expand...
I didn't think of it in terms of adjusting preferences. No one's preferences change during the election. I thought of it as adjusting the candidates.

If E would beat B in the final round, then any vote for B is really a vote for E. So whenever I'm considering a matchup between B and _ in any round, I just replace B with E and then evaluate everyone's preferences to see who would win.
Click to expand...
That's a better way to think about it. Thanks.

 
Ignoratio Elenchi said:
heckmanm said:
How does this distribution look?

Wins for A: 1271 (12.71%)

Wins for B: 2091 (20.91%)

Wins for C: 2512 (25.12%)

Wins for D: 2825 (28.25%)

Wins for E: 1301 (13.01%)
Click to expand...
Not like mine. :)

I came up with A/B with the highest chance of winning, C closely behind, D a little further behind and E way behind everyone else.

This matched the distribution some guy posted on Twitter so I think it's right (or we both made the same exact mistakes). Looks like you may have fixed whatever was wrong with E, but just shifted the error to now credit a bunch of extra wins to D.
Click to expand...
Latest version:

Wins for A: 2216 (22.16%)
Wins for B: 2281 (22.81%)
Wins for C: 2218 (22.18%)
Wins for D: 2040 (20.4%)
Wins for E: 1245 (12.45%)

I also calculated a "likeability" score for each candidate (basically 4-3-2-1 based on the other candidate's 2nd-5th preferences, averaged). So a candidate who is everyone else's 2nd choice would score 4.0.

Minimum winning likeability: 1.75
Maximum winning likeability: 4.0
Average winning likeability: 3.146425


 
So here's an interesting scenario

Candidate A prefers [A, B, C, E, D]
Candidate B prefers [b, A, D, C, E]
Candidate C prefers [C, E, A, D, B]
Candidate D prefers [D, E, B, A, C]
Candidate E prefers [E, A, B, D, C]

On average, C is least "liked" candidate, ranking 3rd, 4th, 5th, and 5th (1.75 likeability), respectively by his peers, while A is the most liked, ranking 2nd, 2nd, 3rd, and 4th (3.25 likeability)

Yet in the 4th round, everyone but C would lose to E, leaving C and E as the only viable candidates, and C as the inevitable winner because 3 candidates prefer C to E, even though nobody really likes him very much.
 
heckmanm said:
Latest version:

Wins for A: 2216 (22.16%)

Wins for B: 2281 (22.81%)

Wins for C: 2218 (22.18%)

Wins for D: 2040 (20.4%)

Wins for E: 1245 (12.45%)
Click to expand...
:goodposting: That's just about what I got. It's actually unclear to me from my trials whether C has the same win probability as A and B, or slightly less. It's usually very close but seems like A and B are the same and C might tend to be a little lower overall, though I haven't really analyzed it. For whatever it's worth, Here's the tweet that inspired the question, and it looks like he has C a little lower than A/B.

 
Ignoratio Elenchi said:
heckmanm said:
Latest version:

Wins for A: 2216 (22.16%)

Wins for B: 2281 (22.81%)

Wins for C: 2218 (22.18%)

Wins for D: 2040 (20.4%)

Wins for E: 1245 (12.45%)
Click to expand...
:goodposting: That's just about what I got. It's actually unclear to me from my trials whether C has the same win probability as A and B, or slightly less. It's usually very close but seems like A and B are the same and C might tend to be a little lower overall, though I haven't really analyzed it. For whatever it's worth, Here's the tweet that inspired the question, and it looks like he has C a little lower than A/B.
Click to expand...
Does E have to beat everyone in round 4 to win? i.e., if just one candidate beats E, will the other 3 inevitably vote for him? I think so.

Also, I've run my program for up to 25 candidates, and the pattern is similar - the first ~80% of the candidates have similar but slightly decreasing win probability, and then it drops off rather sharply from there to the last candidate.

 
heckmanm said:
Does E have to beat everyone in round 4 to win? i.e., if just one candidate beats E, will the other 3 inevitably vote for him? I think so.
Click to expand...
I think so too. Assume there's at least one candidate who would beat E in the final round. Call this candidate X. In any prior round of voting, any candidates that wouldn't eventually beat E are replaced by "E" in terms of determining preferences (e.g. "a vote for B is essentially a vote for E"). For the real E to win, you have to assume one of those prior "E"'s will knock X out. But that implies that voters prefer E to X, which is a contradiction. Thus if anyone is preferred to E, then E can't win.

 
ABCDE cars

A is slowest

ABCDE - 20% chance

B is slowest

A BCDE - 20% chance

C is slowest

AB CDE, A B CDE - 10% chance of either

D is slowest

ABC DE, AB C DE, A BC DE, A B C DE - 5% chance of any

E is slowest

ABCD E, A BCD E, AB CD E, A B CD E, ABC D E, A BC D E, AB C D E, A B C D E - 2.5% chance of any

Average # of groups

2.4

:shrug:

ETA - I missed a grouping in E is slowest

 
Last edited by a moderator:
bostonfred said:
Log2 (n)
Click to expand...
I think this is correct. The slowest car will be, on average, in the middle of the pack, with half the cars grouped behind it. Of the cars in front, the slowest of those will be on average in the middle again, with a quarter of the cars grouped behind it. Then 1/8, 1/16, etc.

Doubling the number of cars increases the expected groups by 1. Cutting it in half decreases the groups by 1. So, log2(n).

Granted, I've only given it like 30 seconds of thought, so it's likely I'm missing something.

 
If there were 128 cars, then on average the slowest car would have 64 ahead of it and 64 behind it. Every car behind the slowest car will eventually catch up to it and not pass it. So that's one group.

Of the 64 cars left, the slowest car will be, on average, halfway. 32 cars will be ahead and 32 behind. All of the remaining cars are moving faster than the slow group behind them, and none of the guys behind the slowest of the front bunch will move past it, so we now have a group of 64 behind a group of 32 with 32 more cars in the front.

Of those, on average, 16 will be stuck behind the new slowest car. Then 8. Then 4. Then 2. Then 1.

We keep cutting it in half. So the answer is, as many times as we can cut it in half. Or the number of times to which we can multiply 2 by itself to get n.

In other words, log base 2 (n).

 
"Each car is going in the same direction, and each driver has a distinct positive speed at which she prefers to travel."

Apparently all the drivers are female. All logic should thus be thrown out.

 
bostonfred said:
If there were 128 cars, then on average the slowest car would have 64 ahead of it and 64 behind it. Every car behind the slowest car will eventually catch up to it and not pass it. So that's one group.

Of the 64 cars left, the slowest car will be, on average, halfway. 32 cars will be ahead and 32 behind. All of the remaining cars are moving faster than the slow group behind them, and none of the guys behind the slowest of the front bunch will move past it, so we now have a group of 64 behind a group of 32 with 32 more cars in the front.

Of those, on average, 16 will be stuck behind the new slowest car. Then 8. Then 4. Then 2. Then 1.

We keep cutting it in half. So the answer is, as many times as we can cut it in half. Or the number of times to which we can multiply 2 by itself to get n.

In other words, log base 2 (n).
Click to expand...
Fails in the easiest of cases, n = 1 (1 group), n = 2 (1.5 groups), n = 3 (1.833 groups).

 
Last edited by a moderator:
Actually, log2(2) is not correct.

CBusAlex said:
bostonfred said:
Log2 (n)
Click to expand...
I think this is correct. The slowest car will be, on average, in the middle of the pack, with half the cars grouped behind it. Of the cars in front, the slowest of those will be on average in the middle again, with a quarter of the cars grouped behind it. Then 1/8, 1/16, etc.

Doubling the number of cars increases the expected groups by 1. Cutting it in half decreases the groups by 1. So, log2(n).

Granted, I've only given it like 30 seconds of thought, so it's likely I'm missing something.
Click to expand...
Upon further examination, this is not correct, at least for small numbers.

For two cars, there are two possible orders. {fast, slow} = one group, {slow, fast} = 2 groups. 1.5 /= log2(2)

For three cars, there are six orders:

{fast, medium, slow} = 1 group

{medium, fast, slow} = 1 group

{fast, slow, medium} = 2 groups

{medium, slow, fast} = 2 groups

{slow, fast, medium} = 2 groups

{slow, medium, fast} = 3 groups

Average # of groups is 1.833 /= log2(2)

 
JayMan said:
JayMan said:
Ignoratio Elenchi said:
New puzzle, and solution to last week's.
Click to expand...
Quick answer would be (N+1)/2 but it's overshooting on some scenarios - trying to find these patterns.
Click to expand...
Think I've corrected my problem... Avg(n+1) = Avg(n) + 1/(n+1) with obviously Avg(1)=1
Click to expand...
Or, a better explanation is that the j-th car (they are listed as:1,2,3...n) is ‘leading’ a group if and only if he’s the slowest of the first j cars – and since their speeds are random, that probability is 1/j. The number of groups is the expected number of those ‘leading’ cars – which is the n-th harmonic: 1 + 1/2 + 1/3 +... + 1/n

 
JayMan said:
JayMan said:
JayMan said:
Ignoratio Elenchi said:
New puzzle, and solution to last week's.
Click to expand...
Quick answer would be (N+1)/2 but it's overshooting on some scenarios - trying to find these patterns.
Click to expand...
Think I've corrected my problem... Avg(n+1) = Avg(n) + 1/(n+1) with obviously Avg(1)=1
Click to expand...
Or, a better explanation is that the j-th car (they are listed as:1,2,3...n) is ‘leading’ a group if and only if he’s the slowest of the first j cars – and since their speeds are random, that probability is 1/j. The number of groups is the expected number of those ‘leading’ cars – which is the n-th harmonic: 1 + 1/2 + 1/3 +... + 1/n
Click to expand...
I think this is right. Based on my crappy excel sheet I was getting answers that were approaching the harmonic series.

 
Ignoratio Elenchi said:
JayMan said:
Ignoratio Elenchi said:
New puzzle, and solution to last week's.
Click to expand...
Quick answer would be (N+1)/2 but it's overshooting on some scenarios - trying to find these patterns.
Click to expand...
I'm just now getting around to giving this a shot and this is what I'm coming up with at first as well. Are you sure it's wrong? Could you provide an example of a scenario where it's not the case?
Click to expand...
Already at n=3... on the 6 possibilities there are (1, 1, 2, 2, 2, 3) groups: 11/6 = 1 + 1/2 + 1/3 and not 12/6 which would be (n+1)/2

 
I wrote a program (easier than the election one!) to run multiple trials on various numbers of cars. In general:

1. Assign each car a random preferred speed, and set its actual speed to the preferred speed

2. Loop through the list of cars repeatedly, starting at #2 (#1 can go his preferred speed no matter what):

a. If car n wants to go faster than car n-1, set n's actual speed to that of n-1

b. If we get through the whole list without changing any speeds, we're done, with groups of 1 or more cars moving at slower and slower speeds.

3. Count the number of different "actual speed" values that remain in the entire list. That is the number of groups.

I ran 1000 trials for each number of cars, and averaged the results. Definitely less than log2(n).

Code: 
Cars	Groups	Log2(n)10	2.886	3.32220	3.664	4.32230	4.036	4.90740	4.197	5.32250	4.575	5.64460	4.724	5.90770	4.807	6.12980	5.003	6.32290	5.034	6.492100	5.046	6.644150	5.668	7.229200	5.847	7.644
 
JayMan said:
Ignoratio Elenchi said:
JayMan said:
Ignoratio Elenchi said:
New puzzle, and solution to last week's.
Click to expand...
Quick answer would be (N+1)/2 but it's overshooting on some scenarios - trying to find these patterns.
Click to expand...
I'm just now getting around to giving this a shot and this is what I'm coming up with at first as well. Are you sure it's wrong? Could you provide an example of a scenario where it's not the case?
Click to expand...
Already at n=3... on the 6 possibilities there are (1, 1, 2, 2, 2, 3) groups: 11/6 = 1 + 1/2 + 1/3 and not 12/6 which would be (n+1)/2
Click to expand...
Which are the two 1's? I see (1, 2, 2, 2, 2, 3) groups, making 12/6 = 2 = (n+1)/2

Strip away the story about the cars and whatnot and this seems like a relatively simple counting problem. For each permutation of the integers from 1 to n, when you move left to right through the sequence how many times is the ith term less than the (i-1)th term?

 
heckmanm said:
I wrote a program (easier than the election one!) to run multiple trials on various numbers of cars. In general:

1. Assign each car a random preferred speed, and set its actual speed to the preferred speed

2. Loop through the list of cars repeatedly, starting at #2 (#1 can go his preferred speed no matter what):

a. If car n wants to go faster than car n-1, set n's actual speed to that of n-1

b. If we get through the whole list without changing any speeds, we're done, with groups of 1 or more cars moving at slower and slower speeds.

3. Count the number of different "actual speed" values that remain in the entire list. That is the number of groups.

I ran 1000 trials for each number of cars, and averaged the results. Definitely less than log2(n).
Click to expand...
The difference between the n-th harmonic and ln(n) at limit is Euler's constant (roughly 0.577)

 
Ignoratio Elenchi said:
JayMan said:
Ignoratio Elenchi said:
JayMan said:
Ignoratio Elenchi said:
New puzzle, and solution to last week's.
Click to expand...
Quick answer would be (N+1)/2 but it's overshooting on some scenarios - trying to find these patterns.
Click to expand...
I'm just now getting around to giving this a shot and this is what I'm coming up with at first as well. Are you sure it's wrong? Could you provide an example of a scenario where it's not the case?
Click to expand...
Already at n=3... on the 6 possibilities there are (1, 1, 2, 2, 2, 3) groups: 11/6 = 1 + 1/2 + 1/3 and not 12/6 which would be (n+1)/2
Click to expand...
Which are the two 1's? I see (1, 2, 2, 2, 2, 3) groups, making 12/6 = 2 = (n+1)/2
Click to expand...
Label the cars as 1 (in front), 2, 3... with 2>3>1 (speed wise) - that result in only one group (since 2 is stuck behind 1 and 3 eventually catches on) - probably the scenario that you had at 2 groups (?)

 
JayMan said:
heckmanm said:
I wrote a program (easier than the election one!) to run multiple trials on various numbers of cars. In general:

1. Assign each car a random preferred speed, and set its actual speed to the preferred speed

2. Loop through the list of cars repeatedly, starting at #2 (#1 can go his preferred speed no matter what):

a. If car n wants to go faster than car n-1, set n's actual speed to that of n-1

b. If we get through the whole list without changing any speeds, we're done, with groups of 1 or more cars moving at slower and slower speeds.

3. Count the number of different "actual speed" values that remain in the entire list. That is the number of groups.

I ran 1000 trials for each number of cars, and averaged the results. Definitely less than log2(n).
Click to expand...
The difference between the n-th harmonic and ln(n) at limit is Euler's constant (roughly 0.577)
Click to expand...
Interesting. The difference between my numbers and ln(n) varies between 0.441 and 0.663 (for n between 10 and 200), but the graph has a definite logarithmic shape.

 
heckmanm said:
JayMan said:
heckmanm said:
I wrote a program (easier than the election one!) to run multiple trials on various numbers of cars. In general:

1. Assign each car a random preferred speed, and set its actual speed to the preferred speed

2. Loop through the list of cars repeatedly, starting at #2 (#1 can go his preferred speed no matter what):

a. If car n wants to go faster than car n-1, set n's actual speed to that of n-1

b. If we get through the whole list without changing any speeds, we're done, with groups of 1 or more cars moving at slower and slower speeds.

3. Count the number of different "actual speed" values that remain in the entire list. That is the number of groups.

I ran 1000 trials for each number of cars, and averaged the results. Definitely less than log2(n).
Click to expand...
The difference between the n-th harmonic and ln(n) at limit is Euler's constant (roughly 0.577)
Click to expand...
Interesting. The difference between my numbers and ln(n) varies between 0.441 and 0.663 (for n between 10 and 200), but the graph has a definite logarithmic shape.
Click to expand...
Exactly... the n-th harmonic series is a 'scale' graph since it deals with integers... but at infinite limits it nearly supperpose the log graph

 
Imagine the cars are traveling in a line from right to left. We don't need to calculate anything about their "random speeds", we know one will be the fastest, one will be second fastest, ... , and one will be slowest. So we can just assign them "speeds" of all the integers from 1 to n, and consider every permutation of these integers.

There will always be at least one group of cars. Additional groups will form wherever a number in the sequence is less than the one that came immediately before it. So for the case N = 3, the possible ordering of speeds are:

0 1 2 <- None of the numbers is less than its neighbor to the left. So 1 group + 0 additional = 1 group.

0 2 1 <- One of the numbers is less than its neighbor to the left. So 1 group + 1 additional = 2 groups.

1 0 2 <- One of the numbers is less than its neighbor to the left. So 1 group + 1 additional = 2 groups.

1 2 0 <- One of the numbers is less than its neighbor to the left. So 1 group + 1 additional = 2 groups.

2 0 1 <- One of the numbers is less than its neighbor to the left. So 1 group + 1 additional = 2 groups.

2 1 0 <- Two of the numbers are less than their neighbor to the left. So 1 group + 2 additional = 3 groups.

On average we'll end up with 2 groups, which is (n+1)/2.

Inspection of the first few values of N indicates that this will always be the case, so I'm pretty convinced this is the answer unless I've somehow misinterpreted the puzzle. I don't have a rigorous proof yet, going to work on that after the kids go to bed tonight. Seems similar to a skyscraper puzzle (where you're looking for the number of local maxima in a row of skyscrapers of varying heights), so that's where I'd start if someone wants to beat me to the punch. :)

Edit: I see my mistake now. A group is formed wherever a car is slower than ALL of the cars to its left, not just the one car immediately to its left.

 
Last edited by a moderator:
1 car

1(mph) = 1 group

2 cars

1, 2 = 1 group

2 1 = 2 groups, average 1.5 groups (.5, or 1/2 more than prior)

3 cars

123 = 1 group

132 = 1 group

213 = 2 groups

231 = 2 groups

312 = 2 groups

321 = 3 groups, 11/6 = 1.833 groups (.333, or 1/3 more than prior)

4 cars

1234 = 1 group

1243 = 1 group

1324 = 1 group

1342 = 1 group

1423 = 1 group

1432 = 1 group

2134 = 2 groups

2143 = 2 groups

2314 = 2 groups

2341 = 2 groups

2413 = 2 groups

2431 = 2 groups

3124 = 2 groups

3142 = 2 groups

3214 = 3 groups

3241 = 3 groups

3412 = 2 groups

3421 = 3 groups

4123 = 2 groups

4132 = 2 groups

4213 = 3 groups

4231 = 3 groups

4312 = 3 groups

4321 = 4 groups, 50/24 = 2.0833 groups (.25, or 1/4 more than prior)

So # of groups for n = 1 + 1/n + 1/n-1 + 1/n-2 .... (until your denominator = 0, at which point you stop). I'm sure there is a fancy way to write that with symbols and such.

ETA - also, the number of possible combinations of order of cars is n to the n-1 power, to the n-2 power...... Again, likely a fancy way to write that as well.

 
Last edited by a moderator:
matttyl said:
1 car

1(mph) = 1 group

2 cars

1, 2 = 1 group

2 1 = 2 groups, average 1.5 groups (.5, or 1/2 more than prior)

3 cars

123 = 1 group

132 = 1 group

213 = 2 groups

231 = 2 groups

312 = 2 groups

321 = 3 groups, 11/6 = 1.833 groups (.333, or 1/3 more than prior)

4 cars

1234 = 1 group

1243 = 1 group

1324 = 1 group

1342 = 1 group

1423 = 1 group

1432 = 1 group

2134 = 2 groups

2143 = 2 groups

2314 = 2 groups

2341 = 2 groups

2413 = 2 groups

2431 = 2 groups

3124 = 2 groups

3142 = 2 groups

3214 = 3 groups

3241 = 3 groups

3412 = 2 groups

3421 = 3 groups

4123 = 2 groups

4132 = 2 groups

4213 = 3 groups

4231 = 3 groups

4312 = 3 groups

4321 = 4 groups, 50/24 = 2.0833 groups (.25, or 1/4 more than prior)

So # of groups for n = 1 + 1/n + 1/n-1 + 1/n-2 .... (until your denominator = 0, at which point you stop). I'm sure there is a fancy way to write that with symbols and such.

ETA - also, the number of possible combinations of order of cars is n to the n-1 power, to the n-2 power...... Again, likely a fancy way to write that as well.
Click to expand...
The fancy way to write it is: 1/1 + 1/2 + 1/3 + ... 1/n (the n-th Harmonic)

 
Now that I'm properly interpreting the question I get the same answer as you guys. I'll work on some kind of proof over the weekend. I was (at least partly) right about one thing, this problem shares characteristics of Skyscraper numbers which themselves are related to unsigned Stirling numbers of the first kind, given by this sequence. If you look at the triangular array in that last link, the kth value in row n corresponds to the numbers of ways of ending up with k-1 groups from n-1 cars. For instance, the 6th row is the triangle is:

0 24 50 35 10 1

When there are N=5 cars, there are 0 ways of making 0 groups, 24 ways of making 1 group (when the slowest car is in front), 50 ways of making 2 groups, 35 ways of making 3 groups, 10 ways of making 4 groups, and 1 way of making 5 groups (when the cars are in descending order of speed). And the average number of groups is (24*1 + 50*2 + 35*3 + 10*4 + 1*5) / (24+50+35+10+1) = 274/120 = 2.2833... = the 5th harmonic number.

 
Last edited by a moderator:
Easiest explanation:

Tag the cars: 1 (front), 2, 3,... n.

The j-th car is leading a group if and only if he's the slowest of the first j cars.

Since their respective speeds are set randomly, the probability that the j-th car leads a group is: 1/j.

Now we want to know the numbers of groups (i.e. counting the leaders of groups) which is only the sum of the probabilities above: 1 + 1/2 + 1/3 + ... + 1/n.

 
Proof by Induction. Let P(N) = Average number of groups for N Cars.

P(1) = 1. 1 car = 1 group.

Assume P(N) = 1 + 1/2 + 1/3 + ... + 1/N

Then we need to prove P(N+1) = 1 + 1/2 + 1/3 + ... + 1/N + 1/(N+1) = P(N) + 1/(N+1)

P(N+1) can be considered as N cars followed by 1 car. The N cars will form P(N) groups. The 1 car at the end will add a group only if it is the slowest car. If it is faster than any of the cars in the group of N, it will join that group and not add any groups. The probability it is the slowest car is 1/(N+1) because there are N + 1 cars and the speeds are random.

Therefore P(N+1) = P(N) + 1/(N+1).

 
There will be N! - N/2 groups of cars, with drivers A, B and E preferring to be grouped together so long as none of the bridges on the highway have been knocked out by a storm, while drivers C and D group up in boats that travel between islands on their way to the gym to shoot free throws, most of which D will not witness as he's going to leave for awhile.

What do I win?

 
JayMan said:
matttyl said:
1 car

1(mph) = 1 group

2 cars

1, 2 = 1 group

2 1 = 2 groups, average 1.5 groups (.5, or 1/2 more than prior)

3 cars

123 = 1 group

132 = 1 group

213 = 2 groups

231 = 2 groups

312 = 2 groups

321 = 3 groups, 11/6 = 1.833 groups (.333, or 1/3 more than prior)

4 cars

1234 = 1 group

1243 = 1 group

1324 = 1 group

1342 = 1 group

1423 = 1 group

1432 = 1 group

2134 = 2 groups

2143 = 2 groups

2314 = 2 groups

2341 = 2 groups

2413 = 2 groups

2431 = 2 groups

3124 = 2 groups

3142 = 2 groups

3214 = 3 groups

3241 = 3 groups

3412 = 2 groups

3421 = 3 groups

4123 = 2 groups

4132 = 2 groups

4213 = 3 groups

4231 = 3 groups

4312 = 3 groups

4321 = 4 groups, 50/24 = 2.0833 groups (.25, or 1/4 more than prior)

So # of groups for n = 1 + 1/n + 1/n-1 + 1/n-2 .... (until your denominator = 0, at which point you stop). I'm sure there is a fancy way to write that with symbols and such.

ETA - also, the number of possible combinations of order of cars is n to the n-1 power, to the n-2 power...... Again, likely a fancy way to write that as well.
Click to expand...
The fancy way to write it is: 1/1 + 1/2 + 1/3 + ... 1/n (the n-th Harmonic)
Click to expand...
I think the fancy way involves this (the summation symbol), but it's been years since I've taken any math class.

 
You must log in or register to reply here.

Similar threads

GordonGekko
What Are Things That You Wished You Had Done Sooner In Life? (20/30)
Replies
7
Views
453
Gally
G
rockaction
Cinnamon To The Front Stage -- A Gentleman's Club Mix That Omits Hip Hop And Eighties Cheese (Mon Dieu!)
Replies
12
Views
494
Northern Voice
Northern Voice
GregR
Everyone Kills Hitler On Their First Trip
Replies
18
Views
834
grateful zed
grateful zed

Users who are viewing this thread

Total: 2 (members: 0, guests: 2)
Top