If A Picture Paints A Thousand Words

And so begins the words of the a song by the Bread. The complexity we see in the world is a product of the interactions of simple building blocks. Everything we see is just a combination of a few elements in the periodic table. In turn every element is a combination of electrons, protons and neutrons.

A picture paints a thousands words but what paints a thousand pictures? Just like a Lego truck that is composed of a few Lego shapes, a “black and white” picture is also composed of a few levels of gray. The levels is just a set of 256 numbers starting from 0 up to 255. The number 0 represents black and the number 255 represents white. The numbers in between represent colors between extreme black and extreme white. The diagram below shows the levels of gray in a 16 by 16 matrix. The gradient goes from left to right, top to bottom.



Using just these 256 numbers, we can already draw interesting figures. Take for example this 8 by 8 matrix of numbers:

197   4  46  18 155 186 144 190 
111  30   6 131 235  99 112 227  
10   26 141 147 120  28  92 187 
241 100 118 149 178   5 158 213 
105  43 104  63 172 222  64 174 
130 194 243  56  59 166 134 133 
247 145  36  82 238 251  53 129 
171  29  51 163 199 214 113 195

When you plot this on an 8×8 grid, you get the following pattern:



Not all pictures need to be boring. Here’s an example of a picture that is not that boring:

17 23 26 20 13 20 20 22 21 17 17 25 20 11 15 15 9 10 18 13 14 12 13 39 61 63 71 72 69 71 74 72 74 75 72 76 75 75 75 80 77 78 79 79 80 80 80 80 81 81 82 82 83 83 83 83 84 84 84 84 85 86 86 86 87 87 87 88 88 88 89 89 89 89 90 90 90 90 90 91 90 90 91 91 92 92 92 92 94 94 95 95 95 95 95 95 96 96 96 96 97 97 97 97 98 98 98 99 99 99 100 100 101 101 101 101 102 102 103 103 104 104 104 105 105 105 105 105 106 106 106 107 107 108 108 108 110 110 110 110 111 111 112 112 113 113 113 114 114 115 115 115 116 116 117 117 117 118 118 119 119 119 120 120 121 121 122 122 123 124 124 125 125 125 126 127 127 127 128 128 129 129 129 129 131 131 132 132 133 134 ...

That is just the start of a 310×204 matrix saved in the file “clifton.txt”. If you plot that using the R command

clifton = read.table("clifton.txt")

#convert this data frame to a vector
vclifton = as.numeric(clifton) 

#create the 310x204 matrix
mclifton = matrix(vclifton,nrow=310,ncol=204)

#plot the image
image(mclifton[,ncol(mclifton):1],col=gray((0:255)/255))

you’ll get the following image



Histogram

If you look at the file “clifton.txt” and count the occurrence of each number, you will see that there are 9 occurrences of zero and 4 occurrences of 240. If you do this for all other numbers, you will get the following counts:

Level Frequency
0     9
1     16
2     31
3     34
4     49
:
:
237   115
238   113
239   18
240   4
:
:
254   0
255   0

If you plot this data as a bar chart, you will get what is known as the histogram of the picture:



The histogram above was obtained using the following R command:

hist(vclifton,breaks=256)

The histogram tells us the how much of each gray level contribute to the actual image.

Here’s another example of a picture that is relatively dark. In photography, the image below is called a “Low Key” image because it is mostly dark.



Low Key images tend to have the bulk of the colors at the right side of the scale. The next image is a “High Key” image because it is mostly white:

Histograms of High Key images tend to have the bulk of the colors at the right side of the scale. The histogram of the “clifton.txt” image tends to have a much better balance in that it contains most of the colors at the middle of the range.

It’s surprising how we can come up with complex images using just 256 levels of gray. We haven’t even considered colors yet! We also learned how histograms can be constructed by counting the frequency of each level and what histograms of High Key, Low Key and Optimum exposure look like.

A Sound Correction

As I was taking my coffee over breakfast today, I realized that in the previous post, I did not incorporate the time it took for the sound waves to reach my ear when I pressed the stop button of the stopwatch. Sound waves travel at 340.29 meters per second. At a height of 25 meters, it would take 0.073 seconds for the sound of the explosion to reach the ground. This should be negligible for the purposes of our computation. However, what is really the effect if we incorporate this minor correction?

As seen in the figure below, the recorded time is composed of the time it took for the skyrocket to reach the maximum height plus the time it took for the sound waves to reach my ear, that is,

t_r = t_a + t_s

