Friday, February 8, 2013

The science behind meditation - is it brain training?

An interesting article on Matthieu Ricard, a researcher turned monk, suggests that meditation might act as a brain training exercise, helping the human mind to achieve superior levels of happiness and decreased propensity for negativity. One hopes more research is done in this area so that the exact mechanism by which meditation acts to bring peace of mind is understood, thereby helping the whole of mankind lead a more content life.

Thursday, February 7, 2013

Converting twips to pixels and vice-versa

Here is a Ruby program to convert between twips and pixels:

#!/bin/ruby

# As per PostScript definition
TWIPS_PER_INCH = 1440

def twips_to_pixels(twips, dpi, round = true)
  raise "Invalid DPI" if (dpi <= 0)
  raise "Invalid twips" if (twips < 0)

  num_pixels = ((twips / TWIPS_PER_INCH.to_f) * dpi)
  return round ? num_pixels.round : num_pixels.floor
end

def pixels_to_twips(pixels, dpi, round = true)
  raise "Invalid DPI" if (dpi <= 0)
  raise "Invalid number of pixels" if (pixels < 0)

  twips = ((pixels / dpi.to_f) * TWIPS_PER_INCH)
  return round ? twips.round : twips.floor
end

def numeric?(str)
  Float(str) != nil rescue false
end

def print_usage_and_exit
  puts "Usage: #{$0} [-t twips | -p pixels] [-d dpi]"
  exit(1)
end

if __FILE__ == $0
  print_usage_and_exit if ARGV.length != 4

  dpi = nil
  twips = nil
  pixels = nil

  [0, 2].each do |option_index|
    option = ARGV[option_index]
    option_val = ARGV[option_index + 1]
    print_usage_and_exit unless (numeric?(option_val))

    case option
      when "-d" then dpi = option_val.to_f
      when "-t" then twips = option_val.to_f
      when "-p" then pixels = option_val.to_f
      else print_usage_and_exit
    end
  end

  print_usage_and_exit if ((pixels.nil? && twips.nil?) || dpi.nil?)
  res = twips.nil? ? pixels_to_twips(pixels, dpi) : twips_to_pixels(twips, dpi)
  puts res
end

Sunday, February 3, 2013

1/-1 matrix - problem #29 from Problem solving strategies

Here is the solution to one of the problems mentioned in the earlier blog post:

Problem 29: Suppose contrary to the claim a1 + b1 + … + a25 + b25 = 0. Then:
(a1 + a2 + … + a25) = - (b1 + … + b25)
Now note that ai= -1,if number of elements having value -1 in row i is even, and 1 otherwise.

Thus (a1 + a2 + … + a25) = -x + y,  where x is the number of rows having odd number of -1s and y is the number of rows having even number of -1s

Similarly, (b1 + … + b25) = -m + n, where m is the number of columns having odd number of -1s and n is the number of columns having even number of -1s

Combining ①, ② and ③ results in the equation (y – x ) = (m - n)

But (y + x) = 25, the total number of rows in the matrix, and (m + n) = 25, the total number of columns in the matrix. Thus (y + x) = (m + n)

Combining ④ and ⑤ results in the equality y = m, which implies that the number of rows with even number of -1s equals the number of columns with odd number of -1s.

Define z = number of -1s in the matrix.

Suppose y is odd. Then, x must be even and by original definition of x and y, z must be even (even number of rows with odd number of -1s plus odd number of rows with even number of -1s, resulting in even + even). If y is even, z must be odd. Thus parity(z) ≠ parity(y)

On the other hand, by definition of m and n, it can be shown that if m is odd, then z must be odd and if m is even then z must be even. Thus parity(z) = parity(m). But this contradicts since y = m as per an earlier equation. Thus the assumption a1 + b1 + … + a25 + b25 = 0 is wrong.

Thursday, January 31, 2013

2 problems - Matrix numbering and integer colouring

Here are 2 interesting problems from chapter 2 of Arthur Engel's book:

1. The positive integers are colored black and white. The sum of two differently colored
numbers is black, and their product is white. What is the product of two white
numbers? Find all such colorings.

