Volume of tetrahedron limited by 4 planes

Consider the following puzzle:

Calculate the volume of a tetrahedron enclosed by the following 4 planes
$$a_1x+b_1y+c_1z+d_1=0\\a_2x+b_2y+c_2z+d_2=0\\a_3x+b_3y+c_3z+d_3=0\\a_4x+b_4y+c_4z+d_4=0$$

The easiest way to calculate this volume is by applying a linear transformation to the tetrahedron where the planes of the tetrahedron align to the coordinate planes. It is impossible to find a purely linear transformation that does this, as all linear transformations project the origin, to the origin, but it is possible to find a linear transformation, followed by a translation, to do this. As translations do not change the volume, this will not pose any unsolvable issues.

An example of such a transformation is

$$u=a_1x+b_1y+c_1z+d_1\\v=a_2x+b_2y+c_2z+d_2\\w=a_3x+b_3y+c_3z+d_3$$

To find the transformation of a given plane, one has to add the equation of the plane to the system of equations of the transformation. For example, for the first plane this becomes:

$$u=a_1x+b_1y+c_1z+d_1\\v=a_2x+b_2y+c_2z+d_2\\w=a_3x+b_3y+c_3z+d_3\\0=a_1x+b_1y+c_1z+d_1$$

Or solved: $u=0$. So the first plane matches the $vw$-plane.

This is analog for the two next planes, but things become interesting for the last plane, where the system becomes:

$$u=a_1x+b_1y+c_1z+d_1\\v=a_2x+b_2y+c_2z+d_2\\w=a_3x+b_3y+c_3z+d_3\\0=a_4x+b_4y+c_4z+d_4$$

Now, in our $uvw$ space, we have a tetrahedron enclosed by the coordinate planes, and a 4th plane that is the solution of the above equation. Tetrahedra enclosed by all 3 coordinate planes have the following vertices: $$(0,0,0), (u,0,0), (0,v,0), (0,0,w)$$ Each of these points can be found by solving the system of equations of 3 of the 4 planes. 

Using the first 3 planes obviously gives (0,0,0) as a solution.

Using all of them except the first gives us:

$$u=a_1x+b_1y+c_1z+d_1\\v=a_2x+b_2y+c_2z+d_2\\w=a_3x+b_3y+c_3z+d_3\\0=a_4x+b_4y+c_4z+d_4\\v=0\\w=0$$

This easily simplifies to 

$$u=a_1x+b_1y+c_1z+d_1\\0=a_2x+b_2y+c_2z+d_2\\0=a_3x+b_3y+c_3z+d_3\\0=a_4x+b_4y+c_4z+d_4$$

If we call:

$$A_1 =\left[ \begin{matrix} a_1&b_1&c_1&1\\a_2&b_2&c_2&0\\a_3&b_3&c_3&0\\a_4&b_4&c_4&0\end{matrix}\right]\\A_2 =\left[ \begin{matrix} a_1&b_1&c_1&0\\a_2&b_2&c_2&1\\a_3&b_3&c_3&0\\a_4&b_4&c_4&0\end{matrix}\right]\\A_3 =\left[ \begin{matrix} a_1&b_1&c_1&0\\a_2&b_2&c_2&0\\a_3&b_3&c_3&1\\a_4&b_4&c_4&0\end{matrix}\right]\\A_4 =\left[ \begin{matrix} a_1&b_1&c_1&0\\a_2&b_2&c_2&0\\a_3&b_3&c_3&0\\a_4&b_4&c_4&1\end{matrix}\right]$$

$$D = \left[\begin{matrix} d_1\\d_2\\d_3\\d_4 \end{matrix}\right]$$

$$X = \left[\begin{matrix} x\\y\\z\\-u \end{matrix}\right]$$

The system can be rewritten as

$$A_1X+D=0$$

$$X=-A_1^{-1}D $$

Now as 

$$u =  -\left[\begin{matrix} 0&0&0&1 \end{matrix}\right]X$$

$$u =  \left[\begin{matrix} 0&0&0&1 \end{matrix}\right]A_1^{-1}D$$

$$u =  \frac{1}{\det{A_1}}\left[\begin{matrix} 0&0&0&1 \end{matrix}\right]\text{adj}{A_1}D$$

As the bottom row of $\text{adj}{A_1}$ equals

$$\left| \begin{matrix}a_2&b_2&c_2\\a_3&b_3&c_3\\a_4&b_4&c_4\end{matrix}\right|;\left| \begin{matrix} a_1&b_1&c_1\\a_3&b_3&c_3\\a_4&b_4&c_4\end{matrix}\right|;\left| \begin{matrix} a_1&b_1&c_1\\a_2&b_2&c_2\\a_4&b_4&c_4\end{matrix}\right|;\left| \begin{matrix} a_1&b_1&c_1\\a_2&b_2&c_2\\a_3&b_3&c_3\end{matrix}\right|$$

