3 primes problem

Given prime number $p$, how many triples of distinct prime numbers $(a,b,c)$ are there for a such that $a^a + b^b + c^c$ is a multiple of $p$?

According to diriclet theorem There exist infinite many odd primes for $b$ and $c$ such that $b \equiv 1 \pmod p$ and $c \equiv -1 \pmod p$. If we take $a$ to be $p$, then we get:
$\begin{aligned}a^a+b^b+c^c &\equiv 0^a+1^b+(-1)^c &\pmod p \\&\equiv 0+1+(-1) &\pmod p \\&\equiv 0&\pmod p \\\end{aligned}$
So $a^a + b^b + c^c$ is a multiple of $p$. As there exist infinitly many values for $b$ and $c$, there are infinitly many triples.

Convertor belt esolang

 I craeted a small esotheric language, the specifications, along with an interpreter/debugger and a compiler can be found here: https://gitlab.com/Elmosfire/Conveyor_belt_esolang

Murder Mystery Generator

 I created a small program that generates a murder mystery. The source can be found here: https://gitlab.com/Elmosfire/murder_mystery_generator. The backstory is as follows (details can differ, it is a generator of course.)

5 people are invited to a rich's persons mansion, on a Sunday at 14:00. They all stay there in different rooms, meeting with different people, and at the end of the day, after everyone went home, the body is found. You, as an investigator, are tasked with finding out who murdered him. Your subordinates have already done the tasks like interviewing the suspects and witnesses, gathering DNA, and so on, but it is your task to interpret this information and find out who the killer is.

Mechanically it works like this: each person is located at a given place each hour. They will report each hour where they were, and which other people they saw in the same room. People might forget information, and they might lie, but they will never accidentally report false information. If people were committing a crime, they will lie about there whereabouts, otherwise they will tell the truth, as long as their memory serves them. But beware, the murder is not the only crime committed, people will often lie because they were committing unrelated crimes like:

1. Thief: A person was alone in a room.
2. Affair: Two people were together in a room. 
3. Secret meeting: Three people were together in a room.

No matter the crime, these people will always lie and state they were somewhere else.

You can analyse the following information:

Witness report

A person will state for every hour in which room they were, what other people they saw there and how many people they saw, if they remember. They might lie if they were committing an aforementioned crime. The murder victim will not have a witness report, and will also never be spotted after the crime (although people might claim they spotted him).

Name of murder victim

The name of the murder victim

Dna evidence

Dna of people can be found in rooms they were in. Note absence of DNA is no proof a person was not there, but existence of DNA proofs 100% the person was there.

Inventory report

Art will be missing from rooms where a "thief" crime happens.

Smart Lights

Lights will always have been on if there was at least one person in the room, otherwise, they would be off. They are logged for every room at every time.

All clues will be delivered in both a txt human-readable format, and a computer-readable format. Usually it is solvable, but this is not guaranteed. A solving algorithm using a saving backtracked is included, but a human with pen and paper usually can solve this riddle faster than a computer can, as humans are naturally good at backtracking.

3-way rock-paper-scissors (part 2)

This blog is a sequel to this blog post, so if you haven't read that 

We would like to design a game like rock paper scissors with the following axioms

1. Symmetry: The isomorphisms form a transitive permutation group.
2. Unambiguous: unless all players select the same action, there is never a draw.
3. Single winner: for all combinations, there should be a single winner.
4. Order invariance: The winner is selected indifferently from the order the players go in. 
5. Backtracking: Each losing player should have an action that if they would have chosen that action, and all other players kept the same action, they would have won.

We have already proven that this does not work if the number of players is larger than 3. For two players, rock-paper-scissors fits all axioms, so the one game we still have to find is a three-player game. 

First, let us assume that there is a cycle that is also an isomorphism. This is sufficient for axiom 2, but not necessary.

Axiom 5 can be interpreted differently, saying that for every pair(in case of 3 players) there exists play where this pair loses. And as each triple has exactly one pair that loses, this also mains that there have to exist more triples than pairs, which is only true if there are at least five actions. For five actions, it is easy to see that the following winning strategies have a transitive permutation group (the one spanned by (01234)),  and that each pair has a single winning action.

{012} -> 2

{013} -> 1

{014} -> 1

{023} -> 3

{024} -> 0

{034} -> 0

{123} -> 3

{124} -> 2

{134} -> 4

{234} -> 4

This can also be seen as drawing the five numbers on a wheel. We always pick the number wherefore there exists one number lower, but not one higher. (where 0 is one higher than 4). For example:

If we pick 034, then 3 for 3, there is a number one higher, but not one lower, so it loses. for the number 4, there is both one higher (0) and one lower (3), so it also loses. For 0, there is one lower (4), but not one higher, so zero wins. 

