Monthly Archives: April 2015

by

Hilbert matrices are positive definite

(Argument stolen from Yahoo Answers)

It can be seen by using its integral form:

\displaystyle H_{ij} = \int_0^1 dx\,x^{i+j-2}

Then we can express the positive definite condition as

\displaystyle \sum_{i,j} x_i H_{ij} x_j > 0

for \mathbf{x} \ne 0.

Replacing and operating:

\displaystyle \sum_{i,j} x_i \int_0^1 du\,u^{i+j-2} x_j = \int_0^1 du \sum_{i,j} x_i u^{i+j-2} x_j

\displaystyle = \int_0^1 du \sum_{i,j} x_i u^{i-1} x_j u^{j-1}

\displaystyle = \int_0^1 du \sum_i x_i u^{i-1} \sum_j x_j u^{j-1}

\displaystyle = \int_0^1 du \left( \sum_i x_i u^{i-1} \right) \left( \sum_j x_j u^{j-1} \right)

\displaystyle = \int_0^1 du \left( \sum_i x_i u^{i-1} \right)^2

The term inside the parentheses is just a (polynomial) function of u:

\displaystyle = \int_0^1 du\,p(u)^2

The only way the integral can be zero is if p(u) is identically zero:

\displaystyle \sum_i x_i u^{i-1} = 0 \implies \forall i: x_i = 0.

QED

Advertisement
by

Solving the viral Singaporean math problem

The following problem has become very popular in social media:

math3-superJumbo-v2

In this blog we have solved similar problems before, but this is one that can be easily solved by hand. We only need to be careful not to confuse our knowledge state with the one of Albert & Bernard.

Albert and Bernard just became friends with Cheryl, and they want to know when her birthday is. Cheryl gives them a list of 10 possible dates.

May 15 May 16 May 19

June 17 June 18

July 14 July 16

August 14 August 15 August 17

Cheryl then tells Albert and Bernard separately the month and the day of her birthday, respectively.

We will describe a list of the possible knowledge states of Albert and Bernard after being given that information:

Albert
  1. May 15 or May or May 19
  2. June 17 or June 18
  3. July 14 or July 16
  4. August 14 or August 15 or August 17
Bernard
  1. July 14 or August 14
  2. May 15 or August 15
  3. May 16 or July 16
  4. June 17 or August 17
  5. June 18
  6. May 19

Albert: I don’t know when Cheryl’s birthday is, but I know that Bernard does not know, too.

We already knew that Albert wouldn’t know the day based just on being given the month, but he is giving us additional information by telling us that he knows that Bernard doesn’t know. Bernard would know the date if the day were 18 or 19, so Albert knows that those days could not be the right ones. That excludes options 1 and 2 from our knowledge of Albert knowledge:

Albert
  1. July 14 or July 16
  2. August 14 or August 15 or August 17

Bernard can do the same deductions we have and eliminate the options that are not possible from his state of knowledge (all the options with months different from July and August).

Bernard
  1. July 14 or August 14
  2. August 15
  3. July 16
  4. August 17

Bernard: At first, I didn’t know when Cheryl’s birthday is, but I know now.

Updating our knowledge of Bernard knowledge:

Bernard
  1. August 15
  2. July 16
  3. August 17

As Albert also knows what we know about Bernard knowledge…

Albert
  1. July 16
  2. August 15 or August 17

Albert: Then I also know when Cheryl’s birthday is.

Now we know the right date:

Albert
  1. July 16
Bernard
  1. July 16
by

42 code golf

A nice and easy interview problem (link not posted to avoid giving good answers) is the following:

Print the number of integers below one million whose decimal digits sum to 42.

It can be solved with some simple Python code like the following:

print sum(1 if sum(int(c) for c in '%d' % n) == 42 else 0
          for n in range(1000000))

A more interesting problem is to try to write the smallest C program that solves the problem, where C program is defined as something that can be compiled & executed by Ideone in “C” mode. I know it can be done in 83 bytes, but can it be done using less?