Then 

$$\left[\begin{matrix} 0&0&0&1 \end{matrix}\right]\text{adj}{A_1}D = d_1\det{A_1}+d_2\det{A_2}+d_3\det{A_3}+d_4\det{A_4}$$

If one defines:

$$M =\left[ \begin{matrix} a_1&b_1&c_1&d_1\\a_2&b_2&c_2&d_2\\a_3&b_3&c_3&d_3\\a_4&b_4&c_4&d_4\end{matrix}\right]$$

Then is

$$u = \frac{\det{M}}{\det{A_1}}$$

Analog is 

$$v = \frac{\det{M}}{\det{A_2}}\\w =\frac{\det{M}}{\det{A_3}}$$

Now the volume of the tetrahedron is the surface area of one of the faces time the height divided by 3, so if one takes the face to be the $vw$-plane, the volume is

$$\frac{u}{3} \times \frac{vw}{2} =  \frac{uvw}{6}$$

In $uvw$ space. In $xyz$ space the volume has to be divided by the Jacobian:

$$\left| \begin{matrix} a_1&b_1&c_1\\a_2&b_2&c_2\\a_3&b_3&c_3\end{matrix}\right|$$

which is $\det{A_4}$ so the final volume becomes:

$$\frac{\det{M}^3}{6\det{A_1}\det{A_2}\det{A_3}\det{A_4}}$$

Or expanded:

$$\frac{{\left| \begin{matrix} a_1&b_1&c_1&d_1\\a_2&b_2&c_2&d_2\\a_3&b_3&c_3&d_3\\a_4&b_4&c_4&d_4\end{matrix}\right|^3}}{6\left| \begin{matrix}a_2&b_2&c_2\\a_3&b_3&c_3\\a_4&b_4&c_4\end{matrix}\right|\left| \begin{matrix} a_1&b_1&c_1\\a_3&b_3&c_3\\a_4&b_4&c_4\end{matrix}\right|\left| \begin{matrix} a_1&b_1&c_1\\a_2&b_2&c_2\\a_4&b_4&c_4\end{matrix}\right|\left| \begin{matrix} a_1&b_1&c_1\\a_2&b_2&c_2\\a_3&b_3&c_3\end{matrix}\right|}$$

 

Black hole

I created an implementation of an markov chain tree search artificial intelligence of the game black hole, designed by David Bodycombe.

The rules and explanation of the game can be found here:https://www.youtube.com/watch?v=zMLE7a3faI4

This is a small applet that runs the game. Click the hexagons to place the correct token there. 

 

This version makes 100 checks. If it doesn't work in the iframe, you can also open the applet here

The github repository can be found here:https://github.com/thorvalddox/blackhole

An if the above AI is to easy to beat, the following pages are the same applet with increased difficulty:

1000 checks

10000 checks

100000 checks

Note that this might get very slow to run, as the full program runs in your browser.

Number theory solution to coin problem

In my previous post, I described different ways to solve the coin change problem. This post describes the last method in more detail. The code for this method can be found here 

The method is based on generating functions, where we encode the total money in the exponent and the number of ways to encode them in the coefficient.

If we only have a single coin (with value $n$) and we are obligated to take $a$ coins, there is only one total value to create being $an$, so the generating function is:

$$x^{an}$$

If one can take multiple values, it is easy to see that the single values have to be summed, so

$$x^{an} + x^{bn} + x^{cn}$$

As this encodes, there is one way to get $an$, one to get $bn$ and one to get $cn$. If the number of coins is completely free, gene generating function becomes by consequence:

$$\sum_{i=0}^{\infty} x^{in} = \frac{1}{x^n-1}$$

As adding the values of different coins is equivalent to adding the exponents, which is equivalent to multiplying, combining multiple coins is equivalent to multiplying the generating functions. So if we have coins with values $c_1, c_2, ... \in S$, out generating function becomes

$$\prod_{c \in S} \frac{1}{x^c-1}$$

In the real numbers, the expression $x^c -1$ cannot be unbound in factors of the form $x-a$, so we have to consider our polynomial in a field that does allow this. An obvious extension would be the complex numbers, but to make calculations easier and more exact, we are going to use modular rings.

Note that by using this method, we will only get a final result modulo our prime, so our prime has to be selected large enough so that this doesn't matter.

Coin change 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...

