For what pairs of a and b is $a|b$ and $a+1|b+1$. where $|$ mean "is a divisors of".

 

There exist $p$ and $q$ so $ap=b$ and $(a+1)q = b+1$

Now is 

$$b-a=ap-a=a(p-1)$$

$$b-a=(b+1)-(a+1)=(a+1)(q-1)$$

so

$$a(p-1)=(a+1)(q-1)$$

$a$ and $a+1$ cannot share any divisors so there exists an $n$ where $an=(q-1)$ and  $(p-1)=n(a+1)$. 

Solve to $p$ and $q$ to get $q = na+1$ and $p=na+n+1=q+n$. with $b=ap=na^2+na+a$, the pair becomes: $(a, na^2+na+a)$ for $a$ and $n$ any integer. These pairs contain all possible pairs.

Three colored tokens problem

This blogpost has a nicely typesetted version using latex that might be more readable, found here

Sphere Of Influence

 I created a small game, that can be played here:

https://sphere-of-influence-service-bajtxwzftq-ew.a.run.app/

Players place tokens on the map in succession. Token can be placed on any pixel that is a land tile, (so on plains, mountains and rivers), not in oceans. The first token of each player is placed randomly. From the second turn onwards, players can only place their token in their "sphere of influence". 

Each pixel is in a player's sphere of influence if the player can travel from there to one of its tokens the quickest. It does not matter how fast you travel, or how many tokens are close, it only matters that your token is closer (in travel time) than any of your enemies' tokens. 

Travel time is calculated as follows

1. Travelling over flat land takes 1 unit of time.
2. Travelling over mountains takes 1 to 10 units of time, depending on how mountainous it is. 
3. Travelling over rivers or ocean takes 10 units of time

If all players have placed 10 tokens, the player who has the larger sphere of influence, land or water, wins. 

The code for this game is open source and can be found here:

https://gitlab.com/Elmosfire/Sphere_of_influence/

Red and Blue checkers riddle

 Image you have a circle of red and blue checkers. Between every two checkers, you add a red checker if they have the same colour, and a blue checker if they have a different colour. Then you remove the original tokens. You repeat this process indefinitely. For wat starting conditions does the circle end up with only red tokens?

In case you are on mobile, and the video does not load, here is the link: https://www.youtube.com/watch?v=JC75OzQzILk

The video gives a visual solution, but if this unrigorous solution is not satisfying, below is a more rigorous one:

A wheel as described in the problem is isomorph with the finite ring defined by:

$$\mathcal{W_n} = GF(2)[X]/(X^n+1)$$

Where for our isomorphism works as follows.

Let $\delta_0$ be 0 if the top token is red, and 1 is the top token is blue. The walk clockwise, and for each token you pass, perform the same procedure, but use $\delta_1$, $\delta_2$ and so on instead. 

Now are element of our finite ring can be written as $$\sum_{i=0}^{n-1}\delta_ix^i$$

Or expanded:

$$\delta_0+\delta_1x+\delta_2x^2+...+\delta_{n-1}x^{n-1}$$

Summing two elements is evidently equivalent to combining two wheels (where we combine two the same tokens to a red token and two different tokens to a blue token). Each delta just follows the $$GF(2)$$ rules.

Rotating the system one turn clockwise, is equivalent to multiplying with $x$. This can be shown as follows

$$\begin{align*}xs&\equiv x(\delta_0+\delta_1x+\delta_2x^2+...+\delta_{n-1}x^{n-1})\\&\equiv\delta_0x+\delta_1x^2+\delta_2x^3+...+\delta_{n-2}x^{n-1}+\delta_{n-1}x^{n}\\&\equiv\delta_0x+\delta_1x^2+\delta_2x^3+...+\delta_{n-2}x^{n-1}+\delta_{n-1}x^{n} +\delta_{n-1}(x^n+1)\\&\equiv\delta_0x+\delta_1x^2+\delta_2x^3+...+\delta_{n-2}x^{n-1}+\delta_{n-1}x^{n} +\delta_{n-1}(x^n+1)\\&\equiv\delta_0x+\delta_1x^2+\delta_2x^3+...+\delta_{n-2}x^{n-1}+\delta_{n-1} \end{align*}$$

This means that our initially described operator is the same as multiplying our initial state $s$ with $x+1$.

So our system becomes only red tokens if and only if $$\exists a: s(x+1)^a\equiv0$$

Definition 1:

$$\mathcal{W_n} = GF(2)[X]/(X^n+1)$$

We call $\mathcal{W_n}$ a wheel and $n$ the size of the wheel. In words, a wheel with size $n$ is the quotient ring of of the polynomial ring over the second order galois field