If we pick 134, for 1, there is no higher nor lower, so it loses. For 3, there is one higher number, but and no lower one, so it loses, but for 4, there is a number one lower, but not one higher, so it loses.

Instead of using boring numbers, we can use the 5 elements according to Taoism.

 

We only need a single cycle, so we are using the generating one. So the game goes as follows:

1. Each player selects an element, and all players reveal it at the same time.
2. If all players have selected the same element, it is a draw.
3. If two players have selected the same element, and a third one has a different element, the third player wins.
4. Otherwise, the player whos element is generated by another element, but does not generate another element wins. So for example, Fire wins if Wood is there, and Earth is not.

So in practice, there are 125 choices, 5 are draws, 60 are won by other players playing duplicates, and 60 by 3 different elements.

If you want to play this game in real life, I suggest using scissors for fire, paper for metal(like a sheet of metal), Rock for earth (obviously), closed scissors for wood, and pinky for water, altough the choice is completely free, as long as it is consistent. 

3- way rock paper scissors (part 1)

 Rock paper scissors is a game for two people. But as we can see here, it does not easily scale up to three people.

 But is interesting that it has the following properties, and we would like to keep them for our 3 person game:

1.  Symmetry: No action is inherently different from any other action.
   In other words: The permutation group of isomorphic permutations over the actions is transitive.
   
2. Unambiguous: Unless all players select the same action, there is never a draw.
3. Single Winner: For all players, there should be a single winner. All losers are considered equivalent.
4. Order invariance: The winner is selected indifferently from the order the players go in. 

First, one can easily see that if two or more players (but not all of them) select the same action, they both lose, due to a combination of axiom 2, 3 and 4. (two or more winning break axiom 3, one of them winning breaks axiom 4, drawing breaks axiom 2). 

This means that for a number of players larger than 3, a system like this cannot be constructed. (because two players taking one action and all other player taking a different action can never be resolved).

Now let us introduce some notation. Note the different actions as 0,1,2,..., and note all player actions as {0,0,1} (this is two players play action 0, 1 player plays one). The winner is well-defined by its action, so if the player with action 1 wins, we can write this as such {0,0,1} = 1. Due to axiom 4 {0,0,1} = {1,0,0} = {0,1,0}. Here equal means "has the same winner".

For the isomorphisms, we use cyclic permutation group notation. So is the isomorphism switches 0 with 1 and 2 with 3, then we note this as (01)(23).

Another thing that can be noted is the following: no isomorphic permutation can contain a cycle of the same length as the number of players. This can easily be proven, as follows

Assume there are three players, and there is an isomorphic permutation with the cycle (abc), and a is the winner of the play {a,b,c}. Then if we apply the permutation, we get a play {b,c,a} where b is the winner, but this is the same play as {a,b,c}, with a different winner, so the permutation is not isomorphic. the proof works exactly the same for any other number of players.

2 players and 2 actions

For two players and two actions, there is only one non-identity permutation, being (01), and this permutation has length 2. To make the permutation group transitive, we have to make this isomorphic, but we cannot, as it has the same length as the number of players. So this is impossible. For the same reason 

2 players and 3 actions

This is the classic rock paper scissors. But we can build the game from the ground up. Over three elements, there are 6 permutations, being (1)(2)(3), (12)(3), (1)(23), (13)(2), (123) and (132). Only the identity and the rotations do not contain a cycle of length 2, so we will have to use them for our cyclic transmutation group. 

There are 3-non draw plays: {0,1}, {0,2} and {1,2} Non of them can have the same winner (because then a reflection would be isomorphic), so we can choose one arbitrarily. For example {0,1}=1 makes {0,2}=0 and {1,2}=2. This matches 0=rock, 1=paper 2=scissors. If we had made the opposite choice the results would have been equivalent.

3 players and 3 actions

Impossible because each third=order permutation group contains at least a 3-cycle.

In other words, there is never a good way to resolve the case where one person takes rock, one takes scissor, and one takes paper.

3 players and 4 actions

The permutation group [(0123),(02)(13),(0312)] is transitive and contains no 3-cycles.

Assume {0 1 2} = 1

Then {1 2 3} = 2, {2 3 0} = 3 and {3 0 1} = 0

In addition {0 0 1} = 1 is the only way to resolve that without breaking axiom 3.

So in short, the rules can be condensed as follows:

• If all three players take the same action, it is a draw
• If two of the three players take the same action, the third player wins
• If all three players take a different action, the one with the different parity wins.

What is notable on this game is that only the parity you play matters, not the actual action.

3 players 2 actions

There is only one permutation (01), and in the end, it doesn't matter.

Rules can be derived from previous statements:

• If all three players pick the same, it is a draw
• If two of them pick the same colour, the third player wins.

This is fully consistent with all rules, but in practice, this is not a very good game.

Imagine you have finished a certain game a certain way. What would happen if you made a different choice. The results are the following:

• If you won, switching would have resulted in a draw.
• If you draw, switching would have resulted in a win.
• If you lose, switching would have just resulted in a loss, but the winner changes.

In addition to this, two players can work together, agreeing to pick a different colour than each other, ensuring that the third player can never win or draw, everything the third player can do is choose which of the two original players wins.

Therefore, to make the game better, we could add an extra axiom,

• Each player must have a winning move, given he knows the moves of all other players.

Sidestepping this issue. Adding this axiom makes constructing a game with 3 players and two actions impossible.

How to construct this game with the axiom can be read in a future blog

 

Polynomial solution to coin problem

Consider the following math problem.

 Given an unlimited supply of coins of given denominations, find the total number of distinct ways to get a desired change.

 Consider the easier problem. Consider an vector of sets of numbers (the sets finite or countable, the vector is finite). What are the number of ways to select one item from each set in order to generate a given sum $n$?

Lets define a generating function as follows:

If $v$ is a vector of sets, and $a_i$ is the number of ways to select an element from each set to sum to $i$, then is:
$$G_v(x) = a_ix^i$$.

The sum you get by selecting an element is the value of that specific element. So if the needed sum is in the set, there is one way to create the sum, otherwise the is none. By consequence:

If $v$ contains a single set $s$, then $G_v(x) = \sum_i \delta_ix^i$. where $\delta_i$ is 1 if the set contains the element, and zero if it doesn't.

Consider now two vectors, $a$ and $b$. 

Set $G_a(x) = a_ix^i$ and $G_b(x) = b_ix^i$ Say we want to create a sum of $n$. Call $k$ the sum of elements we get from the original vector $a$. Then the sum of elements we get from original vector $b$ is $n-k$. The number of ways to select a sum $k$ from $a$ is $a_k$, and the number of possibilities to select $n-k$ from $b$ is $b_{n-k}$. So the number of ways to create $n$ with this scheme is $a_kb_{n-k}$. But this counts for every $k$, and all these ways are distinct. So the total numbers of ways is $\sum_k a_kb_{n-k}$. So $G_c(x) = \sum_n\sum_k a_kb_{n-k}x^n$, but this is exactly $G_a(x)G_b(x)$.

By consequance, if $a$ and $b$ are vectors, and $c$ is the concatenation of the two, then $$G_c(x) = G_a(x)G_b(x)$$, or more extreme, each generating function can be constructed by multiplying the generating functions of the single sets in the vector.

Prime polynomals

Find all polynomals $P$ where if $x$ is a prime then $P(x)$ is also a prime.

Trivial solutions are $P(x) = p$ for $p$ any prime and $P(x)=x$.  Now we will prove that these are the only solutions.

As out polynomial has an infinite number of rational points, all coefficients are rational. 

Let $q$ be the common multiple of all denominators and $Q(x) = qP(x)$. Now $Q$ has only integer coefficients. 

There are two possible cases:

Case 1: $P(p)=p$ for all but finitly many primes $p$.

As to non-identical polynomials can only intersect a finite number of times, and this polynomial intersects $P(x)=x$ an infinite number of times, the polynomial is identical to $P(x)$, a trivial solution.

Case 2: $\exists^{\infty} p: P(p)=x$ with $x\neq p$

This is equivalent to $Q(p)=qx$.

As there exists infinitely many $p$, take a $p$ bigger than $2q$, 

This means that $p$ is coprime with $2q$, as it is with $x$, so $p$ is coprime with $2qx$.

According to Dirichlet's theorem, $p+2qxk$ hits infinitely many primes.

$Q(p+2qxk)$ can be written as $Q(p) + 2qx\times c$ with c a constant. 

So if $Q(p)=qx$, then $Q(p+2qx)$ is a multiple of $qx$, so $P(p+2qx)$ is a multiple of $x$.

Now there are two cases:

Case 1: The polynomial is constant. This gives rise to the trivial solutions.

Case 2: The polynomial is unbounded, $\forall a,\exists r \forall v > r, |P(v)| > a$.

Take $a=x$, take $v$ a prime of the form $p+2qxk$ which is larger than $r$.

It has the following properties:

1. $|P(v)| > x$
2. $|P(v)|$ is a multiple of $x$
3. $|P(v)|$ is prime.

These 3 properties are unsatisfiable. (the only multiple of $x$ that is prime is $x$ itself, which does not larger than $x$). Therefore this leads to a contradiction.

This means that the trivial solutions are the only solutions.