This is a classic dynamic programming exercise, and I will explain a couple of ways to solve this problem.

First, let us translate the problem to mathematical notation:

$$f : \mathbb{N} \times [\mathbb{N}] \rightarrow \mathbb{N}$$

$$f(m,S) = \#\left\{\mathcal{S}(X) \subset S \middle| \sum X = m \right\}$$

Note that we are using braces for sets, brackets for multisets, $\mathcal{S}$ for the support function and # for cardinality.

Brute force method

The most intuitive approach is to check all possible multisets, calculate the sum, and check the sum equals the desired change. But as the number of possible multisets are infinite, this is impossible. Therefore, we will have to limit our possible multisets. One can easily see that the multiplicity of each coin has to be smaller or equal than $m/c$, with $m$ the total money and $c$ the value of the coin, limiting the total number of possible multisets to:

$$\prod_{c \in S} \frac{x}{c} =  m^n\prod_{c \in S} \frac{1}{c}$$

example scala code:

def gridScan(base:Int,mx:Int): List[List[Int]] = {
  if (mx==1)(0 until base).map(x => List(x)).toList
  else (0 until base).map(x => gridScan(base,mx-1).map(y => x :: y))
    .toList.flatten.toList
}
def change(money: Int, coins: List[Int]) : Int = {
  gridScan(money/coins.min + 1,coins.length)
    .map(x => (x zip coins)
      .map{ Function.tupled(_ * _)}.sum)
    .count(_==money)
}

The time order of this method is by consequence $O(m^n)$

Weak simplex method

Let us consider a hyperspace where each axis is the multiplicity of a specific coin. Each point in this hyperspace can be mapped to the analytic continuation of the total money that this coin makes. So, if we call $c_1,c_2, ...$ the values of the coins and $x_1,x_2, ...$ the multiplicities, then is $$\sum x_ic_i$$ the total value. Therefore, one can just check all integer multiplicities where $$\sum x_ic_i \le m$$. One could also go for equality, but solving this exact equation is harder than checking for inequality, so for this method, we use the inequality. 

As this method gives no efficient way to calculate the allowed integer multiplicities, no code is provided.

The time order of this method is $O\left(\frac{m^n}{n}\right)$

Recursive method

We can build a way to construct a multiset as follows:

1. select a coin with a value smaller or equal then the remaining amount of money.
2. subtract the value of the coin for the pool of money.
3. If you still have money, repeat.

Note that the solutions of this algorithm are not distinct, but this can easily be solved by only allowing coins that are smaller or equal then the coins selected in previous iterations.

Now, the number of ways that this algorithm can be applied is also the number of possible combinations. 

This can be transformed into a recursive function. 

$$f(m,S) = \sum_{y \in S} f(m-y,S| y \ge m) $$

We can forgo the check if $y \le m$ by defining $f(m,S) = 0$ for $m <0$

Note that this method checks all possibilities defined in "weak simplex method", so it has the same computational complexity, but this method describes how to actually scan them. 

example scala code:

def change(money: Int, coins: List[Int]) : Int = {
  if (money < 0) 0
  else if (money == 0) 1
  else coins.map(x => change(money-x,coins.filter(y => y>=x))).sum
}

Strong simplex  method

If we call $c_1,c_2, ...$ the values of the coins and $x_1,x_2, ...$ the multiplicities, then for all solutions is $$\sum x_ic_i = m$$. So the value of the smallest coin can be extracted as $$x_0 = \frac{m-\sum_{i>0} x_ic_i}{c_0}$$

This simplifies the system to the weak simplex method with one dimensionless, so one can apply the same recursive formula.

$$f(x,S) = \sum_{y \in S \setminus x_0} f(m-y,S| y \ge m) + (x|m) $$

the scala code for this method is

def change(money: Int, coins: List[Int]) : Int = {
  if (money < 0) 0
  else if (money == 0) 1
  else coins.tail.map(x => change(money-x,coins.filter(y => y<=x))).sum + 
    (if (money % coins.head == 0) 1 else 0)
}

The time order of this method is $O\left(\frac{m^{n-1}}{n}\right)$

Dynamic programming method

Instead of using the amount of money as a breakdown for our induction, one can use the number of coins as an induction value. If we add a new coin to the set, the number of multisets can be calculated from the old ones. This does not change the recursive formula in any way, but allows us the first calculate all the values for a single coin, if we save these, we can calculate all the values for two coins based on the single one and so on. This means that the runtime of the algorithm is $O(nm)$, which is way faster. (although the runtime is practice is very similar as, even if the recursive tree is exponential, the number branches that are reached are in the same magnitude)

The Scala code is as follows:

