Skip to main content

Trust Issues

Hi, I am Debayu and this is my second blogpost !! We start off with the following problem. 

Problem: Find the sum of all $b$ such that $$2n+1 \mid \binom{2n}{b} -1$$ for all $n$ such that $2n \geq b$.

At first glance, this looks somewhat innocent and its probably some problem from some random computational contest, some may this can be what the IOQM 10 markers will look like this year. hmmm so what do we do here? Let's check what happens when $b$ is $2$. So we have that for all $n$, $$2n+1 \mid \binom{2n}{2}$$ $$\iff 2n+1 \mid n(2n-1)-1=2n^2-n-1$$ $$ \iff 2n+1 \mid |2n^2-n-1-n(2n+1)| = |-2n-1|$$ which is true so yay $2$ works. Now we might want to check $b=3$, this means $$2n+1 \mid \binom{2n}{3}$$ $$\iff  2n +1 \mid \frac{n(2n-1)(2n-2)}{3}$$ $$\iff 6n+3 \mid 4n^3-6n^2+2n$$ from here, it is easy to see that if $n$ is even, the divisibility wont hold so $3$ doesn't work. Similarly one can check that $4$ doesn't work either and one might guess that the only possible $b$ is $2$ which is actually correct but proving this seems really hard. One idea probably is to try to prove that $b$ should always be even or $b$ is always a prime but it seems pretty counterintuitive to do that since $4$ and $3$ don't work and both the claims seem very weak, but there doesn't seem to be too much to do either. Anyways let's see what we can do, lets begin with expanding the thing we have,

$$\binom{2n}{b}-1= \frac{(2n)!}{b!(2n-b)!}-1=\frac{(2n)(2n-1)\cdots(2n-b+1)}{b!}-1$$

Hmm, not too shaggy, lets see what happens when we take this modulo $2n+1$,

$$\frac{(2n)(2n-1)\cdots(2n-b+1)}{b!} - 1 \equiv \frac{(-1)(-2)\cdots(-b)}{b!}-1 \equiv (-1)^b -1 \pmod{2n+1}$$

Woah so indeed $b$ must be even, so we finally have some progress but what do we do now. There seems to be nothing to do since $2$ gives us very less information and expanding binomial coefficients is not the best idea as they can turn ugly really quick. What do you do when nothing else makes sense? Magic? Yes, let's generalize the problem by replacing $a$ with $2$ since $2$ is the most trashy number ever. Here we have our new problem,

Magically Generalized Problem: Find all $b$ such that $$an+1 \mid \binom{an}{b} -1$$ for all $n$ such that $an \geq b$.

Wait wait, this doesn't trivialize the problem in any way so don't leave your seats, this just gives you more space to work with. Also notice that we don't have the sum thing in the problem now as it might be that there are infinitely many such $b$. Now recall Dirichlet's Theorem,

Dirichlet's Theorem: There are infinitely many primes dividing an AP $(an+b)_{n \geq 0}$ with $gcd(a, b)=1$.

Obviously, we have $gcd(a, 1)=1$ so we can probably pick big primes dividing $an+1$ to mess all the numbers that don't work. From here the key idea is to notice that if we have primes smaller than $b$ then we can probably mess with the $\nu_p$, to avoid that we might want to prove that all primes $p \leq b$ divide $a$.

Now suppose the above thing is not true, then pick $p^{huge} | an+1$ which is possible since we are assuming $gcd(a, p)=1$. This means,

$$\nu_p (\binom{an}{b}) = \nu_p((an)(an-1)\cdots (an-b+1)) -\nu_p(b!) > 0$$ but then $an+1$ wont divide $\binom{an}{b}-1$ so indeed what we wanted to prove is correct. IIRC these two conditions actually fully characterize all such numbers which is really cool. 

Now returning to the original problem, we had $a=2$, so the only possible $b$ is $2$ since all primes $\leq b$ must divide $a$ so we are done!!

You probably know by now how bad you got scammed, this was nothing but 2019 N5, here's the problem statement of it if you are still having trust issues.

ISL 2019 N5: Let $a$ be a positive integer. We say that a positive integer $b$ is $a$-good if $\tbinom{an}{b}-1$ is divisible by $an+1$ for all positive integers $n$ with $an \geq b$. Suppose $b$ is a positive integer such that $b$ is $a$-good, but $b+2$ is not $a$-good. Prove that $b+1$ is prime.

Here, notice that for $b+2$ to be bad, you need either $b+1$ or $b+1$ to be prime but $b$ is even so $b+1$ has to be prime.

See dont be mad at me, I know I probably just gave you trust issues for the rest your life but firstly there exist things that will make you have even more of them like,

and secondly, you have more scam ammunition with you now to scam even more people.

Credits: Ameya

"Scams are like rickrolls, the first thing to do after getting scammed is to scam them back" - Me?

Now, I shall introduce you to a very cool theorem!!

Lucas' Theorem: Given natural numbers $m$ and $n$ expressed in base $p$,

$$m=m_kp^k+m_{k-1}p^{k-1}+\cdots+m_1p+m_0, \text{and}$$

$$n = n_kp^k +n_{k-1}p^{k-1}+\cdots+n_1p+n_0,$$

where $p$ is a prime, we have 

$$\binom{m}{n} \equiv \binom{m_k}{n_k}\binom{m_{k-1}}{n_{k-1}}\cdots \binom{m_0}{n_0} \pmod{p}$$

It makes some sense why we might want to use it, I will just present the proof of our main claim which uses lucas', I first came to know about this after I saw Aryan's proof to it. The key idea is that if one of the binomials in the RHS is $0$ then the whole thing just breaks down and that happens which its like $\binom{0}{\text{non-zero}}$.

Proof: Assume contradiction. Consider the base $p$ representation of $b = m_ip^i+m_{i-1}p^{i-1}+\cdots+m_1p+m_0$. Since $p \geq b$, it must have a non-zero $m_j$ other than $m_0$. Now we pick $n$ such that the base $p$ representation of $an$ has the coefficient associated with $p^k$ to be $0$, this is possible since $an+1$ can span all residues $\pmod{p^{k+1}}$ from our assumption. By lucas', $\binom{an}{b} \equiv 0 \pmod{p}$ which is a contradiction. $\blacksquare$

If you want to read more about lucas', you can refer to this article. That was all for today!! I hope you have major trust issues now, I mean I hope you enjoyed!! :P


Post a Comment

Popular posts from this blog

LMAO Revenge

Continuing the tradition of past years, our seniors at the Indian IMO camp(an unofficial one happened this year) once again conducted LMAO, essentially ELMO but Indian. Sadly, only those who were in the unofficial IMOTC conducted by Pranav, Atul, Sunaina, Gunjan and others could participate in that. We all were super excited for the problems but I ended up not really trying the problems because of school things and stuff yet I solved problem 1 or so did I think. Problem 1:  There is a   grid of real numbers. In a move, you can pick any real number  ,  and any row or column and replace every entry   in it with  .  Is it possible to reach any grid from any other by a finite sequence of such moves? It turned out that I fakesolved and oh my god I was so disgusted, no way this proof could be false and then when I was asked Atul, it turns out that even my answer was wrong and he didn't even read the proof, this made me even more angry and guess what? I was not alone, Krutarth too fakesol

The importance of "intuition" in geometry

Hii everyone! Today I will be discussing a few geometry problems in which once you "guess" or "claim" the important things, then the problem can easily be finished using not-so-fancy techniques (e.g. angle chasing, power-of-point etc. Sometimes you would want to use inversion or projective geometry but once you have figured out that some particular synthetic property should hold, the finish shouldn't be that non trivial) This post stresses more about intuition rather than being rigorous. When I did these problems myself, I used freehand diagrams (not geogebra or ruler/compass) because I feel that gives a lot more freedom to you. By freedom, I mean, the power to guess. To elaborate on this - Suppose you drew a perfect  diagram on paper using ruler and compass, then you would be too rigid on what is true in the diagram which you drew. But sometimes that might just be a coincidence. e.g. Let's say a question says $D$ is a random point on segment $BC$, so maybe

Edge querying in graph theory

In this post, I will present three graph theory problems in increasing difficulty, each with a common theme that one would determine a property of an edge in a complete graph through repeated iterations, and seek to achieve a greater objective. ESPR Summer Program Application: Alice and Bob play the following game on a $K_n$ ($n\ge 3$): initially all edges are uncolored, and each turn, Alice chooses an uncolored edge then Bob chooses to color it red or blue. The game ends when any vertex is adjacent to $n-1$ red edges, or when every edge is colored; Bob wins if and only if both condition holds at that time. Devise a winning strategy for Bob. This is more of a warm-up to the post, since it has a different flavor from the other two problems, and isn't as demanding in terms of experience with combinatorics. However, do note that when this problem was first presented, applicants did not know the winner ahead of time; it would be difficult to believe that Bob can hold such a strong