Fruits of procrastination

Month: April, 2020

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.

(More or less) Effective Altruism- March and April

In March, I donated $250 to EA

Screen Shot 2020-03-13 at 9.53.46 AM

In April, I decided to donate $250 instead to the Association for India’s Development to fight coronavirus in India:

Screen Shot 2020-04-07 at 9.19.23 AM

Thinking about a notorious Putnam problem

Consider the following Putnam question from the 2018 exam:

Consider a smooth function f:\Bbb{R}\to\Bbb{R} such that f\geq 0, and f(0)=0 and f(1)=1. Prove that there exists a point x and a positive integer n such that f^{(n)}(x)<0.

This is a problem from the 2018 Putnam, and only 10 students were able to solve it completely, making it the hardest question on the exam. I spent a day thinking about it, and my “proof” differs a lot from the official solutions, and is really a heuristic.

Proof: Assume that there does not exist any x and n such that f^{(n)}(x)<0. We will compare f with functions of the form x^n in [0,1]. We will prove that f\leq x^n on [0,1]. Because x^n\to 0 on [0,1) as n\to\infty, we will have proven that f=0 on [0,1) and f(1)=1. Hence, f cannot be smooth.

Why is f\leq x^n? Let us first analyze what f looks like. It is easy to see that f(x)=0 for x\leq 0. This is because as f\geq 0, if f(x)>0 for x<0, when f will have to decrease to 0 at x=0. Hence, there will be a negative derivative involved, which is a contradiction. Hence, f(x)=0 for x\leq 0, and by continuity of derivatives for smooth functions, all derivatives at x=0 are also 0.

Now consider the functions x^n, which are 0 at x=0 and 1 at x=1. These are the same endpoints for f(x) in [0,1]. If f(x) ever crosses x^n in [0,1), then it will have a higher nth derivative than x^n at the point of intersection. As its (n+1)th derivative is also non-negative, f will just keep shooting above x^n, and hence never “return” to x^n at x=1. This contradicts the fact that f(1)=1. Hence, f will always be bounded above by x^n in [0,1]. As this is true for all n, f=0 on [0,1) and f(1)=1. This contradicts the fact that f is continuous.

Putnam 2010

The Putnam exam is one of the hardest and most prestigious mathematical exams. Every year, more than 4,000 students, including math olympiad medalists from various countries, attempt the exam. The median score, almost every year, is 0. Each correctly answered question is worth 10 points

I often find myself trying to solve old Putnam problems, mainly because it serves as a way of “mathematical” procrastination- something that detracts me from my actual job of trying to solve my research problem. Yesterday, I ended up solving most questions from the 2010 Putnam paper. This is probably due to the fact that 2010 was one of the easiest papers in the recent past. When I compared my solutions with the solutions online, they turned out to be pretty different. Hence, I am recording them here.

The problems can be found here

A1: We need to find the largest number of boxes. Clearly, we need to place as few elements as possible in each box. If n is odd, then assume that we can place the largest element n in a box by itself. All the other boxes contain elements of the form \{i,n-i\}. Hence, we can have \frac{n+1}{2} boxes. Why can we not have an even larger number of boxes? Let a be the lowest number of elements in a box. If a=1, then the configuration above is the only possibility. If a\geq 2, then there are at most \frac{n-1}{2} boxes, which is lower than the number of boxes we have obtained above (\frac{n+1}{2}).

If n is even, then one such configuration is \{i,n+1-i\}. Using an argument similar to that given above, we can conclude that the highest number of boxes possible is \frac{n}{2}.

A2: First we prove that the derivative of the function above is periodic with period 1. For some x, we know that

f'(x)=\frac{f(x+2)-f(x)}{2}=\frac{f(x+2)-f(x+1)}{2}+\frac{f(x+1)-f(x)}{2}=\frac{f(x+2)-f(x+1)}{2}+\frac{1}{2}f'(x).

Hence, f'(x+1)=\frac{f(x+2)-f(x+1)}{1}=f'(x). This way, we have proven that the derivative of f is periodic with period 1.

What this shows is it that the function repeats the same “shape” every time we move to the right or left by 1. If f is not a straight line, then there will be two points in [0,1] with different derivatives. Let us also assume without loss of generality that f(1)>f(0). Hence, f'(0)=\frac{f(1)-f(0)}{1} is positive. Let p\in[0,1] be the point with a derivative that is different from f'(0). However, f'(p)=\frac{f(p+1)-f(p)}{1} will be the same as f'(0) because f(p+1)-f(p)=f(1)-f(0). This is because the function repeats its shape with a period of 1. Hence,

f(p+1)-f(p)=\int_p^{p+1}{f'(x)} dx=\int_p^1 f'(x)dx+\int _0^p f'(x)dx=f(1)-f(0).

This contradicts the fact that f'(p)\neq f'(0).

Therefore, as the derivative at all points is the same, straight lines are the only solutions.

A3: Consider the curve \gamma: t\to (at,bt). Clearly, a\frac{dh}{dx}+b\frac{dh}{dy}=\frac{\partial}{\partial t}h(\gamma(t)). Now as h(\gamma(t))=\frac{\partial}{\partial t}h(\gamma(t)), clearly h(\gamma(t) is exponential, at least along \gamma. That contradicts the fact that h is bounded.

A4: Let n=2^ab, where b is not a power of 2. Then we claim that 10^{10^{10^n}}+10^{10^n}+10^n-1 is divisible by 10^{2^a}+1.

Proof: 10^n\equiv -1\pmod {10^{2^a}+1}.

Now 10^{10^n}=10^{10^{2^a b}}=10^{2^{2^a b}5^{2^a b}}=(10^{2^a})^{2^{2^ab-a}5^{2^ab}}. Hence, it is \equiv 1 \pmod {10^{2^a}+1}.

Similarly, 10^{10^{10^n}}\equiv 1\pmod {10^{2^a}+1}. Adding the residues up, we see that 10^{10^{10^n}}+10^{10^n}+10^n-1\equiv 0\pmod{10^{2^a}+1}

B1: Let us assume that this is true. Then we have a_1^2+a_2^2+\dots+a_n^2+\dots=2. If any of these elements, say a_i, is greater than 1, then a_i^{2n} will be much greater than 2n for large enough n. Hence, this contradicts the fact that a_1^{2n}+\dots+a_i^{2n}+\dots=2n. Therefore, all the a_i‘s are less than 1. The a_i‘s that are exactly equal to \{\pm 1\}, we can remove by subtracting them from the left hand side. Now for these numbers that are less than 1, as we increase n, \sum a_i^n is a decreasing sequence. However, the right hand side, which is n, is an increasing sequence. This is a contradiction. Therefore, no such sequence exists.

B2: The smallest such length is 3. Let A=(0,0). If the smallest length is 1, then without loss of generality let B=(1,0). Note that if C=(x,y), then both \sqrt{x^2+y^2} and \sqrt{(x-1)^2+y^2} need to be integers. This is impossible. Similarly, if the smallest length is 2, then without loss of generality, we can assume that B=(-2,0). Then if C=(x,y), then both \sqrt{x^2+y^2} and \sqrt{(x-2)^2+y^2} need to be integers. This can also be seen to be impossible, by a simple case by case analysis. Note that (n+1)^2-n^2=2n+1. Hence, the difference between \sqrt{x^2+y^2} and \sqrt{(x+2)^2+y^2} must be at least twice the smaller number plus 1. Without loss of generality, we can assume that x,y\geq 1 (y\neq 0 as the three points are not collinear). This leaves only a couple of possibilities for x,y which can be checked by hand to not be possible. Hence the minimum length is 3, which gives us the regular pythagorean triangle with sides 3,4,5. The coordinate of the points will be (0,0), (3,0) and (0,4).

B3: This is indeed a fantastic problem, with a simple solution: first transfer all the balls to B_1, and then transfer them one by one to the other baskets. As we can only draw i balls from the B_ith basket, we need to ensure that at least one basket B_i is such that it has i balls. Otherwise, no balls can be moved from the initial configuration. Hence, the minimal number of balls is 0+1+\dots+2009+1=\frac{2009\times 2010}{2}+1. Hence, the minimal value of n is the upper floor value of this number divided by 2010, which is 1005.

B5: This is a pretty tricky problem. The way that I finally thought through is is to visualize what f(f(x)) would look like for an increasing function f(x). If f(x) is always positive, then f(f(x)) for x\to-\infty would be within an \epsilon distance of a fixed positive number, which is a contradiction as f'(x) gets arbitrarily close to 0 for x\to -\infty. Now we shall allow f(x) to be negative. If f(x) is not bounded below, then there will exist negative x such that f(f(x)) will be negative. This contradicts the fact that f'(x) is always non-negative. Now consider f(x) which is bounded below, but can still be negative. Clearly f(x) has to become positive at some point, as f'(x) must be positive. If it becomes positive only when x>0, then f(f(x)) for x<0 will still be negative, which is a contradiction as f'(x)=f(f(x)) must be non-negative. Let -a (a is assumed to be positive here) be \lim\limits_{x\to-\infty} f(x). If f(x) becomes positive when x>-a, then f(f(x)) for x\to-\infty will be negative, which is again a contradiction. Hence, f(x) has to become positive for x<-a. Now if f(-a)>0, then f(f(x)) for x\to -\infty will be arbitrarily close to a fixed positive number, which is a contradiction as f'(x) for x\to -\infty approaches 0. Hence, f(a) must be 0.

Hence, the only remaining possibility is a function f(x) such that \lim\limits_{x\to -\infty} f(x)=-a and f(-a)=0. Let us analyze this function. We know that f'(-a)=f(0). Also, for x\in(-a,0], f'(x)>f(0). Hence, f(0)>af'(-a). This implies that a<1. I haven’t yet determined how to eliminate this case.