Revolving Number

Remember when you first learned the decimal representation of $\displaystyle\frac{1}{k}$? Some of them have a nice form $\left( \dfrac{1}{2} = 0.5, \dfrac{1}{4} = 0.25, \dfrac{1}{5} = 0.2 \right)$, others don't terminate but the pattern is easy to remember $\left( \dfrac{1}{3} = 0.333\cdots \right)$, and the remaining ones have the form you might not care about. Among those which lie on the final category, this one particularly attracted me

\[ \frac{1}{7} = 0.\overline{142857} \]

and led my train of thought to an even bigger mystery.

The repeated value $142857$ is special on its own way. Try jotting down the first multiples of the number and you'll see why
\begin{align*} 142857 \cdot 2 & = 285714 \\
142857 \cdot 3 & = 428571 \\
142857 \cdot 4 & = 571428 \\
142857 \cdot 5 & = 714285 \\
142857 \cdot 6 & = 857142 \\
\end{align*}
The pattern is obvious: these consecutive multiples of $142857$ can be obtained by rotating the original number as if the final digit connected to the first digit (imagine the digits are sitting on a circular table). I'd like to define numbers like these as 'revolving numbers' due to their nature. A more formal definition is the following,

A circular representation of $N \in \mathbb{N}$ is the placement of its digits in a circle without changing the order. $M \in \mathbb{N}$ is a rotation of $N$ if the circular representation of $M$ can be obtained from the circular representation of $N$. Finally, $N$ is a revolving number if the first $k>1$ multiple of $N$ is a rotation of $N$ and the number of digits of $N$ equals $k$.

An initial observation from the definition of a revolving number $N$ is that its number of digits must be less than $10$; since if $k = 10$, then $10 \cdot N$ would have more digits than $N$. Hence, $N < 10^9$ and we can easily find all revolving numbers with a simple brute-force program. The challenge is for us to do it without using the aid of computer.

Apparently, the list is extremely thin within the first one billion positive integers. Let's introduce a more generous definition where $k$ is not necessarily as big as the number of digits,

$N$ is a partially-revolving number if for some $k>1$ less or equal to the number of digit of $N$, the first $k$ multiple of $N$ is a rotation of $N$ .

In other words, if $2N$ is a rotation of $N$, then $N$ is a partially-revolving number. Seems there are much more of these, but can you find one on top of your head aside from $142857$?

Surprisingly, $142857$ is the only revolving number. The title of this blog is actually a hint, since I left the noun as singular. And the more amazing fact is that the other partially-revolving numbers are only its multiples: $285714$ and $428571$.

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/#_=_

Solution for Problem #2

For those of you guessing 30, yes your answer is correct.

Proof of minimality

Let $S$ be the set of players in the group, but we will start from the empty set ($S = \emptyset$) and add new players as we advance from week to week. For the first month, we need to add $20$ different individuals to cover all $5 \cdot 4$ slots since everyone can only attend once every month. Now for the second month, we will try to analyze week per week. Let $S_n$ be the set of people (already in the set $S$) that is available to be added into $S$ at the start of week $n$  :

- Week 1, $S_1 = \{A_1,A_2,A_3,A_4,A_5\}$. We can only add one $A_i$ since they already met at the week 1 of the 1st month, (any of them will be the same, so let's add $A_1$). Then we need to add $4$ extra guys, let's call them $E_1,E_2,E_3,E_4$

- Week 2, $S_2 = \{A_2,A_3,A_4,A_5,B_1,B_2,B_3,B_4,B_5\}$. By similar fashion, we can only add one $A_i$, and one $B_j$ from $S_2$. Without losing of generality, let's add $A_2$ and $B_1$, then add $3$ new guys $F_1,F_2,F_3$

Now do you see the pattern ?
For Week 3, we will just add $A_3,B_2,C_1$, then add $2$ new guys $G_1,G_2$.
And for Week 4, add $A_4,B_3,C_2,D_1$ and add one new guy $H_1$.

We have $30$ people in $S$ after completing the 2nd month. So, we can claim that the number of people in the group should at least be $30$.

Now a possible configuration is the following :

1st Month

$A_1 A_2 A_3 A_4 A_5$

$B_1 B_2 B_3 B_4 B_5$

$C_1 C_2 C_3 C_4 C_5$

$D_1 D_2 D_3 D_4 D_5$

2nd Month

$A_1 E_1 E_2 E_3 E_4$

$A_2 B_1 F_1 F_2 F_3$

$A_3 B_2 C_1 G_1 G_2$

$A_4 B_3 C_2 D_1 H_1$

3rd Month

$A_5 B_4 C_3 D_2 E_1$

$B_5 C_4 D_3 E_2 F_2$

$C_5 D_4 E_3 F_3 G_1$

$D_5 E_4 F_4 G_2 H_1$

Note that we can modify the arrangement for the 3rd month, such that we don't need to add more people to $S$ after the 2nd month, and yet it will still meet the requirements on the problem. One important point to help you is that, since the configuration for the 4th month will be exactly the same with that of 1st month, then we have some 'restrictions' for the weeks on the 3rd month :

-  $A_i$ can attend at most until the 1st week

-  $B_i$ can attend at most until the 2nd week

-  $C_i$ can attend at most until the 3rd week

-  $D_i$ can attend at most until the 4th week

So for example, since $A_i$ can only attend the 1st week of the 3rd month, we should use the only available $A_i$ at that week i.e. $A_5$. Applying this idea and by tracking all $S_n$ as in explained in the 2nd month, will automatically generate the above's configuration for you. 

Problem #2 - How big is this Group ?

Don't worry, it's nothing about Group Theory. The following is an interesting combinatorics problem that I got few moments ago from one of my friend, Leonardo

"If every week $5$ person from a group are to meet with each other and they are assigned such that a person $x$ need to attend the meeting at most once a month and he/she will not see the same people ( either of the people) from previous meeting for at least $3$ months, what is the minimum number of the people in such group?" (1 month = 4 weeks)

Some clarification :

- If $A$ attends a meeting at week $W$, he can only attend again at least at week $W+4$ (so not only once a month)

- If both $A$ and $B$ meet at a meeting in week $W$, they can only meet again at week $W+13$

One simple fact is the group must have 20 distinct people to be assigned into 4 weeks of the first month (5 people each). The challenge is to find the minimum number of people in such group. Equivalently, if that minimum number is $N$, there will be no configurations satisfying the requirements in the problem with $N-1$ people.

See Solution

Problem #1 - Tackling the Diophantine

"Mathematics is the queen of the sciences and number theory is the queen of mathematics." - G.H. Hardy

Even though I might not concentrate in Number Theory during my upcoming PhD years, but what can I say, she is still my 'first love'. So let's get started with a Diophantine Equation !

I found this problem in my latest homework about Ring Theory especially interesting :

Find the integer solutions (x,y) of

\[x^3-2 = y^2\]

There is an advanced solution revolving around the ring $ \mathbb{Z}[\sqrt{-2}] $, which I just found recently (you don't wanna hear where I solved it), but the challenge is can you give a solution using Elementary Number Theory ?

For your information, there are exactly 2 pairs of integer solutions for this equation.

You're up !