Combinatorics Question of the Day (2/14)

[Laurabelle]

Suppose we are looking at our paladin's talent choices. We mutter under our breath "Hm only 6 choices, not much variation..."

Suddenly we wonder...

A. What is the minimum number of level 90 paladins that have to log on simultaneously to guarantee that at least two of those paladins have exactly the same talent choices?

B. Same as A, except in addition they also have the same spec (ret, holy, or prot).


--------

Clarification: We allow leaving any number of our choices per "row" on the talent page to be "empty", e.g. we purposefully selected no talent for that row. Otherwise, we could choose one of the three talents per row.

Note: Paladin isn't important per se, you could substitute your favorite class there if you prefer. Though, Part B will have a different answer for druids.

Note: We disregard those lower than level 90 for simplicity (since level dictates how many choices you get).

[Puri]

Suppose we are looking at our paladin's talent choices. We mutter under our breath "Hm only 6 choices, not much variation..."

Suddenly we wonder...

A. What is the minimum number of level 90 paladins that have to log on simultaneously to guarantee that at least two of those paladins have exactly the same talent choices?

B. Same as A, except in addition they also have the same spec (ret, holy, or prot).


--------

Clarification: We allow leaving any number of our choices per "row" on the talent page to be "empty", e.g. we purposefully selected no talent for that row. Otherwise, we could choose one of the three talents per row.

Note: Paladin isn't important per se, you could substitute your favorite class there if you prefer. Though, Part B will have a different answer for druids.

Note: We disregard those lower than level 90 for simplicity (since level dictates how many choices you get).

Never mind, was misreading.
And A) 4^6+1
B) 3*4^6+1

[Nalnik]

This should be simple enough. Ignoring any "there's only one real choice" talents.

A. 4097
B. 12289

For each level, we have 4 options, one of three talents plus a blank. For each choice, the next level down has four choices, etc, etc, for the six talent levels. 4^6 = 4096 possible combinations (permutations? it's been a while). So, +1 for guaranting a match.

So, if each spec has 4096 possibles, then three specs +1 for a guarantee.

16385 for druids...?

[Laurabelle]

Nice job guys, both are correct.