where t_r is the recorded time, t_a is the actual time the skyrocket reached its maximum height and t_s is the time it took for the sound waves to travel from the maximum height to the ground.



We can rewrite the height as

\displaystyle h_{\text{max}} = - \frac{gt_a^2}{2} + v_i t_a

Since v_i = gt_a,

\displaystyle h_{\text{max}} =  - \frac{gt_a^2}{2} + gt_a^2
\displaystyle  =  \frac{gt_a^2}{2}

At the maximum height, h_{\text{max}}, it would take the sound waves t_s seconds to travel, that is,

\displaystyle h_{\text{max}} = v_s t_s

where v_s is the speed of sound. Therefore,

\displaystyle t_sv_s = \frac{gt_a^2}{2}
\displaystyle (t_r- t_a)v_s = \frac{gt_a^2}{2}
\displaystyle v_st_r - v_st_a = \frac{gt_a^2}{2}
\displaystyle \frac{gt_a^2}{2} + v_st_a - v_st_r = 0

The last equation above is a quadratic equation which we can solve for t_a using the quadratic formula:

\displaystyle t_a = \frac{-v_s \pm \sqrt{v_s^2 - 4(1/2)gv_st_r}}{2(1/2)g}

Substituting the values g = 9.8, v_s=340.29, and t_r = 2.3, we get

\displaystyle t_a = 2.22

Using this result, the maximum height is computed to be

\displaystyle h_{\text{max}} = \frac{gt_a^2}{2} = 24.33

Comparing this with our previous computation of h_{\text{max}} = 25.829, we find that we have overestimated the maximum height by about 1.49 meters. It’s not really that bad so we can just drop the effect of sound.

New Year, New Heights and the Projectile

I spent my new year celebration at our friend’s place with 2 other colleagues. It was started with a dinner at about 9:30 pm and we bought some bottles of wine in addition to the spirits we already brought. At about 10:30, a street party was setup in the vicinity and about 5 other families joined in a potluck. Marijo’s brother started the fireworks at about that time with David and Gerard (my colleagues) taking turns setting them off. I did not attempt to set them off because I did a lot those things way back as a child and still lucky enough to have my fingers intact.

This is a video of our 2012 New Year’s Celebration:

As Gerard was flying off skyrockets (or kwitis as they are called in my language) David asked me “How high do you think these things go up?”. That was a really good question which got me to thinking. I said “Let’s compute!” So I took my iphone and launched its built-in stopwatch. Gerard flew about 3 skyrockets and I took the time it takes for them to fly until they blow up in the air. The average was found to be 2.3 seconds.

Independent of Mass

Legend has it that Galileo Galilei performed an experiment at the Leaning Tower of Pisa. He dropped objects of different masses to see which of them falls first. Starting from the heaviest to the lightest object, what he found was that, in a vacuum, they reach the ground at the same length of time when dropped from the same height. Using this result, we can compute for the distance travelled by any object under the influence of gravity. At heights near the earth’s surface, the acceleration of objects in the presence of gravity alone is given by

\displaystyle \frac{d^2h}{dt^2}= \frac{dv}{dt} = -g

where h is the vertical distance (height), v is the velocity and g is the acceleration due to gravity given by g = 9.8 \text{m/s}^2.

The equation above is a simple differential equation which we can solve for the velocity at any time t by integrating both sides:

\displaystyle  \int^{v}_{v_i} dv = \int^{t}_{t_i} -g dt

which by the Fundamental Theorem of Calculus gives us

\displaystyle v - v_i = -g(t - t_i)
\displaystyle v = -gt + v_i + t_i

If we take initial time of the rocket launch to be zero, that is, t_i=0, we have

\displaystyle v = \frac{dh}{dt}=  -gt + v_i

We don’t know the initial velocity v_i of the rocket. However, at the maximum height attained by the rocket, the velocity is zero. Using this fact, we can solve for the initial velocity:

\displaystyle 0 = -gt_{\text{max}} + v_i
\displaystyle v_i = gt_{\text{max}}

where t_{\text{max}} is the time the rocket reached maximum height.

At t_{\text{max}}=2.3 seconds, the initial velocity is therefore v_i = 9.8 * 2.3 = 22.5 m/s.

Maximum height

We can solve for the height as a function of time by integrating both sides of the velocity equation:

\displaystyle \int^{h}_{h_i} dh = \int^{t}_{t_i} -gt dt  + v_i dt
\displaystyle h - h_i = -\frac{gt^2}{2} + v_i t \big|^t_{t_i}

