An analytical solution to a geometric problem.

Consider a triangle ABC. Now construct 3 isosceles triangles with the same top angle. Proof that the centre of mass of the triangle formed by the three newly created points is the centre of mass of the original triangle.

This purely geometric problem can be solved very easily if we do not think of points geometrically, but think of them as complex numbers. Assume without loss of generality that the centre of mass of $ABC$ is 0. This means $$A+B+C = 0$$ Call $A'$ the top of the triangle constructed on side $BC$, then is $$A' = B/2 + C/2 + i(B-C)/2 \tan(\alpha/2)$$ with $\alpha$ the top angle. Same works for the other sides: $$B' = C/2 + A/2 + i(C-A)/2 \tan(\alpha/2)$$ $$C' = A/2 + B/2 + i(A-B)/2 \tan(\alpha/2)$$ Summing these three numbers gives obviously zero, so the centres of mass coincide.

Square of squares

There is a famous unsolved problem in mathematics, called the square of squares, mainly popularised by numberphile. The goal is the create a 3x3 square meeting the following two criteria:

- 9 unique square numbers
- Adding to the same value along all rows, columns and diagonals.

Today, we are not going to solve this problem, but a slight adaptation of it. In particular, we are going to apply the following two changes:

- Numbers can instead of being a perfect square, also be the negative of a perfect square.
- The centre of the square has to be zero.

Our squares then looks as follows: $$\begin{matrix} b^2&-d^2&c^2\\ a^2&0 & -a^2\\ -c^2&d^2&-b^2 \end{matrix} $$ I will now prove that such a square cannot exist.
The above configuration leads to 2 equations: $$a^2 + b^2 = c^2$$ $$b^2 + c^2 = d^2$$ as $a^2 + 2b^2 = d^2$, $a$ and $d$ have the same parity. Define: $x := \frac{d-a}{2}$ and $y := \frac{d+a}{2}$ then is $$a^2 = (x-y)^2$$ $$b^2 = 2xy$$ $$c^2 = x^2 + y^2$$ $$d^2 = (x+y)^2$$ If we look at the second equation, $b^2$ is even, so $b^2$ is a multiple of 4. therefor $x$ or $y$ has to be even. As all formulas are symmetric over switching $x$ and $y$, one can assume without loss of generality that $x$ is even. Now if $b' := b/2$ and $x' := x/2$ then $$b'^2 = x'y$$ If a product is a perfect square, each factor can be written as a common factor times a square, so $x' = q\xi^2$ and $y = q\gamma^2$. Plugging this in in the third equation gives: $$c^2 = q^2(4\xi^4 + \gamma^4)$$ So $4\xi^4 + \gamma^4$ is a perfect square. Let's call it $n^2$. $$n^2 = 4\xi^4 + \gamma^4$$ Now assume we have the smallest non-zero solution for $n,\xi,\gamma$ If $n$ and $\gamma$ are even, then $n' := n/2$ and $\gamma' := \gamma/2$. $$n'^2 = \xi^4 + 4\gamma'^4$$ So our solution was not the smallest, and this leads to a contradiction. Now if we assume $n$ and $\gamma$ are odd. $$4\xi^4 = (\gamma^2-n)(\gamma^2+n)$$ as $$\gamma^2 \equiv 1 (mod 4)$$ and $n$ is odd, one of the factors on the right side is $2 (mod 4)$ and the other $0 (mod 4)$. SO for one factor the power of prime factor $2$ is $1$, and for the other it is even. So the power of prime factor 2 for the full right side is odd. As the left side is square, the power of prime factor $2$ is even. So as both sides of the equation have a different prime decomposition, this leads to a contradiction. Therefore, there is no nontrivial solution. This being said, thare is obviouslty a trivial solution, where all nine sqaures are zero.

crazy mathematicians river crossing problem

$n$ mathematicians arrive at a river. On the shores of the river lies a boat, that is strong enough to carry three mathematicians. But, as the mathematicians are crazy, they only want to cross if, at the moment the boat lands on any shore, the number of mathematicians on each side of the river, including in the boat, are coprime.

In one of my previous blogs, , I demonstrated how to convert a river crossing problem to a maze. we are now doing the same, except that as we only have one dimension, we have way more freedom how to build our maze. let's build it as follows

0		2	1	4	3	6	5	8	7	10	9
	1	0	3	2	5	4	7	6	9	8	11

Each number represents the number of people on the right riverbank, and blue means the boat is on the right, red means the boat lies on the left. You can see that if the boat lies on the left, going back is sailing one person over, going sideways is siling two people over and going forward is sailing 3 people over. Similar if the boat is on the right, then going back is sailing three people back, sideways for 2 people, and going forward is sailing one person back. Now the fact if we can walk from one end of the tape to the other is dependant on which numbers are unreachable because they lead to coprime states. If two adjacent numbers, or two numbers differing two are blocked, then it is impossible to transverse the tape, otherwise it is possible. For starters, two numbers are coprime if and only if one of them is coprime to the sum. This means that we just have to compare the number of people on the right bank with the total, and we can forget about the number on the left. Now imagine our original number of mathematicians has at least two different prime factors, $p$ and $q$. According to Bézout's identity, there exist $a$ and $b$ so $ap-bq = 1$. Now, if $ap$ and $bq$ are not in range of 0 to $n$, we can subtract multiples of $n$ until they are. This gives us two numbers, $ap$ and $bq$, that are both coprime with $n$, and are adjacent. This means that if $n$ is not a power of a prime, the mathematicians will never cross the river. Now if $n$ is a power of a prime other than two, the blocking numbers are spread out far enough so the mathematicians can get to the other side. But if $n$ is a power of 2, then all even numbers will be coprime and, unless $n$ is 4 or 2, it will be impossible to cross the river.

River crossing problems and two-dimensional mazes

River crossing problems, like the famous problem of the wolf, sheep and cabbage, are, at first sight, completely different from solving two-dimensional mazes. If you look a little deeper, you can quickly see that both problems simply reduce to finding hamiltonian paths inside of graphs, so their similarity is quite obvious, but today I am not going to talk about the graph-theoretical representations of both problems. I am going to demonstrate a technique to turn a river crossing problem into a 2-dimensional maze.

The wolf, goat and cabbage

According to Wikipedia, this problem can be described as follows:

Once upon a time a farmer went to a market and purchased a wolf, a goat, and a cabbage. On his way home, the farmer came to the bank of a river and rented a boat. But crossing the river by boat, the farmer could carry only himself and a single one of his purchases: the wolf, the goat, or the cabbage. If left unattended together, the wolf would eat the goat, or the goat would eat the cabbage. The farmer's challenge was to carry himself and his purchases to the far bank of the river, leaving each purchase intact. How did he do it?

Now, the solution can be found on the same Wikipedia article, but how can we reformulate this problem as a maze. At first one can notice that a wolf and a cabbage are completely similar in this riddle. Because in essence, it does not matter who eats who, the thing that matters is that they both cannot be left alone with a goat. So the problem could be restated as a farmer with a goat and two cabbages.
Now that this is out of the way, let us draw a grid, where the rows represent the number of goats left on the left bank of the river, and the columns the number of cabbages and wolfs. Now split each cell of this grid in two triangles, where the upper triangle means the boat is on the right side, and the bottom triangle means it is on the left.

If we state the problem like this, we can interpret the problem as a pawn, roaming around on the triangles of this grid, where each triangle represents a given state of the problem, so a given location of both the boat, as the wolf, goat and cabbage.
Here crossing a horizontal line means sailing to the other side with the goat, crossing a vertical line means crossing with a wolf or cabbage, and crossing a diagonal line means crossing alone. If we then mark all the tiles where the goat eats a cabbage or is eaten in red, we can get a nice maze, that can be solved easily:
Each crossing of one of the lines is a certain action. If we follow the blue line, we see that the following actions have to be taken:

1. Cross with goat
2. Cross alone
3. Cross with wolf (or cabbage)
4. Cross with goat
5. Cross with Cabbage (or Wolf)
6. Cross alone
7. Cross with goat

What is also the correct solution to the problem.

the two children and two adults

A similar river crossing problem is the following one:

Two children and two adults have to cross a river, and there is only one rowing boat. A boat can carry one adult or two children. The boat cannot sail on its own. How do the two children and adults get to the other side?

Using the solution as before, one can make a grid with the following allowed moves:
Note that the allowed moves do not align with the grid anymore. This does not disallow us from solving the problem, as the solution equals this:
But it is way less obvious. Can't we reshape the grid so we can only move to adjacent squares? Well, if we move all the white tiles one unit to the right, and in addition, move the second row one tile to the right and the third row 2 tiles, then the grid is reshaped as:
Where again, crossing a vertical line means 2 children cross the river, crossing a diagonal means one child crosses the river, and crossing a horizontal line means an adult crosses the river. This gives rise to the following solution:
As before, this can be transformed back to a valid solution:

1. 2 Children cross
2. 1 Child goes back
3. 1 adult crosses
4. Other child goes back
5. 2 Children cross
6. 1 Child goes back
7. Other adult crosses
8. Other child goes back
9. 2 Children cross

So the children will have to do a lot of rowing.

Evil Apprentices

Three mages and three apprentices arrive at a river. There is one boat that can carry two people. The apprentices will do as the mages ask, even when left alone, as they want to stay in the good graces of the mages. But the apprentices are also opportunistic, if at any point, the apprentices outnumber the mages at any side, they will attack the mages and take over. How can the mages get everyone to the other side?

This problem is equivalent to this problem
The exact solution is similar, but now it is not possible anymore to convert the maze to a system where all possible moves correspond to adjacent tiles. But we can still optimise the layout by rotating all the tiles and shifting the blue tiles one unit down and right. This gives the following solution:
Here, crossing the diagonal line is crossing with one mage and one apprentice, the horizontal and vertical lines are a mage and apprentice crossing alone, and crossing the corners of the triangles is crossing with two mages or two apprentices. Solving the maze is a bit harder, but still quite straight forward.

Evil Apprentices 2

You are a Wizard. you arrive with 3 apprentices and 4 bodyguards at a large canyon. You conjure a large floating disk, which you can use to transfer yourself and maximal one other person to the other side. You have to stay on the disk yourself, as your apprentices are not powerful enough to keep the disk afloat themselves. But if you take everyone to the other side one by one, you have a problem. Each of your apprentices is waiting for an opportunity to become wizard themselves, and overthrow you. They will not try anything if there is another apprentice there, because they do not want to share the glory, or if there are at least 3 guards present. How do you get with all your apprentices and guards to the other side?

There is a lot to unpack here, but notice that this is quite easy when you consider it as a mage. You do not have to transform the mage or anything, as you can only bring one unit at a time. The solution is drawn below.
In other words, bring your guards to the other side until you have 3 of them there, then bring one apprentice to the right, bring a guard back, transfer another apprentice, bring another guard back, move the last apprentice, and then carry the remaining guards to the other side. Easy.

Urns and Balls

This classical problem describes a puzzle where one has to divide black and white marbles over urns, in such a way that if we select an urn at random, and then select a random marble in this urn, the chance of us drawing a white marble is maximized. The solution to this problem can be found in many places on the internet, for example here.
This problem can be generalized by dividing $w$ white balls and $b$ black balls over $u$ urns, but the solution stays quite simple, one always has to put a single white ball in each urn, and put the remainder in the last urn.
To make the problem more interesting, we can add an extra condition to the problem, each urn must contain at least one marble of each colour. This version of the problem is has a less obvious solution, as for 50 white and black marbles, with 2 urns we have to put 1 black and 12 white marbles in the first urn and 38 white and 49 black marbles in the second.
To solve the harder version of the problem, let us first develop a framework to describe and deal with any general case. The technique described in this blog is a technique that is similar to a technique used in quantum mechanics, which is for example used to calculate the division of electrons between different atoms.

The framework

First, let us call the chance to draw a white marble times the number of urns "Energy", due to equivalence with quantum mechanics. As the number of urns is constant, maximizing the chance is equivalent to maximizing the energy. Note that in quantum mechanics, we often minimize the energy, but the concept is the same.
If we call the number of white marbles in urn $i$ $w_i$ and the number of black marbles $b_i$, then the energy can be written as
$E= \sum \frac{w_i}{t_i}$
Where $t_i=w_i+b_i$ is the total number of balls in each urn.
The workfunction is the energy needed to remove a marble from an urn, or in our case, the energy difference between the urn and a similar urn with one marble less.
For a white marble, this is
$W_w =  \frac{w_i-1}{t_i-1} - \frac{w_i}{t_i} = \frac{-b_i}{t_i(t_i-1)}$
and for a black marble this is:
$W_b =  \frac{w_i}{t_i-1} - \frac{w_i}{t_i} = \frac{w_i}{t_i(t_i-1)}$
Similarly, we can calculate the energy to add a marble
$T_w =  \frac{w_i+1}{t_i+1} - \frac{w_i}{t_i} = \frac{b_i}{t_i(t_i+1)}$
$T_b =  \frac{w_i}{t_i+1} - \frac{w_i}{t_i} = \frac{-w_i}{t_i(t_i+1)}$
As the total number of marbles is set by the problem statement, one cannot add or remove marbles, but one can move them from one urn to another.
The energy cost to move a marble from urn i to urn j is:
$W_{ij} = \frac{b_j}{t_j(t_j+1)} - \frac{b_i}{t_i(t_i-1)}$
$B_{ij} = -\frac{w_j}{t_j(t_j+1)} + \frac{w_i}{t_i(t_i-1)}$
Where W moves white marbles and B moves black marbles.
If we move a white marble from $i$ to $j$ and a black marble in the opposite direction, the energy cost is:
$\frac{1}{t_i}- \frac{1}{t_j}$
Not all of the actions are always valid. As there are sometimes restrictions on the number of marbles in each urn, we can only move the so-called "unpinned" marbles. For example, if one has to have a least one white marble in an urn, an urn with 3 white marbles is said to have 2 unpinned and one pinned marble.
Remember that we are looking for the configuration with the highest energy. This means that none of the three previously considered actions -moving white, moving black and moving both- are allowed to increase the energy. This means that the cost should always be positive, for every valid action that can be done in the configuration. While this is necessary, this is not sufficient, it could be that a configuration is locally optimal, but not globally.
Let us now only consider the action of moving a black marble in one direction and a white one in the other. Moving the black marble from the smaller to the bigger urn (and a white one opposite) will always increase our energy. This means that in the optimal configuration, at least one of the following statements is true for each pair of urns:

1. Both urns have an equal number of marbles
2. The bigger urn has no unpinned white marbles
3. The smaller urn has no unpinned black marbles

This results intuitively makes sense, as if the number of marbles is already decided, we would want to move the black marbles to urns with a larger amount of marbles, to decrease the chance that they are drawn, and move white marbles to urns with a lower number of marbles. If two urns have the same about of marbles, the chance that each one of them is drawn is equal, so moving them around does nothing.
If two urns have the same number of marbles, the energy cost of moving a single black marble is:
$B_{ij} = -\frac{w_j}{t(t+1)} + \frac{w_i}{t(t-1)}$
what can always be made smaller than zero by swapping $i$ and $j$, so, in the first condition, one must add the extra condition that one of them must have no unpinned black marbles.
The same technique applies in the second case, where the bigger urn contains no white marbles that we are allowed to move. If the bigger urn is called j, then is $t_j > t_i$ and $w_j \leq w_i$ making
$B_{ij} = -\frac{w_j}{t_j(t_j+1)} + \frac{w_i}{t_i(t_i-1)}$
Always bigger than zero, so we can add the same condition as before to the second statement. This combines all statements in a single statement, being "For each pair of urns, one of them should have no unpinned black marbles" or equivalent:

All unpinned black marbles must be concentrated in a single jar

We will from now on refer to the jar with all the unpinned black marbles as the black jar, and to the other jars as the white jars.
We now know that the number of black marbles in the white jars are all equal (because they are all pinned), so the energy to move a marble from one jar to another is:
$W_{ij} = \frac{b}{t_j(t_j+1)} - \frac{b}{t_i(t_i-1)}$
This allows two jars to have at most a difference of one white marble between each pair. By consequence, there is only one single configuration possible for the white marbles in the white jars, namely distributing all of them equally, or giving some urns one extra if an equal distribution is not possible. This leaves only a single free parameter $\omega$ in our system, which is the number of white marbles in the white jars (the remainder is added to the black jar). For each system, the total energy can be calculated in the function of this variable, and then the maximal value can be selected.
Another approach is to check if moving a white marble from the white to the black jars increases the energy. The energy to move a white marble from the white to the heavy jars is:
$W_{ij} = \frac{b_P}{(b_P+b_W+\lceil\omega/(n-1)\rceil)(b_P+b_W+\lceil\omega/(n-1)\rceil+1)} - \frac{b_P+b}{(b_P+b+w-\omega)(b_P+b+w-\omega-1)}$
This will flip sign if the optimum is reached, so one can put it equal to zero to find the optimal omega.
Note that, unless in very specific edge cases, white marbles are always distributed, so the number of pinned white marbles rarely matters.

The original problem

In the original problem, there where no pinned marbles, all of our marbles are free. The number of jars also was two, leaving us with a single black and a single white jar. the total energy is thus
$\frac{\omega}{\omega} + \frac{w-\omega}{w-\omega +b} = 2- \frac{b}{w-\omega +b} $
This has no value if $\omega$ is zero, and is obviously larger is omega is smaller, so the optimal solution is $\omega=1$, which means that the optimal solution is equivalent to the solution found in the other sources.

The new problem

For the new problem, the energy can be optimized computationally.
Our starting problem had 2 urns, 50 marbles of each colour, and at least one black marble in each urn (also a white one, but this does not matter). Using this, one gets 12 white marbles and one black in the first urn, and 38 white with 49 blacks in the second.

Permutations of sequences

Imagine an infinite sequence of 3 objects, $A$, $B$, $C$, that has the following property:
For each permutation in the 3 objects $A$, $B$, $C$, if this permutation is applied to the sequence, the resulting sequence is a tail of the original sequence.
For example, if we have the sequence, $AABACBA...$, the permutations would be $BBABCAB...$, $CCBCABC...$, $BBCBACB...$, $AACABCA...$ and $CCACBAC...$ Each one of these must appear as a tail.
If you try this for a moment, you will soon discover that this is impossible. This is also quite easy to prove.
First off, the sequence must evidently contain all 3 objects, if not, the permutation that turns an object that is contained in an object that is not will not be displayed as any tail.
One can assume without loss of generality that the first element of the series is A. Now one can look at the permutations ABC->BCA and the permutations ABC->BAC. For each of these, a tail must exist, we can call the tails indices x and y. Because these elements are each the first element of there tail, they both have to be B (as both permutations project A to B). But if we look at element x+y, this element is both the x-th element of the "y" tail, as the y-th element of the "x" tail. So this element would have to be C, as well as A, which leads to a contradiction. Therefore such a sequence cannot exist.
If one considers a subset of permutations that are allowed, and generalise this to sequences with more possible elements, one can easily prove that a valid sequence exists if and only if the subset of permutations forms a cyclic group. The proof of this is left as an exercise to the reader.