Superiority Paradox

Today I want to take a quick look at a simple real-life semi-paradox that I observed after looking at NBA Draft Lottery system. 

The Paradox

Let's say the following is the weather forecast for tomorrow morning,

• Rain hard : 45%
• Tiny drizzle : 30%
• Cloudy : 20%
• Hot sunny day : 5%

Naively speaking from this data, it is wiser for people to take their umbrella/wear a raincoat to their office. Right?

But is it really true?

At a glance, you can see that the condition 'Rain hard', clearly has the most probability of occuring than the other possibilities. But you may forget to notice that it is more likely that it won't rain cats and dogs tomorrow morning. Yes. The probability of it won't rain hard tomorrow morning is 55%, and it's bigger than 45% !

So now we arrive to the paradox :

It's more likely that it'll be rain hard compared to each of the other weather conditions. But it's more likely that it won't rain hard tomorrow?

Then the probability itself means no good afterall? Even if one got the greatest chance than the others?

Let's now consider a tangible, real-life consequence of this issue.

NBA Draft Lottery

If you are familiar with NBA, then you know that every year NBA means to distribute the best rookies to the worst teams.  Between the 14 lowest performing teams, they will get a chance to get the #1 rookie that comes in next season. The order below starts with the worst team, 2nd worst team, etc.

1. 250 combinations, 25.0% chance of receiving the #1 pick
2. 199 combinations, 19.9% chance
3. 156 combinations, 15.6% chance
4. 119 combinations, 11.9% chance
5. 88 combinations, 8.8% chance
6. 63 combinations, 6.3% chance
7. 43 combinations, 4.3% chance
8. 28 combinations, 2.8% chance
9. 17 combinations, 1.7% chance
10. 11 combinations, 1.1% chance
11. 8 combinations, 0.8% chance
12. 7 combinations, 0.7% chance
13. 6 combinations, 0.6% chance
14. 5 combinations, 0.5% chance

Again, the same dilemma. The worst team will get the highest chance (25%), yet it's more likely for other teams to get the players. And the reality? Below are the data from the last 23 years of NBA rookie drafting on which teams got the opportunity to select the #1 rookie

• 1st : 3 times  
• 2nd : 4 times
• 3rd : 5 times
• 5th : 5 times
• 6th : 2 times
• 7th : 1 time
• 8th : 1 time
• 9th : 1 time
• 11th : 1 time

The funny thing is that the worst team only get the #1 rookie 3/23 ~ 13%, which is around half of their expected probability ! But more than anything, this empirical data, although lacking in numbers of experiment, practically confirms that the worst team really got no edge of getting the expectedly, most talented boy than the other teams.

To sum it all, I try to reconstruct some opinions from each party regarding their positions before the lottery

From the worst team's point of view,

We are in the pole position of rookie drafting? It's still much more likely that we didn't get the #1 rookie !

From the other team's point of view 

We really wish we are the worst team, they have the greatest chance of getting the #1 rookie !

Intriguing, isn't it?

Reference/Note :

1. NBA Draft Lottery data taken from http://en.wikipedia.org/wiki/NBA_Draft_Lottery#Process
2. This paradox won't occur in case that the highest party has more than 50% probability (that's why I call it semi-paradox) So can we just all agree that one thing is superior if that they have more than half the chance?

[Brilliant.org] Polynomials with no Common Factors

Okay, I've decided to post the solutions from Brilliant.org as they have proven to provide some fine problems. All the problems are owned by Brilliant.org and I don't deserve any credits for those. I only provide my own versions of the solutions.

The following is the hardest problem on NT & Algebra section last week. 

If you are currently a level 5 NT&Algebra user, you can see a solution in this link, using recursion formula and the reducibility property of a polynomial. There might be unfamiliar terms such as UFD in that solution so you need to have some basic understanding of the terms in the first place.

Anyway, I have a different, longer approach that should be more elementary. Here it goes,

First, let $x = a-b,y=c-a$ so that $b = a-x,c = a+y$ and thus
\begin{align}
\nonumber  F_n(a,x,y) & = a(-x-y)^n+(a-x)y^n+(a+y)x^n \\
& = a(x^n+y^n+(-x-y)^n) + xy(x^{n-1}-y^{n-1}) \label{eq1}
\end{align}
as now I am using the variable $(a,x,y)$ instead of $(a,b,c)$. It will be easier for one to analyze the factors of $F_n$ in this form as you will see very soon.

As we're interested for $F_4$, let $p$ be a root of $p^3 = 1, p \neq 1 \Rightarrow p^2 = -p-1$ and so in general
\[p^n =
\begin{cases}
1 & \mbox{if } n \equiv 0 \mod 3 \\
p & \mbox{if } n \equiv 1 \mod 3 \\
-p-1 & \mbox{if } n \equiv 2 \mod 3
\end{cases}
\]

From $\eqref{eq1}$ above, we obtain

\begin{align*}
F_4(a,x,px) & = a(x^4+p^4x^4+(-1-p)^4x^4)+px^2(x^3-y^3)) \\
& = x^4a(1+p^4+(p^2)^4) \\
& = x^4a(1+p+p^2) = 0
\end{align*}
means that $(y-px)|F_4$ for the two complex roots of $p^2+p+1=0$ and so
\[\prod_{p} (y-px) = x^2 \prod_p \left(\frac{y}{x}-p \right) = x^2\left( \frac{y}{x} \right)^2+\frac{y}{x}+1=  (y^2+yx+x^2)\]
divides $F_4$. Knowing one of its factor, now we can show easily that
\begin{align}
\nonumber  F_4(a,x,y) & = a(x^4+y^4+(-x-y)^4))+xy(x^3-y^3) \\
\nonumber & = 2a(x^2+xy+y^2)^2+xy(x^2+xy+y^2)(x-y) \\
& = (x^2+xy+y^2)(2a(x^2+xy+y^2)+xy(x-y)) \label{eq2}
\end{align}
Clearly, $gcd(x^2+xy+y^2,2a(x^2+xy+y^2)+xy(x-y)) = gcd(x^2+xy+y^2,xy(x-y)) = 1$
since if $f(x,y) = x^2+xy+y^2$, then
\[f(0,y) = y^2, f(x,0) = x^2, f(x,x) = 3x^2\]
are not always zero.