Since the initial height is zero , that is , h_i = 0 and the initial time is zero t_i = 0, we have

\displaystyle h = -\frac{gt^2}{2} + v_i t

Since at t=2.3 seconds, the rocket reaches the maximum height, we have

\displaystyle h_{\text{max}} = -\frac{9.8 \times (2.3)^2}{2} + 22.5 * 2.3 = 25.829 \text{ meters}

Does this make sense? The average height of a building storey is about 3 meters. This is about 8 or 9 storeys high which I think makes sense.

It’s good that my new year not only started with a warm welcome from friends but it also appealed to my physics curiosity.

Thank you to Marijo Condes and family for letting us spend a memorable New Year’s Eve.

Mathematically Romancing Mt Mayon

The name Mayon is short for Daragang Magayon, or “Beautiful Lady”, which is the legend associated with Mt Mayon. No wonder, I still find myself captivated by its charms after visiting it three weeks ago.

While playing with google maps this sunday, I decided to take a look at Mt Mayon and I was hoping I could get a three dimensional view of the beauty. I was disappointed. Although there is a 3D view, but it was not beautiful at all. Luckily, google map provides a topographical information of Mt Mayon. Suddenly, I was inspired to recreate the view of Mt Mayon using that information and using the tool called R.

First thing I did was to capture the image from the google maps and saved it as JPEG. Using the ReadImages library of R, I loaded the image and plotted it.

# load the library
library("ReadImages")

# read the file and plot
x=read.jpeg("mount_mayon_topography2.jpg")
plot(x)

# add grid lines
grid(nx=20,ny=20,col="red")

The result of the code above is a plot of the image with red grid lines, as shown below.


You will notice that the image contains contour lines with a height information associated with it. I used the grid lines to manually interpolate the height of Mt Mayon at each intersection. I started at the bottom line and worked myself upward from left to right. However, I got lazy interpolating from point to point so I just stopped when I reached the middle line. I decided that the upper half of the image is just a mirror image of the bottom so I might as well use the same numbers. Here’s a dump of the interpolated height from the bottom half of the image:

0,        0,    0,     0,     0,    0,400,400,400,450,450,420,400,350,300,280,250,220,200,
0,     100,200,300,400,420,450,500,550,570,550,500,480,420,400,380,350,250,200,
200,300,350,400,420,500,550,580,600,650,600,600,580,550,500,400,350,300,320,
280,350,380,400,500,580,610,650,780,800,750,730,650,600,500,450,380,310,300,
300,400,430,500,580,650,780,800,950,990,970,900,800,700,580,500,520,350,300,
310,400,480,580,610,750,840,1000,1100,1200,1150,1100,1000,800,650,550,450,380,350,
320,450,500,600,700,800,1000,1200,1350,1500,1500,1380,1180,900,800,650,510,400,350,
350,450,500,600,750,900,1100,1350,1600,1800,1800,1600,1350,1100,900,700,550,450,350,
370,450,500,600,780,900,1200,1500,1800,2100,2000,1800,1500,1180,900,700,550,500,350,
380,450,500,620,780,970,1200,1500,1900,2250,2200,1800,1400,1150,900,700,550,520,400,

Reflecting this information about the middle line and inputting this to R, we get

z=c(0,        0,    0,     0,     0,    0,400,400,400,450,450,420,400,350,300,280,250,220,200,
0,     100,200,300,400,420,450,500,550,570,550,500,480,420,400,380,350,250,200,
200,300,350,400,420,500,550,580,600,650,600,600,580,550,500,400,350,300,320,
280,350,380,400,500,580,610,650,780,800,750,730,650,600,500,450,380,310,300,
300,400,430,500,580,650,780,800,950,990,970,900,800,700,580,500,520,350,300,
310,400,480,580,610,750,840,1000,1100,1200,1150,1100,1000,800,650,550,450,380,350,
320,450,500,600,700,800,1000,1200,1350,1500,1500,1380,1180,900,800,650,510,400,350,
350,450,500,600,750,900,1100,1350,1600,1800,1800,1600,1350,1100,900,700,550,450,350,
370,450,500,600,780,900,1200,1500,1800,2100,2000,1800,1500,1180,900,700,550,500,350,
380,450,500,620,780,970,1200,1500,1900,2250,2200,1800,1400,1150,900,700,550,520,400,
370,450,500,600,780,900,1200,1500,1800,2100,2000,1800,1500,1180,900,700,550,500,350,
350,450,500,600,750,900,1100,1350,1600,1800,1800,1600,1350,1100,900,700,550,450,350,
320,450,500,600,700,800,1000,1200,1350,1500,1500,1380,1180,900,800,650,510,400,350,
310,400,480,580,610,750,840,1000,1100,1200,1150,1100,1000,800,650,550,450,380,350,
300,400,430,500,580,650,780,800,950,990,970,900,800,700,580,500,520,350,300,
280,350,380,400,500,580,610,650,780,800,750,730,650,600,500,450,380,310,300,
200,300,350,400,420,500,550,580,600,650,600,600,580,550,500,400,350,300,320,
0,     100,200,300,400,420,450,500,550,570,550,500,480,420,400,380,350,250,200,
0,        0,    0,     0,     0,    0,400,400,400,450,450,420,400,350,300,280,250,220,200)

