Connecting Dots

Suppose we're given a 5 by 5 grid squared grid of nodes. We're told the bottom left point is the starting point. The second from the right on the bottom row is the finishing point. We have to travel to every node from the start to the finish, visiting all 25 nodes exactly once. We can travel from each node to a neighbouring node either by going horizontally or vertically one step. We cannot go diagonally.

So what path can we choose? Here is an example of a path we might try:

In that case, although we have successfully travelled from the start to the finish. We have skipped one node.
We can try lots of different paths and each time we find that something goes wrong. We can't get from the start to the finish visiting every node exactly once.
In fact it turns out it can't be done. And here's the proof:

Suppose we lable each node on the grid by its position (1,1) to (5,5). We deem a node to be odd if the sum of its two indices is odd. It is deemed to be even if the sum of its indices is even.
The starting node (1,1) is even since 1+1=2 is even.
The finishing node (4,1) is odd since 4+1=5 is odd.

Every step we take in the path will toggle from odd to even or even to odd, since in each step one index is changed by 1.
If we find a path to get to get from the start to the finish, we'll need to visit 25 nodes, that's 24 steps. So the final node will be even since the starting node was even. However we know that the final node is odd. So we have a contradiction. Hence no such path exists.
So you can spend as long as you like searching for a path, but you won't find one.

Using a Neural Network to solve a Rubiks Cube

