Packing Problems

Easy to state and hard to solve problems make mathematics interesting. Packing problems are one such type. In fact there is a very nice Wikipedia article on this topic:

 Packing problems involve attempting to pack objects together into containers. The goal is to either pack a single container as densely as possible or pack all objects using as few containers as possible.

I came across this problem a couple of years ago, while watching the following TED Talk by Eduardo Sáenz de Cabezón:

In this talk, the object of attraction is the Weaire-Phelan structure made from six 14-hedrons and two dodechedrons. This object is believed to be the solution of Kelvin’s problem:

How you can chop 3d space into cells of equal volume with the minimum surface area per cell?

The packing problem for higher dimensions was in news last year, since a problem about “Densest Packing Problem in Dimensions 8 and 24” was solved by a young mathematician (Maryna Viazovska). The mathematics involved in the solution is very advanced but we can start gaining knowledge from this book:

A classic reference in this field by two well known geniuses.

Recently, while reading Matt Parker’s book, I discovered a wonderful website called Packomania by Eckard Specht (Otto-von-Guericke-Universität Magdeburg) containing data about packing problems in 2D and 3D. (also checkout his Math4u.de website, it’s a good reference for elementary triangle geometry and inequalities problems.)

Screen-shot of Dr. Eckard Specht’s homepage, his online problem collection (with solutions; each problem in GIF, PS and PDF formats) and Packomania.

Computers also have a role to play in solving such optimization problems For example, in 2015 Thomas Hales formally proved Kepler’s Conjecture about 3D packing:

No arrangement of equally sized spheres filling space has a greater average density than that of the cubic close packing (face-centered cubic) and hexagonal close packing arrangements.

using HOL Light proof assistant.

The proof was a huge collaboration and was called Flyspeck Project. The details about this proof are available in this book:

NOTE: You can construct your own Truncated octahedron and Weaire-Phelan polyhedra by printing the nets available at Matt Parker’s website.

Clocks

Clocks are amazing. They tell us time. In this post I want to talk about working of analog clocks. In case you haven’t seen an analog clock, this is how it looks like:

 

 

A wall clock, it’s working part in the back and inside of the working part.

But, what clocks have to do with mathematics? As I have mentioned several times, one major part of mathematics is about counting and clocks “count”! Clocks are amazing counting device, they perform mod 12 and mod 60 calculations (that’s why modular arithmetic is also called clock arithmetic).

Unfortunately, the ideal cases exist only in our abstract world of mathematics. In real world, whatever we build has some error percentage and our motive to minimize this error. A mathematical construction, called Stern-Brocot tree, was created to help build timepieces and understand number theory.

By Aaron Rotenberg (Own work) [GFDL or CC-BY-SA-3.0], via Wikimedia Commons

This “tree” gives an exceptionally elegant way to enumerate the positive rational numbers and is a surprisingly useful tool for constructing clocks.  For more information about this construction read this feature column article by David Austin.

Just like continued fractions, this tree gives us good rational approximations of a given real number. Clocks typically have a source of energy–such as a spring, a suspended weight, or a battery–that using gears turns a shaft at a fixed rate. We can increase the precision by using more number of gears of different teeth count in appropriate combination.

I will end this post with an example from Austin’s article:

Suppose we place a pinion on a shaft that rotates once every hour and ask to drive a wheel that rotates once in a mean tropical year, which is 365 days, 5 hours, 49 minutes. Converting both periods to minutes, we see that we need the ratio 720 / 525,949. The problem here is that the denominator 525,949 is prime so we cannot factor it. To obtain this ratio exactly, we cannot use gears with a smaller number of teeth. It is likewise impossible to find a multi-stage gear train to obtain this ratio. But, as we slide down the “tree” toward 720 / 525,949, the rationals we meet along the way will give good approximations with relatively small numerators and denominators. As we descend the Stern-Brocot tree towards 720 / 525,949, we find the fraction 196 / 143,175, which may be factored into four rational factors, 2/3, 2/25, 7/23 and 7/83. We can therefore construct a four-stage gear train and can get a pretty accurate clock.