Next, I generated the coordinates of the x and y plane:

myx=seq(-9,9,1)
myy=seq(-9,9,1)

To generate the 3D view, I used the persp3d function of the rgl library and animated the 3D plot so that we can see the plot 360 degrees.

library(rgl)
persp3d(myx,myy,z,col="darkseagreen", aspect=c(4,4,1))
play3d(spin3d(axis=c(0,0,1), rpm=8), duration=20)

The result of the above code is an animated plot of Mt Mayon using partial topographical information. Shown below is the animation:

This is indeed a great waste of time. But I guess, that’s what you do when you fall in love…mathematically!

Chances Are

I just came from a great weekend escapade, with my wife and two colleagues, in one of the beautiful regions of the Philippines. Bicol is home to Mayon Volcano, one of the seven perfect coned volcanoes on Earth. The scenery is so green and the air so refreshing. It was one of the best trips I ever made in the Philippines.



The trip was also full of coincidences. We met a colleague in one of the restaurants in Naga City where we had our dinner. In the same restaurant we also met one of our contacts in Ateneo de Naga. On the way home, we met another colleague at the airport. But the first coincidence happened on our way to Legazpi City where one of my companions (i’ll hide the name to protect the innocent) met a good friend in the airplane seated next to him. It was a pleasant surprise for my companion and he asked “What are the odds of that happening”? That’s a good question which got me thinking later that night.

To simplify the problem, let us not compute the odds of my companion and his friend to be in the same plane going to Bicol. Rather, let us compute the odds of him being seated next to his friend. The plane was an airbus A320 and about 180 seats. The seats are laid out in such a way that there is a middle isle and each row is composed of three seats. Let us draw a row of seats and assume we have persons A and B. How many ways can they be seated in that row in such a way that they sit next to each other? Below is a diagram on the ways two persons can be seated next to each other.



As you can see, there are four ways for them to be seated next to each other for any given row. In the first arrangement, we have A, B seated in that order. The third seat can be occupied by anyone. Having chosen the seats for A and B, how many choices do we have for the third person? Since there are 180 seats minus two, the third person has 178 other seats to choose from. Once person number 3 chooses one seat, the fourth person can then choose from the remaining 177 seats. Doing this for all other passengers, you will come up with 178! ways of assigning seating arrangements for the 180 passengers such that persons A and B are seated next to each other. Now, that is just for the case where A and B are in the first two seats. For the other three cases, you will see that it also takes 178! ways for each case. Since there are 4 cases per row and 60 rows, we have

\displaystyle 4\cdot 60\cdot 178!

ways to have two persons sit next to each other on a 180 seater plane. Since the total number of ways to assign passengers to 180 seats is 180!, then the probability of having two persons seat next to each other is

\displaystyle \frac{4\cdot 60\cdot 178!}{180!}
\displaystyle = \frac{4\cdot 60\cdot 178!}{180\cdot 179\cdot 178!}
\displaystyle = \frac{4\cdot 60}{180\cdot 179}
\displaystyle = 0.00744879

This is quite a low probability and it assumes that the seating arrangement is totally random. By totally random, I mean that my wife and I could be seated far apart from each other. In reality, this is not the case since many passengers come in groups and they prefer to be seated next to each other. If we take this into account, then the probability of my companion and his friend to be seated next to each other increases.

Reflecting on Convexity

Last Friday, I was told of a puzzle by my colleague that was given to him on an interview. The puzzle goes like this: You and an opponent sit opposite a round table. You are to place coins (of the same size) on the table, one at a time. No coin should sit on top of another coin, even partially. No part of any coin should go beyond the table’s boundaries. You take turns putting coins on the table until you can no longer find any space to fit a coin. The last person to put a coin wins. If you had the first turn, what would be your strategy? This is a puzzle i’m not be able to answer on an interview and over 2 bottles of beer. So I told my colleague i’ll work on it on the weekend.