def change(money: Int, coins: List[Int]) : Int = {

  if (money < 0) return 0
  if (coins.isEmpty) return 0

  val dp = new Array[Int](money + 1)
  dp(0) = 1
  var i = 0
  while (i < coins.length) {
    var j = coins(i)
    while (j <= money) {
      dp(j) += dp(j - coins(i))

      j += 1
    }

    i += 1
  }
  return dp(money)
}

Note that if one would clean this code up to be more scala-like, it will reduce itself to a recursive function very similar to the one described above, and less efficient.

Generating function method

It is easy to see that

$$\prod_{c \in S} \sum_{i \rightarrow \infty} x^{ic}$$

Will generate the number of denominations for a specific coin value for each coefficient, independent of the rings over which the polynomial is placed. 

This expression can with Taylor series be simplified to 

$$\prod_{c \in S} \frac{1}{1-x^{ic}} = (-1)^{\#S} \frac{1}{\prod_{c \in S} x^{ic} - 1}$$

As $$x^a - 1 = \prod_{i=0}^{i<a} x-e^{w_a^i}$$

With $w_a$ the $a$-th root of unity 

So if the set $$T = \{ \forall a \in S \forall i < a\}$$

Then our formula simplifies to 

$$(-1)^{\#S} \frac{1}{\prod_{c \in T} x - t}$$

This formula can be simplified using partial fraction decomposition.

$$(-1)^{\#S} \sum_{t \in T} \frac{1}{i!(x - t)^{s-i}} \frac{d^i}{dp^i} \frac{(p+t)^s}{\prod_{c \in T} p - c} $$

Where $s$ is the total multiplicity and $i$ is the counting multiplicity.

Complex generating function method

In the complex field, the roots of unity are

$$2\imath \pi/a$$

So we can plug this in in our formula for $T$

Even though the formula looks horrible, it only scales in complexity with the size of $T$, so the speed is $O(ns)$ (with $s$ the size of the largest coin), so for very large amounts (like millions), this formula will be faster. 

The main drawback with this method is that small floating points errors propagate enormously(due to all divisions and powers), and as the algorithm runs, these can become larger then 1, and thus give the wrong result, even if the math is correct. This is why we would prefer a field that has no problems from floating-point arithmetic. 

Number theory generating function method

Let's take as field the $p$-modulo rings such that $p-1$ is a multiple of all coins. According to the Dirichlet theorem, for every number a prime of the form $kn+1$ exists, so also for the least common multiple of all coins, so this field exists. As $p$ is prime, it as a Primitive root, and all roots of unity can be written as:

$$g^{(p-1)/a}$$ with $g$ the primitive root and $a$ the multiplicity of the root (which is the value of the coin). 

The method of partial fractions does not work as derivatives are not defined over this field, but as this field gives a nice linear equation if one uses the method of undetermined coefficients, the problem is actually easier than this. 

This algorithm has a slower running time than the above, it is even exponential (as primetest is exponential), but in practice this will run exact and fast for large numbers.

The code will follow in the future. 

I based most of my methods on this post: https://stackoverflow.com/Questions/4243831/how-to-count-possible-combination-for-coin-problem

Probabilistic Moore's statements

This blog is a followup on my previous blog here, if you have not read that, go read it first.

The previous axioms introduce a new paradox, the Preface Paradox, and to fix this paradox we have to forgo the assumption that all beliefs are true or false, and go to a probabilistic model.

Using fuzzy logic the following operators are defined:

$$a \land b = ab$$

$$a \lor b = a+b-ab$$

$$a \oplus b = a+b-2ab$$

$$\lnot b = 1-b$$

All these operators are closed in the unit interval $\mathbb{I}$ and consistent with De Morgan's laws.

A universe is defined the same way as before, but probabilistic statements are defined as follows:

$$P: U \rightarrow \mathbb{I}$$

Not that normal statements still exist, and are defined as follows:

$$S: U \rightarrow {T,F}$$

And let's also define 

$$\Omega: S \rightarrow P$$

The space of all statement transformations, which turns a statement into how sure we are of the statement.

Now define:

$$\forall x \in \mathbb{I}, \forall p in S: F_x(s)(u) := 

\begin{cases}

    1,& \text{if } p(u) = x\\

    0,& \text{otherwise}

\end{cases}

$$

This function turns a probabilistic statement, for example 'it will rain tomorrow', into a normal statement, "I am 90% sure it will rain tomorrow". If there was indeed a 90% chance, the new statement will have a 100% chance to be true, otherwise it will be zero. Call this function the fuzzy function.

Note that our beliefs only apply to deterministic states, and not to probabilistic states, as it is nonsensical to clarify a belief in a probabilistic statement. For example, I am 60% sure I am 90% sure is, while mathematically valid, not something I would constitute as a belief.

Now that we have these to sets we can read our new axioms. Call the subset of $\Omega$ that matches these axioms $M$

Now is $m \in M$ if

1. $m$ is reasonable:
   $$\forall x \in \mathbb{I}:m(\bar{T}) = C_1$$
   
2. $$\forall x \in \mathbb{I}:m(\bar{F}) = C_0$$
3. $m$ is consistent:
   $m$ is distributive with $\land,\lor,\lnot,\oplus$
4. $m$ is self-conscious:
   $$m(F_x(m(s))) = F_x(m(s))$$
   

The function $F_1 \circ m$ is equivalent to the belief function of previous blog, and by stating things like, I am quite sure, $F_{0.95} \circ m$, also works, and has no problem with the Preface Paradox.

An extention to Moore's statements

This post is a sequel to my previous post here. If you have not read it, read that one first.

In the previous post we assumed that there was a single belief function. But peoples belief can change over time and differ between people, so one should create a belief function for each person for each point in time.

Image one changes Moore's statement to use a different time or person, for example "it is raining but you don't belief it is raining" or "it was raining but I did not belief it was raining". It is obvious from the text that this is not a contradiction of an absurdity. The math reflects this:

$$M_1(s) \land M_1(M_2(s))$$

As there are two different belief functions, the self-consiousness axiom does not apply, and this cannot be reduced further, making this statement undecided.

Now that we have a working framework, one can build more Moore's statements. For example:

$$s \oplus M(s)$$

This translates to "I do not belief this statement", which looks like the classic liars paradox, but isn't a paradox, and can be true or false. But If one checks if the person who tells the statement beliefs it, one gets the following.

$$M(s) \oplus M(M(s)) = \bar{F}$$

Which is a contradiction.

A solution to Moore's paradox

Moore's paradox describes the so called Moorian sentences, like for example "It is raining but I don't believe it is raining". These are statements that can be true, and are logically consistent, yet seem (and are) absurd. But if we mathematically formalise what "believing" means, we can see the source of the paradox appear bright as day.

Lets start with some definitions:

$U$ is the set of all states of the universe. This is a set of custom objects, and does not have any other properties. 

A statement is defined as the following.

$$U \rightarrow {T,F}$$

So, for example, 'it is raining', is a statement, so it is a function that takes the current state of the universe, and converts it to either true or false, dependant on the actual state (so if it is actually raining). Call the set of all statements $S$.

Statements have the following operations:

$$\forall u \in U, \forall s,t \in S$$

$$(s \land t)(u) := s(u) \land t(u)$$

$$(s \lor t)(u) := s(u) \lor t(u)$$

$$(\lnot s)(u) :=  \lnot s(u)$$

So the classical operations on booleans also apply on statements.

Now, consider two special statements, the Tautology and the Contradiction:

$$\forall u \in U: \bar{T}(u) := T$$

$$\forall u \in U: \bar{F}(u) := F$$

We call a statement undecided if it is not a Tautology nor a Contradiction.

A belief is a function who takes a statement, for example 'it is raining' and retuns a different statement, 'I believe it is raining'.

Formally:

$$M: S \rightarrow S$$

It has by axiom the following properties:

1. Reasonability:
   $$M(\bar{T}) = \bar{T}$$
   One always believes a tautology to be true.
2. Consistency
   $$M(s \land t) = M(s) \land M(t)$$
   $$M(\lnot s) = \lnot M(s)$$
   If I believe that "apples are red" and I believe that "bananas are yellow", I believe that "Both apples are red and bananas are yellow". In addition, if I believe apples are not red, I do not believe apples are red.
3. Self-conciousness
   $$M(M(S)) = M(S)$$
   If I believe that apples are red, I believe that I believe that apples are red.

Now, lets call a statement a triviality if the believe function of the statement is a tautology, and an absurdity if the belief of the statement is a contradiction.

Each contradiction is by the reasonability axiom an absurdity, but this property is not symmetric.

Looking back at Moore's paradox. If we call the statement, 'it is raining' $s$, then Moore's paradox states:

$$s \land \lnot M(s)$$

This statement can obviously be true. But if we apply the believe function to this statement it becomes:

$$M(s \land \lnot M(s) )= M(s) \land \lnot M(M(s)) = M(s) \land \lnot M(s) = \bar{F}$$

So, the statement, while it can be true, can never be believed, and is thus absurd. In short, the reason Moore's statement seems absurd is not because it cannot be true, but because the person stating it can never believe it.