Thus, both factors of $F_4$ are mutually prime and irreducible in $\mathbb{R}[a,x,y]$ from which one can conlude that $F_n$ has some common factors with $F_4$ if and only if $x^2+xy+y^2 | F_n$ where $p$ is as mentioned above) or  $a(x^2+xy+y^2)+xy |F_n$. In other words, the condition is equivalent to $F_n(a,x,px) = 0$ or $F_n \left(\frac{-xy(x-y)}{2(x^2+xy+y^2)},x,y \right) = 0$ (where $x^2+xy+y^2  \neq 0 \Leftrightarrow y \neq px$).

From $\eqref{eq2}$ above, we obtain

\begin{align*}
F_n(a,x,px) & = a(x^n+p^nx^n+(-1-p)^nx^n)+px^2(x^{n-1}-y^{n-1}) \\
& = x^n(a(1+p^n+(p^2)^n)+px(1-p^{n-1}))
\end{align*}
-) If $n \equiv 0 \mod 3$, then
\[F_n(a,x,px) = x^n(a(1+1+1)+px(1-(-1-p)) = x^n(3a+px(p+2)) \neq 0\] for some choice of $x,a$
-) If $n \equiv 1 \mod 3$, then
\[F_n(a,x,px) = x^n(a(1+p+(-p-1))+px(1-1) = 0\]
-) If $n \equiv 2 \mod 3$, then
\[F_n(a,x,px) = x^n(a(1+(-p-1)+p)+px(1-p) = px(1-p) \neq 0\] for some $x \neq 0$

Hence, $F_n(a,x,px) = 0$ for all $a,x$ if and only if $n \equiv 1 \mod 3$.

Also from $\eqref{eq1}$, we have


\begin{align*}
F_n \left(\frac{-xy(x-y)}{2(x^2+xy+y^2)},x,y \right) &= -\frac{xy(x-y)(x^n+y^n+(-x-y)^n)}{2(x^2+xy+y^2)}+xy(x^{n-1}-y^{n-1})
\end{align*}
which is $0$ for $n = 1$, and for $n \geq 2$ equal to
\begin{align*}
\frac{xy(x-y)(2(x^2+xy+y^2)\displaystyle\sum_{k=0}^{n-2}x^ky^{n-2-k}-(x^n+y^n+(-x-y)^n))}{2(x^2+xy+y^2)}
\end{align*} which is $0$ iff all the respective coefficients of
\begin{align*}
g(x,y) &= 2(x^2+xy+y^2)\displaystyle\sum_{k=0}^{n-2}x^ky^{n-2-k} \\
\end{align*}
and
\begin{align*}
h(x,y) &= (x^n+y^n+(-x-y)^n) \\
& = (1+(-1)^n)x^n + \sum_{k=1}^{n-1} (-1)^n \binom{n}{k}x^{n-k}y^k + (1+(-1)^n)y^n
\end{align*}
agree. We can check that $g(x,y) = h(x,y) = 2(x^2+xy+y^2)$ for $n = 2$ and
\[g(x,y) = 2x^n+4x^{n-1}y+3\sum_{k=2}^{n-3}x^{n-k}y^k + 2xy^{n-1}+y^n\]
which  means that $1+(-1)^n = 2 \Leftrightarrow n$ even, and
\[(-1)^n \binom{n}{1} = 4 \Leftrightarrow n = 4\]
One can check that $n = 4$ also works and so
$F_n \left(\frac{-xy(x-y)}{2(x^2+xy+y^2)},x,y \right) = 0$ (where $x^2+xy+y^2  \neq 0 \Leftrightarrow y \neq px$) if and only if $n = 1,2$ or $4$.

The final conclusion is $F_n$ has some common factors with $F_4$ if and only if  $n \equiv 1 \mod 3$ or $n = 2$. There are $(1+\lfloor \frac{1000-1}{3} \rfloor) +1 = 335$ such $n$ which is less than $1000$ and so there are $1000-335 = 665$ possible $n \leq 1000$ such that $F_n$ doesn't have any common factors with $F_4$.

Problem #3 - Arranging The Runners

Sorry for the long wait, I'm back with more problems !
Last time, I saw the following problem which is briefly explained, but not that easy to answer :

There are 100 runners, each given a distinct bib labeled 1 to 100. What is the most number of runners that we could arrange in a circle, such that the product of the numbers on the bibs of any 2 neighboring runners, is less than 1000?*

For instance, I can always arrange 10 people numbered 1 to 10 in a circle without no worries, because the maximum product of 2 neighboring runners is then 9*10 = 90 < 1000. One can always guess the answer, but the complete solution to this problem is a beauty (at least that's what I found myself). 

So if your answer is K, you need to :

a) Give a possible configuration of K people fulfilling the above's criteria

b) Prove that if you take more than K people, you can't arrange them in such circle

Hurry, the runners are waiting !

*Retrieved from https://brilliant.org/assessment/new_solvable_pos/geometry-and-combinatorics/6/#_=_