I hope I have been able to convince you that clocks are much more interesting than they would appear and you should read the article by David Austin for further references.

Arithmetic Operations

There are only 4 binary operations which we call “arithmetic operations”. These are:

• Addition (+)
• Subtractions (-)
• Multiplication (×)
• Division (÷)

Reading this fact, an obvious question is:

Why only four out of the infinitely many possible binary operations are said to be arithmetical?

Before presenting my attempt to answer this question, I would like to remind you that these are the operations you were taught when you learnt about numbers i.e. arithmetic.

In high school when is introduced, we are told that real numbers are of two types: “rational” and “irrational”. Then in college when is introduced, we should be told that complex numbers are of two types: “algebraic” and “transcendental“.

As I have commented before, there are various number systems. And for each number system we have some valid arithmetical operations leading to a valid algebraic structure. So, only these 4 operations are entitled to be arithmetic operations because only these operations lead to valid algebraic numbers when operated on algebraic numbers.

Now this leads to another obvious question:

Why so much concerned about algebraic numbers?

To answer this question, we will have to look into the motivation for construction of various number systems like integers, rational, irrationals, complex numbers… The construction of these number systems has been motivated by our need to be able to solve polynomials of various degree (linear, quadratic, cubic…). And the Fundamental Theorem of Algebra says:

Every polynomial with rational coefficients and of degree n in variable has n solutions in  complex number system.

But, here is a catch. The number of complex numbers which can’t satisfy any polynomial (called transcendental numbers) is much more than the number of complex numbers which can satisfy a polynomial equation (called algebraic numbers). And we wish to find solutions of a polynomial equation (ie.e algebraic numbers) in terms of sum, difference, product, division or root of rational numbers (since coefficients were rational numbers). Therefore, sum, difference, product and division are only 4 possible arithmetic operations.

My previous statement may lead to a doubt that:

Why taking root isn’t an arithmetic operation?

This is because it isn’t a binary operation to start with, since we have fixed . Also, taking root is allowed because of the multiplication property.

CAUTION: The reverse of root is multiplying a number with itself m times and it is obviously allowed. But, this doesn’t make the binary operation of taking exponents, where and are algebraic numbers, an arithmetic operation. For example, is transcendental (called Gelfond–Schneider constant or Hilbert number) even though 2 and are algebraic.

Making Math GIFs

Few months ago I wrote about the technologies we use today to share joy of mathematics. But, I overlooked one very important tool which we can use today: Graphics Interchange Format (GIF). For example, see this Tumblr blog: matan-matika.

Though I used this “technology” in one of my posts earlier this year, I didn’t know how to create my own animated GIF images.  So I started searching and stumbled on an HTML5 application by Pascal Bauermeister called MathVision . It is capable of generating mathematical art pictures using the contour plot technique. It uses simplified Java syntax and can be easily learnt by following this Instructable.

As an exercise in this Instructable, we are asked to make diagonal stripes, here is my attempt:

WIDTH = 350;
RATIO = 1;
X_MIN = 0; X_MAX = 10;
Y_MIN = 0; Y_MAX = 10;

color rgb(x, y) {
  int bu = y+x;
  int value = (int)bu % 2;
  int luma = value * 255;
  return color(luma);
}

Here is a “disturbing” animated spiral (note that it’s spinning in the direction opposite to the one given in instructable; just need to decrement time):

TIME_INCREMENT = 0.1;
FRAMES = 10;
FRAMES = TWO_PI / TIME_INCREMENT / 3;
OUT_PAUSE = false;
WIDTH = 250;
RATIO = 1;
X_MIN = -1; X_MAX = 1;
Y_MIN = -1; Y_MAX = 1;

color rgb(x, y, t) {
float radius = dist(x, y, 0, 0);
float angle = -atan2(x, y);
angle = angle - t;

float value = angle*3 - (radius)*12;
float stripe = cos(value);

float luma = (stripe - 5) * 127;
return color(luma);
}

Today, 6-10-2016, is a Palindrome Day (if written in dd-mm-yyyy format)! So I end my post with this GIF I recorded using byzanz (on Ubuntu) and edited using ezgif.com: