Learning using Puzzles

Mathematical and logic puzzles are a great way to learn. I think they should be used to a greater extent in school and college education than they are, because they:

1. Create an excitement in the mind of the student/solver.
2. Force the solver to think about what method to use to attack the problem. This is much closer to real world situations, where one is not told about what area a problem is in. Tech companies recognize this when they use puzzles  while interviewing job candidates as a way to observe how the candidate thinks.
3. Over time, allow students to recognize patterns in problems and the best way to attack them, so that wehn they are faced with a new, real world problem, they have a good idea of what to try first.

I am certainly not the first one to note the educational value ofpuzzles. Martin Gardner, whose puzzles I have tremendously enjoyed has himself advocated for puzzle-based learning.

Each puzzle is usually based on one (or, sometimes two, but very rarely more than two) fundamental areas of math: probability, number theory, geometry, critical thinking etc. For example, take the following puzzle (try these puzzles before reading answers at the end of the post):

[1] By moving just one of the digits in the following equation, make the equation true:

$latex 62 - 63 = 1$

It should be clear that this puzzle is part math and part logic.

Often there is more than one way to arrive at the solutions -- e.g. using a geometric visualization for a algebraic problem in 2 or 3 variables. For example take the following puzzle:

[2] A stick is broken up into 3 parts at random. What is the probability that the thee parts form a triangle?

One may choose to solve the above problem using algebra, but it can be visualized geometrically too.

Speaking of geometric methods, there is also something to be said about solving puzzles inside one's head, rather than using pen and paper. I feel it adds to the thrill because it can be more challenging. It is also fun to visualize objects and their relationships in mathematical terms,  completely inside one's head. The following is an example of a pretty hard puzzle, which was solved entirely inside one mathematicians head :

[3] Peter is given the product of two integers both of which are between 2 and 99, both included. Sally is given only their sum. The following conversation takes place between them:

P: I cannot figure out the two numbers from the product alone.

S: I already knew that you couldn't have figured them out.

P: Oh, now that you say that, I know what the two numbers are.

S: I see. Now that you say you know what they are, I also know what they are.

What are the two integers?

___

[1] $latex 2^6 - 63 = 1$

[2] Without loss of generality, assume that the stick is of unit length. Since the three lengths add up to 1, and are each $latex \in [0,1]$, they can be treated as three random variables $latex (x,y,z)$ in 3D space, lying on the 2-dimensional triangular simplex with vertices at (1,0,0), (0,1,0) and (0,0,1). The problem now boils down to determining what fraction of the surface of this triangle corresponds to tuples that cannot form a triangle. From the triangle inequality, we know that $latex x + y > z$ and so on for the other two pairs. A little mental visualization reveals that these boundary conditions are met when each side of these inequalities is $latex \frac{1}{2}$. The region corresponding to feasible points is a smaller equilateral triangle inscribed within the simplex and is one-fourth the area of the simplex. The answer therefore must be $latex \frac{1}{4}$.

[3] The answer can be found in this PDF of a note written by EW Dijkstra, who solved the problem in his head.

Andre Geim

"Many people choose a subject for their PhD and then continue the same subject until they retire. I despise this approach. I have changed my subject five times before I got my first tenured position and that helped me to learn different subjects." - Sir Andre Konstantin Geim (2010 Nobel Prize winner in Physics).

You are my hero Andre.

Make webcomics easily

I have wanted to draw webcomics for at least the last 3 years, but never got around to figuring out an easy way to do it. Drawing on a computer with a mouse is a disaster. There are special tablets like Wacom's that artists use (I believe xkcd uses Wacom's tablet). There are also some high-end, expensive iPad apps (e.g. brushes). But I wanted to do very simple drawing and without spending any money. I finally decided to put together a easy to use method for drawing simple black & white comics. I think the simplest way to draw a webcomic is low-tech:

1. Draw on paper with a black marker.
2. Take a picture with your phone and upload to a computer. Unfortunately, a picture taken by a phone is not simple b&w, but contains many colours, graininess of the paper, the effect of lighting, etc. Therefore:
3. Run the picture though a pixel thresholder.

I wrote a small python program to threshold the value of each pixel and make each pixel either pure white or pure black. The result allows me to go from the JPG picture on the left (taken with an iPhone 3GS) to the PNG image on the right:

Each pixel in the left image is simply an integer between 0 and 255 (after converting to grayscale). Now, this should be easy to do using a basic image editing program by 'converting to B&W', but the caveat is that one cannot simply use a threshold of 128 because the pixels corresponding to blank space on the paper may not necessarily be below 128. The result of using a fixed threshold of 128 was a disaster:

There is probably a menu option somewhere on a good image editor to do what I want, but I don't want to deal with image editors, and besides, I want to automate webcomic creation as much as possible. So I settled on running k-means clustering on the pixel values with k=2 clusters. This gives two clusters, one corresponding to the blacks and one corresponding to the whites in the image:

Histogram of pixel values (0-255). Cluster of blacks on the left with centroid at 16. Whites on the right, centroid at 110.

The average of the two centroids can be taken to be the threshold. The threshold for the example above came out to be 63 -- pretty far from 128! By the way, the mean pixel value is 103, which would clearly not have worked as well as the mean of the cluster centroids did.

This code may be useful to others who want to put up their comics/doodling on the web. Unfortunately, the program has a number of python module dependencies (Scipy, PyPNG, Numpy), because I just wanted a quick hack. But I'll put up the code here anyway. Someday, I'll get a github account.

[sourcecode language="python"] import numpy, png, os, sys, pylab as plt import scipy from scipy.cluster.vq import vq, kmeans

infile = sys.argv[1]

print 'Converting to PNG...' #Make sure input is a png pngfile = infile.split('.')[0]+'.png' os.system('convert ' + infile + ' ' + pngfile)

print 'Reading in pixels...' f = open(pngfile, 'rb') r = png.Reader(file=f) k = r.read() l = list(k[2]) numplanes = k[3]['planes'] l = zip(*l) numrows = len(l) l = l[0:numrows:numplanes] # This will skip every numplanes element l = zip(*l) f.close()

# Create a 1-D array of all the pixel values l = numpy.array(l) pixels = [] for i in range(0, len(l)): for j in range(0, len(l[0])): pixels.append(l[i][j]) pixels = numpy.array(pixels)

print 'Computing threshold...' # Find the adaptive threshold by running one-dimensional k-means, with k = 2, and find the mean of the two cluster centers. j = scipy.cluster.vq.kmeans(pixels, 2) adaptivethreshold = (j[0][0] + j[0][1])/float(2)

print 'thresholding...' # now threshold for i in range(0, len(l)): for j in range(0, len(l[0])): if l[i][j] < adaptivethreshold: l[i][j] = 0 else: l[i][j] = 255

print 'Writing to file...' # Now write: thresholdfile = pngfile.split('.')[0]+'-threshold.png' f = open(thresholdfile, 'wb') w = png.Writer(len(l[0]), len(l), greyscale = True) w.write(f, l) f.close() [/sourcecode]

Time Management

I recently came across a surprisingly lucid model for time management. The model consists of just two variables that together categorize the tasks we do roughly into 4 bins. The two variables are 'Importance' and 'Urgency'. That is, a task has an importance score, and an urgency score. To simplify even further, imagine that each of the two variables is just a binary variable: that is, a given task is either important or not, and either urgent or not.

It is necessary to first understand the difference between 'important' and 'urgent'. An important task is one which is aligned with one's long term goals or makes a significant difference to one's life in the long term. An urgent task is one which demands immediate attention.

Which of the four quadrants above do you think we should operate in? Let's look at each of them:

4: Not urgent, and not important: This is the most useless category. Examples would include mindless browsing, excessive use of Facebook. This  is the quadrant of waste.

3: Not important but urgent: Petty things that sometimes take away our attention and time, preventing us from focusing on the important things, for example: receiving an email about a shopping sale on a website that is about to expire can lead us to stop what we are doing and start looking into shopping online. Very dangerous. This quadrant is called the quadrant of deception.

2: Urgent and important: When something important is delayed till it can no longer be delayed, it becomes urgent. Example: John wants to go to graduate school after college, but has delayed working on his application till the very last minute. Now the task is both important and urgent. This is the quadrant of procrastination. Important tasks done in a hurry are rarely done properly, and do not lead to satisfaction.

1: Not urgent, but important: This is the quadrant of planned action. It is the quadrant we want to be in in order to manage time well. Important tasks are planned and assigned time slots before they become urgent.

Note to self: Eliminate tasks in Q4, Q3, and move tasks in Q2 to Q1.

Edit: I just learnt that this model was popularized by Steven Covey, who passed away unexpectedly earlier this year.