In a standard 3x3x3 Rubik's cube, each of the 6 faces contain 9 squares. As a puzzle, it is deemed to be solved when each face just contains one colour, i.e. all the greens squares are on one face, all the blues on another etc.
Some people work out how to solve Rubik's cubes, but it is more common for people to memorize methodologies the others have published online and in books. Generally the algorithms that are relatively easy to remember involve many steps. A more advanced cuber will be able to find solutions with fewer steps. In speed cubing competitions, participants who can find a method of solving the cube with less steps will have an significant advantage.
In this article we'll describe how a neural network can be used to help find an efficient way of solving a Rubik's Cube. (Here's a link to the source code which uses Keras.)

Suppose we have a neural net which takes as input a vector X which represents the current state of a cube.
The output will be a vector Y with Y[i] = (probability that the cube can be solved in i steps) assuming a zero based indexing.
So if: \[\underline{Y}=(0,0,1,0,0, ..., 0)\] then we are 100% certain that the cube can be solved in 2 steps.
And if: \[\underline{Y}=(1,0,0, ..., 0)\] then it is a cube that can be solved in 0 steps, i.e. it is already solved.
We can create training data by starting with a solved cube and then randomly rotating the faces say n times. We then write a row in the training data file with the number n and the representation of the cube.
If you're interested in how this could be implemented in Java, then have a look at this code. On a regular laptop, it takes the code a few seconds to generate a training set with one million instances (rows).
The neural net that we built used a number of dense layers and then the last layer was softmax. It was implemented using Keras. The source code that we wrote can be found here.


How can the neural net be used to solve the cube?
Suppose the NN indicates that it can solve the cube in 8 steps. Then we can try 12 different rotations (each side of the six sides can be rotated either clockwise or anticlockwise). The neural net should then indicate that one of those options results in a cube that can be solved in 8-1=7 steps. And the other 11 can be solved in 8+1=9 steps. We choose the option that reduces the number of steps and then repeat until we have a solved cube.
In our first implementation the NN was very good at identifying if there were less than 6 steps to solve it. However if the solution involved more than 6 steps then it struggled.
One of the improvements we could make now is to use the NN to improve the quality of the training data.
When the training data is being generated, suppose one face is rotated consecutively 3 times clockwise. That could have been achieved with a single rotation anticlockwise. So the neural net may be able to find a faster way to solve the cube than is indicated in the data.
So we could apply the neural net to the input data and when shorter solutions are found, the data could be updated. The model can then be retrained with the improved data, which may enable the data to be improved even more.

Companies buying each other

What happens when two companies buy eachother's stock? Is it like when two snakes start eating eachother tail first?
In this blog post, we'll look into the mathematics of what is going on.
But let's start with a simple case of a company owning its own stock.
Suppose we have a stock price S, with a total of N shares issued, of which n are held by the company itself.
Let M be the value of the companies assets, excluding the shares that it holds in itself.
So we have the total valuation is the total number of shares multiplied by the share price, which is also equal to the valuation M plus the shares it holds in itself: \[S N = M + S n\] Rearranging, we have: \[M = S(N-n)\] So we can say that the main company's valuation M, is the share price times the adjusted number of shares: total number of shares less the number of shares that the company holds in itself.
So far so good.
On the other hand, if we were to let a company declare its own shares on its balance sheet and treat them as a regular asset, then we could have a company valuation of (N S) and the owners of shares in the company would have an odd recursive ownership. When they bought shares they would be buying fractional ownership of more shares that the company held and those shares would have a fractional ownership of more shares etc.
Indeed if the company held many of it own shares, we could end up with a valuation being a large multiple of the main assets M.
Suppose we have a company valuation: \[V=M + S n \] Using the equations above we have: \[S=\frac{M}{N-n}\] and so: \[V= M \left( 1 + \frac{n}{N-n} \right) =M \frac{N}{N-n}\] And in the limit as \(n \rightarrow N\) , the valuation of the company goes to infinity.
So, if we don't want to allow companies to give themselves infinite valuations, then we shouldn't let them declare the own stock on their balance sheet.

Suppose we have two companies and each buys stock in the other. Is this like a case of two snakes consuming eachother? If we look at the numbers, what happens to the company valuations and stock prices?

Let's label the companies 'a' and 'b'. We can say that the valuation of company 'a' is the number of outstanding shares times its share price. And we'll break that valuation into two parts, the main company and shares that the company holds in company 'b': \[N_a S_a = M_a + n_b S_b\] where company 'a' holds \(n_b\) shares in company 'b'.
We have a similar expression for company b which holds \(n_a\) shares in company 'a'. \[N_b S_b = M_b + n_a S_a\] If we add those two equations and rearrange a little, we find: \[M_a + M_b = S_a ( N_a - n_a) + S_b ( N_b - n_b)\] The equation suggests that the summed valuation of the main assets of the two companies is equal to the share price of each multiplied by the adjusted number of shares, which is total shares less shares owned by the other firm. Or in terms of corporate ownership, we can get full ownership of the two companies main assets \(M_a\) and \(M_b\) by buying the remaining share of each company that aren't already held by the other. That sounds reasonable.

Suppose now company 'a' decides to buy a few more share in company 'b', what impact will that have on the two share prices?
We let the investment that 'a' makes in 'b' be \(\delta I_b\). And suppose the price that it pays for each share is \(S_b\).
Company 'a' will need to get the cash for the shares from somewhere, so we need subtract \(\delta I_b\) from \(M_a\).
When the transaction is complete, we'll see what our equations suggest is the appropriate impact on the share price of companies 'a' and 'b'.
We'll let the adjusted share prices be \(S_a + \delta S_a\) and \(S_b + \delta S_b\). So we have a total valuation for company 'a': \[N_a ( S_a + \delta S_a) = M_a - \delta I_b + ( N_b + \delta N_b) ( S_b + \delta S_b)\] where the number of new shares in 'b' that 'a' purchased was: \[\delta N_b = \frac{\delta I_b}{S_b}\] After doing a little bit of algebra we find: \[N_a \delta S_a = N_b \delta S_b + \frac{\delta I_b}{S_b} \delta S_b \hspace{22 mm} eqn(1)\] In the case we are considering, company 'b' hasn't bought any new shares in company 'a', but we're interested to know if its valuation has been impacted, we have a valuation for company 'b': \[N_b ( S_b + \delta S_b) = M_b + n_a ( S_a + \delta S_a) \] Subtracting out the original valuation, we find: \[N_b \delta S_b = n_a \delta S_a \] And so: \[ \delta S_b = \frac{n_a}{N_b} \delta S_a \hspace{22 mm} eqn(2)\] We can substitute that into eqn(1), we find: \[N_a \delta S_a =(N_b + \frac{\delta I_b}{S_b} ) \frac{n_a}{N_b} \delta S_a \] So: \[ 0 = \delta S_a \left[ (N_b + \frac{\delta I_b}{S_b} ) \frac{n_a}{N_b} - N_a \right] \] And so we see that \[\delta S_a = 0\] and consequently, eqn(2) tells us: \[\delta S_b = 0\]
So, our model suggests that two firms buying shares in eachother doesn't cause price instability.

Latitude Longitude Distances

Suppose we have the latitude and longitude of two points on the earth's surface, then how can we work out the distances between them?
One approach would be to make the following assumptions:

• The earth is a sphere.
• We are interested in the distance along the earth's surface.
• Altitude can be ignored.
• The distance from the equator to either pole is 10,000 km.

To calculate the distance we could first find the cartesian coordinates of the two points. We set the origin to be the centre of the earth. For each point on the earth's surface: with latitude \( \phi \) and longitude \( \theta \): \[x = r cos( \phi ) cos ( \theta ) \] \[y = r cos( \phi ) sin ( \theta ) \] \[z = r sin(\phi )\]

If we have two points A and B, with coordinates \( (x_a, y_a, z_a) \) and \( (x_b, y_b, z_b) \)
then we can use a 3 dimensional version of the Pythagorean theorem to determine (d) the straight-line distance between the points using the equation: \[ d^2 = (x_a - x_b)^2 + (y_a - y_b)^2 + (z_a - z_b)^2 \] But that distance is not quite the answer that we are looking for. We seek the distance along the surface of the earth, not the straight-line distance which cuts through the earth.

We let the angle between the points be \( \lambda \), when we know that, we can multiply it by the radius to get the distance along the surface, which is the arc-length.
Looking at the diagram above we can see that: \[sin ( \lambda / 2) = \frac{d/2}{r} \] and so we can evaluate \( \lambda \) using: \[ \lambda = 2 arcsin \left( \frac{d}{2r} \right) \]
Now it is time to try out some numbers:

Inputs
	Latitude	Longitude
Point A
Point B
Result
Distance		km

If you change one of the inputs above and hit enter, then the result will be updated.
The latitude figures are degrees north of the equator. For degrees south, use a negative.
The longitude figures are the degrees west of the prime meridian. For degrees east use a negative number.

If you're interested in the javascript code used to do the calculation, then have a look at this in github.

An alternative approach is to use the Haversine formula.

A Bit of Algebra

In this blog post we're going to look at finding the real positive x such that: \[x^{x^3} = \frac{1}{2^{1/6}} \hspace{10 mm} (Equation 1)\]
By all means, do have a go at solving it, before reading our solution below.

The first, slightly non-obvious step is to raise both sides of the equation to the power of 3: \[ \left( x^{x^3} \right)^3 = \left( \frac{1}{2^{1/6}} \right)^3 \] Rearranging that a bit, we have: \[ x^{3x^3} = \frac{1}{2^{3/6}} \] And so: \[ \left( x^3 \right) ^{x^3} = \left( \frac{1}{2} \right) ^ {1/2} \hspace{10 mm} (Equation 2) \] If \[ a^a = b^b \] then we have a solution: \[a=b\]
So, returning to Equation 2, we have: \[x^3=1/2 \] And hence: \[x=\frac{1}{2^{1/3}} \] So, we have a solution to equation 1. But are there any others?
In fact, it is possible have \[ a \neq b \] when \[ a^a = b^b \] For example: \[ \left( \frac{1}{4} \right)^{1/4} = \left( \frac{1}{2} \right)^{1/2} \] So, returning to equation 2, we can see that another solution for x is when: \[ x^3 = \frac{1}{4} \] And hence: \[ x = \frac{1}{2^{2/3}} \] So, our solutions for x are: \[ \frac{1}{2^{1/3}} \hspace{4 mm} and \hspace{4 mm} \frac{1}{2^{2/3}} \] But are there other solutions?
If we let \[ z=x^3 \] then, returning to equation 2 we have: \[ z^z= \frac{1} {\sqrt{2}} \hspace{10 mm} \] We can plot \(z^z \) for positive z:

We can see that \(z^z\) decreases in the range 0 to 1/e, after that it increases and keeps on increasing. So for positive z, we will have a maximum of two solutions to \( z^z = k\), where k is some constant. We have two solutions already, so we now know there aren't any more,
unless of course we want to investigate negative or complex solutions...

Catching Raindrops

Suppose we know the area of a country and the average annual rainfall. And then suppose that we also know the population and the daily water consumption, then we can work out what proportion of drops of rain that fall need to be captured for use by people.
We convert the daily consuption to annual and then compare the volume of water that is consumed with the volume of water that falls as rain.

Inputs
Population		people
Average Water Consumption		litres per person per day
Land Area		square kilometers
Rainfall		meters per year
Result
Proportion of raindrops to catch		%

(If you change one of the inputs above and hit enter, then the result will be updated.)

Singapore has approximately a population of 5.9 million people, they use 141 litres of water per person per day. The land area is small: 729 sq km, their annual rainfall is about 2.2 meters. So if they captured 19% of the raindrops then they'd meet their water needs.
On the other hand, Ireland has a slightly smaller population but much larger land area and so they only need capture a much lower proportion of their raindrops.

Pumped Storage Power Calculations

Suppose a country had some good sources of intermittent renewable energy, perhaps tidal which is nice and predicatable or wind which is much less foreseable. Either way, one approach to achieve a consistant supply would be to store the energy produced and then release it on demand. A pumped storage power station may be appropriate. It consists of pairs of lakes which are relatively close by eachother, though there is a significant altitude difference between the lakes. One or both of the lakes may be man-made. When there is excess supply of electricity, water is pumped from the low lake to the high lake. On the other hand, when there is excess demand, water flows from the high lake to the low lake, passing through a generator and so it produces electricity.

Now, let's look into how much energy could be stored.
The potential energy stored is Mgh:
where g is the acceleration due to gravity.
h is the height of the high lake above the low lake.
M is the mass of water, which is evaluated by multiplying the volume of one lake times the density of fresh water (1,000 kg per cubic meter).
We'll also introduce an efficiency factor because the system won't be perfectly efficient.

Inputs
Population		people
Average Power Per Person		Watts
Lake Radius (r)		meters
Lake Depth (d)		meters
Altitude Difference (h)		meters
Efficiency		%
Number of Lake Pairs
Results
Annual Energy Consumption		TW hours / year
Energy Stored		TW hours
Days of Energy Stored		days.

(If you change one of the inputs above and hit enter, then the results will be updated.)

If we were to use tidal power, which goes through almost 2 complete cycles per day, then we may need about half a day's worth of demand to be stored, which may be achievable with a series of pumped storage power stations. On the other hand, if we were to try to rely on wind as the sole energy source and we wanted to store enough energy to see us through say six weeks of calm weather, then the number of pumped storage power stations required is likely to be unacceptably large.

Now suppose we choose to harness tidal power. One approach would be to put a sea-wall across the entrance to some bays or inlets. Let the water flow in as the tide rises. The sea water is then blocked as the tide starts to ebb. To extract a maximum amount of energy from this, we would wait until the tide at its lowest point and then instantaneously release all the sea water, passing it through a generator. But it is likely to be much more practical to release the water before low-tide. Also if we want to use much of the electricity as it is being used, then we would want the generation of electricity to continue through much of the tidal cycle.

We can set a target of what proportion of our energy needs we want to come from tidal and then we can work out what area of the sea needs to be put behind sea walls with tidal generators.
In a 27 day lunar cycle we have 2 tides per day due to the spin of the earth, less 2 tides due to orbit of the moon. For now we won't go into the details of why that's true. But our statement here is that we have 2 * ( 27 - 1 ) tides in 27 days, i.e. 1.93 tides per day. So a tidal cycle is (24 / 1.93) hours = 12.44 hours. But we can generate power both as the tide flows in and as the tide flows out. So we'll use the half tidal period which is a little over 6 hours.

The target amount of energy to generate in a half tidal cycle is:
population * powerPerPerson * durationOfHalfTidalCycle * targetTidalPowerProportion.
On the other hand we see how much energy is available from the tidal movement using the equation:
Potential Energy: E= Mgh
In this case M is the mass of the sea water which is the area times the tidal height times the density of sea water (approximately 1030 kg per cubic meter).

So we can evaluate the area of sea that is required:

Inputs
Tidal Height		meters
Tidal Power Efficiency		%
Proportion of Total Energy from Tidal		%
Result
Sea Area Required		square KM

(Once again, if you change the inputs and hit enter, then the result will update.)

Tidal power is something that can provide predictable renewable energy. However, a significan area of sea needs to be harnessed.