cozilikethinking

4 out of 5 dentists recommend this WordPress.com site

An interesting Putnam problem on the Pigeonhole Principle

The following problem is contained in the book “Putnam and Beyond” by Gelca, and I saw it on stackexchange. I’m mainly recording this solution because it took me longer than usual to come up with the solution, as I was led down the wrong path many a time. Noting what is sufficient for a block of numbers to be a square is the main challenge in solving this problem.

Let there be a sequence of m terms, all of which belong to a set of n natural numbers. Prove that if 2^n\leq m, then there exists a block of consecutive terms, the product of which is a square number.

Let the n numbers be \{a_1,\dots,a_n\}, and consider the function f(k)=( a tuple of 0‘s and 1‘s), where the 0‘s and 1‘s denote the number of times \pmod 2 that each element a_i has appeared from the 1st to the kth element of the sequence of positive integers.

So f(1)=(1 somewhere, and the rest of the terms are 0), etc.

Clearly, if f(k)=(0,0,\dots,0) for any k, then the consecutive sequence of numbers from the 1st term to the kth terms is a square. If no f(k) is (0,0,0\dots,0), then there are 2^m-1 such tuples, and at least 2^m values of k. Hence, two of them must be equal. Let us suppose that f(k_1)=f(k_2). Then the sequence of terms from k_1 until k_2 is a square. Hence proved.

Proving that the first two and last two indices of the Riemann curvature tensor commute

I’ve always been confused with the combinatorial aspect of proving the properties of the Riemann curvature tensor. I want to record my proof of the fact that R(X,Y,Z,W)=R(Z,W,X,Y). This is different from the standard proof given in books. I have been unable to prove this theorem in the past, and hence am happy to write down my proof finally.

Define the function f(R(X,Y,Z,W))=R(X,Y,Z,W)-R(Z,W,X,Y). We want to prove that this function is 0.

By simple usage of the facts that R(X,Y,Z,W)+R(Y,Z,X,W)+(R(Z,X,Y,W)=0 and that switching the first two or last two vector fields gives us a negative sign, we can see that

R(X,Y,Z,W)-R(Z,W,X,Y)=R(X,W,Y,Z)-R(Y,Z,X,W).

Hence, f(R((X,Y,Z,W))=f(R(X,W,Y,Z))
Now note that R(X,Y,Z,W)=R(Y,X,W,Z). This is obtained by switching the first two and last two indices. However,

R(Y,X,W,Z)-R(W,Z,Y,X)=R(Y,Z,X,W)-R(X,W,Y,Z)=-f(R(X,W,Y,Z).

As f(R(X,Y,Z,W))= both positive and negative f(R(X,W,Y,Z)), we can conclude that it is 0.

Hence, R(X,Y,Z,W)=R(Z,W,X,Y).

It is not easy to prove this theorem because just manipulating the indices mindlessly (or even with some gameplan) can lead you down a rabbithole without ever reaching a conclusion. Meta-observations, like the above, are necessary to prove this assertion.