2. Each element of a 25 × 25 matrix is either +1 or −1. Let ai be the product of all
elements of the i-th row and bj be the product of all elements of the j-th column.
Prove that a1 + b1 + · · · + a25 + b25 ≠ 0.

Sunday, January 27, 2013

Tile colouring problem (#8) from Problem solving strategies

Problem: Prove that an a × b rectangle can be covered by 1 × n rectangles iff n|a or n|b.

Solution: The proof is given by means of the following 2 claims.

Claim 1: Given a rectangular area is covered by tiles of dimension 1xn placed in horizontal or vertical orientation, it is possible to remove the tiles one at a time in such a way that at any point of time, the covered region’s top border consists of a sequence of steps increasing from left to right as shown in diagram 1.

Proof: Define step blocks to be rectangular regions defined by the step-like shape of the covered area. In diagram 1, step blocks are represented by the areas shaded blue. Start from the left most step block and consider the top left tile in that block. This tile must fall entirely within the current block (call it block A) or must extend beyond the right of the current step block (it cannot beyond the bottom of the current block since the first block is also the bottommost). In the former case, removing the tile will leave behind a step shape, thereby proving the claim. In the latter case, inspect the next step block for the possibility of removing a tile. The top left tile of this next block (call it block B) cannot extend beyond the bottom of that block since the block A’s top left tile occupies that portion as per the previous statement. Hence the top left tile of block B too must either lie entirely within B or extend beyond the right of B. As before, in the former case, removing the tile will leave a step shape whereas in the latter case, the search for a tile to remove can be repeated with the block to the right of C. Note that this procedure can be repeated at most till the rightmost block is reached, in which case the top left tile cannot extend beyond the right of the block (and must therefore lie entirely within that block), thereby becoming eligible for removal while retaining the step shape.

Claim 2: When tiles are removed as per the procedure of claim 1 and neither a not b are divisible by n, then at any point of time at least one of the step regions on the top border will have a height and a width (as defined by diagram 2) that are both indivisible by n.

Proof: The proof is by induction on r, the number of tiles removed so far under the procedure of claim 1. When r is 0, the covered region and also the only step region is the original axb rectangle. The height and width, namely a and b, are both indivisible by n as per the assumption. Suppose the claim is true for values of r upto R. Now consider r = (R + 1). Suppose the tile being removed at the current iteration lies in a step region whose width is W and height Is H. If either W or H is divisible by n, then there must be some other step region with width and height indivisible by n and that region will remain after iteration (R + 1)  as well. But if say W and H are both indivisible by n. After removing the tile in this iteration, the 2 new step regions would have dimensions (a) (W, H - 1) and (W - n, H) or (b) (W, H - n) and (W - 1, H), depending on the orientation of the tile; in either case, one of the new step regions would have its width and height indivisible by n. Hence proved.

Diagram 1: Step blocks denoted by shaded blue regions

Diagram 2: Width of step regions are denoted by L1 and L2; heights are denoted by H1 and H2. The rectangle  bounded by blue and red lines is the top left tile of its step block and is eligible for removal as per the procedure of claim 1

Saturday, January 26, 2013

A simple number theory problem

Divisibility puzzle: Suppose that there are n integers which have the following
property: the difference between the product of any n - 1 integers and
the remaining one is divisible by n . Prove that the sum of the square of
these n numbers is also divisible by n.

Solution:
Denote the n integers by a1, a2, a3, .., an. By the given property, it follows that:


(a1 – a2 a3…an) = k1n
(a2 – a1 a3 ...an) = k2n
(an – a1 a2… an-1) = knn

where k1, k2, .., kn are some integers. By multiplying equation 1 above by a1, similarly equation 2 by a2 and so on till the last equation above (which would be multiplied by an), the following set of equations are obtained:

a12 – C = k1na1
a22 – C = k2na2
...
an2 – C = knnan

where C = a1 a2 a3 ...an.

Summing the above equations and then rearranging leads to:
(a12+ a22 + … + an2) = nC  + n(k1a1 + k2a2 + … + knan)  = n(C + k1a1 + k2a2 + … + knan)

which proves that the sum of squares of the n integers (a1, a2, a3, .., an) is a multiple of n.