Wednesday, December 25, 2013

Puzzle: Shortest distance between points on a cubic grid

This is a middle or high-school level puzzle aimed at encouraging algorithmic thinking.

We know that the distance between two points A and B is \[d_{AB} = \sqrt{(x_A - x_B)^2 + (y_A - y_B)^2 + (z_A - z_B)^2},\] where x, y, and z denote the Cartesian co-ordinates.

Suppose the points A and B lie on a cubic grid or lattice. That is the Cartesian co-ordinates are integers.

What is the shortest distance between the points along the lattice?

In the 2D example below (assuming each small square has sides of length 1), the shortest distance between points  A and B with and without the lattice constraint is \(3 \sqrt{2} + 1\) and 5, respectively.


Additional Notes/Hints:

1. In other words, you start from the point A and hop to any of the 8 (2D) or 26 (3D) nearest lattice points. You repeat this process, until you reach B.
2. In 3D, an individual hop may be of length \(1, \sqrt{2}, \sqrt{3}\).
3. The shortest path itself may not be unique, but the shortest length is.
4. It may be useful to rephrase the problem in terms of \(\Delta x = |x_A - x_B|, \Delta y = |y_A - y_B|, \Delta z = |z_A - z_B|\).


Friday, December 13, 2013

Transition Slides in Beamer

Imagine that you want to produce a series of three transition or thematically linked slides. By that, I mean that most of the information on the slide remains the same, with minor additions, deletions or changes.

As an example consider the following three frames:




The first step, in this case, would be to draw the three figures in a drawing program (like Inkscape), preferably one which supports layers.

I like to draw a border around the image. That way, when I export the image into PNG or PDF format the dimensions of the image are conserved.

Next, we use the following self-explanatory TeX code:

Thursday, December 5, 2013

RIPE: More Polymer Entanglements

In a previous post I discussed entanglements in polymer melts. I thought I’d spend sometime discussing some “practical” matters in which entanglements play a role. Today, lets focus on a very special kind of polymer: DNA.

You have a lot of DNA in your body. In fact, each cell in your body has over 2 meters of DNA packed inside a small bag called the nucleus. The diameter of a typical nucleus is less than 10 microns.

If that hasn’t knocked you off of your seat yet, let me put it in perspective. If all the DNA in your body were set end to end, it would stretch from the Sun to Pluto!

To freaking Pluto; which they say is not even a planet anymore!

I have trouble dealing with headphones in my pocket, and the nucleus manages to pack and use all of that DNA inside it. How the heck does it do that?

The answer turns out to have some parallels in everyday life. How do you deal with a really long water hose or vacuum cleaner cable? You roll it around something! You organize it!

Thus, DNA is not packed randomly. It is organized in a very sophisticated hierarchical manner. This allows the nucleus to sequester a lot of material and information in a very small compartment. Here is a nice video that explains this organization (DNA - nucleosomes - chromatin).