Definition 2:

For any element $w \in \mathcal{W}$ the element has period $p$ if $$wx^p \equiv w$$ Note that an element can have multiple periods.

Trivially, each of the following statements are true:

1. The period is a divider of the size of the wheel.
2. If $p$ is a period, ever multiple is also a peroid.
3. If $a$ and $b$ are periods gcd$(a,b)$ is a period
4. if $a$ and $b$ have period $p$, so does $a+b$
5. if $a$ has period $p$, so does $ab$ for all $b$

Definition 3:

$$u \equiv \sum_{i=0}^{n-1}x^i$$

Theorem 1:

$$\forall a,b \in \mathcal{W_n} a \equiv b \Leftrightarrow a+b \equiv 0$$

Proof: Trivially follows from the fact that $a+a\equiv 0$ in GF(2)

Theorem 2:

$\forall a,b \in \mathcal{W_n}$ If $a(x+1) \equiv 0$ then $a \equiv 0$ or $a \equiv u$

Proof:

Let $a=:\sum_{i=0}^{n-1}\delta_ix^i$. 

$$\begin{align*}a(x+1) &\equiv 0 \\ (x+1)\sum_{i=0}^{n-1}\delta_ix^i &\equiv 0 \\(x+1)\sum_{i=0}^{n-1}\delta_ix^i &\equiv \sum_{i=0}^{n-1}0x^i \\ \sum_{i=0}^{n-1}\delta_i + \delta_{i-1}x^i &\equiv \sum_{i=0}^{n-1}0x^i \\\delta_i + \delta_{i-1} &\equiv 0\\\delta_i &\equiv \delta_{i+1}\\\delta_i &\equiv \delta_0\end{align*}$$

Corollary 2.1:

 If $a(x+1) \equiv 0$ then $ax^j \equiv a$ for all $j$

Theorem 3:

If $a(x+1)$ has period $p$, $a$ has period $2p$.

Proof:

$$\begin{align*}a(x+1) &\equiv ax^p(x+1)\\(a+ax^p)(x+1) &\equiv 0\\a+ax^p &\equiv (a+ax^p)x^p\\a+ax^p &\equiv ax^p+ax^{2p}\\a &\equiv ax^{2p}\end{align*}$$

Corollary 3.1:

If $s(x+1)^a\equiv0$ then $s$ has period $2^a$

Lemma 4.1:

$(a+b)^2 \equiv a^2+b^2$

Proof: Trivially proven by distributive property. Note that $2\equiv 0$ so this is equivalent to the real numbers.

Lemma 4.2:

$(x+1)^{2^y}\equiv x^{2^y}+1$

Proof by induction:

Base case:

$(x+1)^{2^1}\equiv x^{2^1}+1$ is trivially true

Induction step:

Assume

$$(x+1)^{2^y}\equiv x^{2^y}+1$$

then is

$$(x+1)^{2^{y+1}}\equiv \left((x+1)^{2^y}\right)^2 \equiv \left(x^{2^y}+1\right)^2=x^{2^{y+1}}+1$$

Theorem 4:

If $a$ has period $2^y$ then $s(x+1)^{2^y}\equiv 0$

Proof:

 $$s(x+1)^{2^y} \equiv s(x^{2^y}+1) \equiv s(x^{2^y}+1) \equiv sx^{2^y}+s\equiv s+s \equiv 0$$

Epilog

From theorem 3 and 4 follow that our procedure will finish with all red tokens if and only if it has a period of a power of two. In other words, if there exists a power of two such that if I rotate the wheel with an amount of tokens equal to that power of two, if I end up with the same wheel. And in practice youonly have to check powers of two that are divisors of the size of the wheel, so there are not many cases to check.

10 000 Thanosses Problem

Imagine there are 10 000 Thanosses on a planet, each having an infinity gauntlet. Each Thanos snaps its fingers ones, removing every other remaining Thanos with a change of 50%. After all Thanosses have either snapped there fingers or are disintegrated, what is the expected value of Thanosses remaining?

This riddle was inspired by the following riddle: https://fivethirtyeight.com/features/how-many-earthlings-would-survive-63-thanos-snaps/ 

 You can watch the following video made with a horrible automatic voice, or read further to see the same argument layed out in text.

 

There are two kinds of Thanosses. One kind of Thanos is a Thanos that still has to snap it's fingers, in other words, that has a working gauntlet. Let us call this kind of Thanos an active Thanos. The other kind of Thanos is the Thanos that has already snapped it's fingers. It has no working gauntlet, and is therefore harmless. We call this kind of Thanos a passive Thanos.

If we forget for a moment the Thanos that is currently snapping, each other thanos has a chance of exactly one half to be disintegrated. This can be modelled by each Thanos flipping a coin. 

• Head means Thanos survives 
• Tail means Thanos dies

The distribution of the number of heads, and by consequence, the number of remaining Thanosses, can be described by the binomial distribution, with p being $1/2$.

Now, for each snap, there are 3 different kinds of Thanosses, 

• Snapping Thanos (1 active): chance of 1 to have 1 passive Thanos
•  Other active Thanosses ($a-1$ active): chance of $$\binom{k}{a-1}\frac{1}{2^{a-1}}$$ to have $k$ active Thanosses
•  passive Thanosses ($p$ passive): chance of $$\binom{l}{p}\frac{1}{2^{p}}$$ to have $l$ active Thanosses

We can combine these equations to write what the chances are to remain with exactly k active and l plus one passive thanosses.

$$ \binom{k}{a-1}\frac{1}{2^{a-1}} \binom{l}{b}\frac{1}{2^{b}}$$ 

 

We can also look at what happens if we add an extra passive Thanos. This new passive Thanos does not affect the survival chance of any of the other Thanosses. It's survival chance is only affected by the number of remaining active Thanosses. This means that we can split the system in a part dependant on the active and on the passive Thanosses.

 

$$E(a,p+1) = E(a,p) + P(a)$$

where $P(a)$ is a single passive Thanos's survival chance.

 

Combining this with the fact that the expected value equals the sum of each of the chances times the expected value of each corresponding system gives us a nice recursive formula for the expected value.

 

$$E(a,p) = \sum_{k=0}^{a-1} \sum_{l=0}^{p} \binom{k}{a-1}\frac{1}{2^{a-1}} \binom{l}{p}\frac{1}{2^{p}} \left(E(k,l+1)\right)$$

where $E(0,p) = p$

 

Both formulas can be combined, giving us this nice expression:

 

$$A(a)+pP(A) = \sum_{k=0}^{a-1} \sum_{l=0}^{p} \binom{k}{a-1}\frac{1}{2^{a-1}} \frac{1}{2^{p}} \left(A(k)+(l+1)P(k)\right)$$

 

This can be solved to A by plugging in zero

 

$$A(a) = \sum_{k=0}^{a-1} \binom{k}{a-1}\frac{1}{2^{a-1}} \left(A(k)+P(k)\right)$$ 

 

We can also plug in one and substact A:

 

$$P(A)= \sum_{k=0}^{a-1} \binom{k}{a-1}\frac{1}{2^{a-1}} frac{1/2} P(k)$$  

 

If we multiply the first equation with two and adding the second equation we get:

 

It can easily be seen that this expression remains constant, but we are going to proof it with string induction:

 

To proof: $A(a)+2P(a) = A(0)+2P(0) $ 

 

Base case: Trivial

 

Assume $A(k)+2P(k)$ is constant for $k \in [0,a-1]$:

 

$$A(a)+2P(a) = \sum_{k=0}^{a-1} \binom{k}{a-1}\frac{1}{2^{a-1}} \left(A(k)+2P(k)\right)$$

$$= \left(A(0)+2P(0)\right)\sum_{k=0}^{a-1} \binom{k}{a-1}\frac{1}{2^{a-1}} $$

$$= \left(A(0)+2P(0)\right) \times 1 $$

 

The value of the base case equals two, so the value of all other elements must also be two. This means that whenever there are two passive thanosses, the expected value will equal two. If there are less then two passive thanosses, like in our actual problem statement where there are zero, the number of remaining thanosses is less then two.

 

This simplifies our solution to the following equations.

$$P(a)= \sum_{k=0}^{a-1} \binom{k}{a-1}\frac{1}{2^a} P(k)$$

$$A(a)= 2-2P(a)$$

 

There is no nice formula for P, but it can be generated by a computer program. The following rust program generates all the values 

use statrs::distribution::{Binomial, Discrete};

fn main() {
    let mut p: Vec<f64> = vec![0.0; 100001 as usize];
    p[0] = 1.0;
    for n in 1usize..(1<<20) {
        let binom = Binomial::new(0.5, (n-1) as u64).unwrap();
        for k in 0usize..n {
            p[n] += binom.pmf(k as u64) * p[k] * 0.5 ;
        }
        if vec![1,100,1000,10000,100000].iter().any(|x| *x == n) {
            println!("{} & {} &{} \\\\",n,p[n],2.0-2.0*p[n]);
        }
    }
}



Running our program and taking the 10 000 result nicely gives us our solution of 1.999711521253186 which is very close to two, as expected.