My first impulse was to treat this as a packing of circles inside a bigger circle. To start, let us have the circle small enough to fit only a 1 layer of circles along the circumference of the middle circle, as shown below.


In this configuration, the circles in dark blue are mine while the lighter ones are of the opponents. In this game, I win because I was the last one to put the coin. However, since my opponent is also rational, he will not allow me to win. He will put his lighter colored coin in a position shown below. This game started with me putting my coin in the middle. He then put his coin on top of the middle coin. Next I put my coin next to his coin, touching each other. But my opponent now puts his second coin in such a way that it has a space between my 2nd coin and his 2nd coin for which no coin can fit. Then I put my 3rd coin next to his 2nd coin. When he put his third coin, there was no more space for me to insert another coin. So I lost.


There must be a way for me to influence his next move. Looking at the geometry of circles, there must be something that can be made use of the circular symmetry. For one thing, all points on a circle have the same distance from the center. Another thing is if you pass a line through the center it will intersect the circle in 2 points. These points are antipodes of each other. This gives a very good way to control the outcome of the game. We let our opponent select a spot to put the coin, then we get the antipod of that location and put our coin there. We do this until no more coins can be put on the table.


Let us walkthrough the sequence of steps as shown above. After I put my coin in the middle, my opponent puts his coin above it. Then what I do is to put my 2nd coin on the opposite side (antipode). My opponent then employs his usual strategy which is to put his next coin so that it will have a small space in between. However, i put my 3rd coin opposite his 2nd coin. When he puts his 3rd coin, he will realize that there is no more space for him to squeeze it in, as shown by the red coin which already goes beyond the bounder of the table. So I win!

The good news is that this is not a coincidence. We will always be the last person to put a coin on the table. To see this, assume the contrary: our opponent was able to put a coin C_o on the table but for which the antipode has no more space to accommodate the coin. This means that if we put our coin, it will intersect at least one coin C\prime. Let p\prime be a point inside this intersection. By the way this was constructed, there is another coin C which contains the antipode p of point p\prime. This means that p \in C_o \cap C, that is, C_o intersects C, which is a contradiction.

Convex Regions and Point Reflections

Will this work only with circular tables? Will it work also with rectangular tables? Will it work only with coins? Will any other shape also work? Consider a table of some arbitrary shape but with the property that for any two points p and q on this table, we can draw a line connecting them in such a way that the line is contained with in the table. We call this region a convex region. The property of a convex region is that the centroid of this region is contained within it. Shown below is an example of a convex region and a non-convex region.



A table shaped like a horseshoe is not convex and its centroid is outside of the table.

Suppose we have found the centroid of our convex region. Instead of using a coin, let’s use a star to put into the table. If our opponent puts his star anywhere on the table at a position r_1 from the centroid, then the antipode of this position must also be inside the region, by virtue of its being convex. Let us put our star in such a way that it is the reflection through the centroid of our opponent’s star. If we set up a coordinate system on the table centered at the centroid (surprise!), then point reflection through the origin transforms in the following manner:

\displaystyle (x_1,y_1) \mapsto (-x_1, -y_1)

Since this mapping is isometric, i.e, preserves distances, any two points p_1 and p_2 will retain the same distance after reflection. This means that if two stars don’t intersect, they will not suddenly intersect under this mapping.

The figure below shows a star S_1 defined by the following coordinates.

           x         y
1  0.8754257 0.4100271
2  0.8292804 0.4380167
3  0.8248856 0.4700049
4  0.7941220 0.4360175
5  0.7501740 0.4400160
6  0.7809376 0.3980315
7  0.7567662 0.3620448
8  0.8029116 0.3680426
9  0.8226882 0.3380536
10 0.8358726 0.3780389
11 0.8732283 0.4080278

This star is the one shown in blue in the first quadrant. Another star S_2 was defined by translating S_1 by 0.1 in both directions. This is the star shown in red in the first quadrant.


Applying the point reflection through the origin, we get the two stars shown in the third quadrant. The blue colored star is the reflection of the blue colored star in the first quadrant. The same thing applies to the red star. What we have just shown is that you can modify the problem to tables like squares or polygons by virtue of being convex regions. Also, by the isometry of the point reflection through the origin, we can use other shapes and not just circles.