Category Archives: Problem Solving

A sequence I didn’t like

Standard

Following is a problem I encountered many times in my high school olympiads, but was never able to solve it. Hence didn’t like it.

What is the 100th term in the sequence 1,2,2,3,3,3,4,4,4,4,5,\ldots?

Following is a quick solution:

In this post, I will discuss the solution given in The Green Book of Mathematical Problems (problem 14).

Determine a function f(n) such that the n^{th} term of the sequence 1,2,2,3,3,3,4,4,4,4,5,\ldots is given by \lfloor f(n)\rfloor.

Let’s denote the n^{th} number of the sequence by a_n, i.e. a_n=\lfloor f(n)\rfloor. The integer m first occurs in the sequence when each of the integers from 1 to m-1 have already appeared 1 to m-1 times, respectively. Hence, if a_n=m then
n = [1 + 2 + 3 + \ldots + (m-1)]+1 +\ell = \frac{m(m-1)}{2} + 1 + \ell
for \ell = 0,1,2,\ldots, m-1.

Hence we have:
\displaystyle{0\leq n - \frac{m(m-1)}{2} - 1 \leq m-1}

\displaystyle{\Rightarrow \frac{m^2-m+2}{2}\leq n \leq \frac{m^2+m}{2}}

\displaystyle{\Rightarrow m^2-m+2\leq 2n \leq m^2+m}

\displaystyle{\Rightarrow \left(m-\frac{1}{2}\right)^2+\frac{7}{4}\leq 2n \leq \left(m+\frac{1}{2}\right)^2-\frac{1}{4}}

\displaystyle{\Rightarrow (2m-1)^2+7\leq 8n \leq (2m+1)^2 - 1}

\displaystyle{\Rightarrow (2m-1)^2 \leq 8n - 7 \leq (2m+1)^2 - 8}

\displaystyle{\Rightarrow (2m-1)^2 \leq 8n - 7 < (2m+1)^2}

\displaystyle{\Rightarrow 2m-1 \leq \sqrt{8n-7}<2m+1}

\displaystyle{\Rightarrow m \leq \frac{1+\sqrt{8n-7}}{2} < m+1}

\displaystyle{\Rightarrow m=\left\lfloor \frac{1+\sqrt{8n-7}}{2} \right\rfloor}

Hence we have a_n = \left\lfloor \frac{1+\sqrt{8n-7}}{2} \right\rfloor. Thus, we have

\displaystyle{\boxed{f(n) =\frac{1+\sqrt{8n-7}}{2}}}

Now compared to the earlier solution obtained by observing the pattern, one might ask “Is there is a better formula?”. For that, you might also look at the discussion at Math.SE.

Advertisements

Prime Number Problem

Standard

Following is a problem about prime factorization of the sum of consecutive odd primes. (source: problem 80 from The Green Book of Mathematical Problems)

Prove that the sum of two consecutive odd primes is the product of at least three (possibly repeated) prime factors.

The first thing to observe is that sum of odd numbers is even, hence the sum of two consecutive odd primes will be divisible by 2. Let’s see factorization of some of the examples:

3 + 5 = 2\times 2 \times 2
5 + 7 = 2 \times 2\times 3
7+11 = 2 \times 3\times 3
11+13 = 2 \times 2 \times 2 \times 3
13+17 = 2 \times 3 \times 5
17+19 = 2\times 2\times 3 \times 3
19+23 = 42 = 2\times 3\times 7
23+29 = 52 = 2\times 2 \times 13

Now let p_n and p_{n+1} be the consecutive odd primes, then from above observations we can conjecture that either p_n+p_{n+1} is product of at least three distinct primes or p_n+p_{n+1}= 2^k p^\ell for some odd prime p such that k+\ell \geq 3.

To prove our conjecture, let’s assume that p_n+p_{n+1} is NOT a product of three (or more) distinct primes (otherwise we are done). Now we will have to show that if p_n+p_{n+1}= 2^k p^\ell for some odd prime p then k+\ell \geq 3.

If \ell = 0 then we should have k\geq 3. This is true since 3+5=8.

Now let \ell > 0. Since k\geq 1 (sum of odd numbers is even), we just need to show that k=1, \ell=1 is not possible. On the contrary, let’s assume that k=1,\ell = 1. Then p_n+p_{n+1} = 2p. By arithmetic mean property, we have

\displaystyle{p_n < \frac{p_n+p_{n+1}}{2}} = p <p_{n+1}

But, this contradicts the fact that p_n,p_{n+1} are consecutive primes. Hence completing the proof of our conjecture.


This is a nice problem where we are equating the sum of prime numbers to product of prime numbers. Please let me know the flaws in my solution (if any) in the comments.

Birch and Swinnerton-Dyer Conjecture

Standard

This is part of the 6 unsolved Millennium Problems. Following is a beautiful exposition of the statement and consequences of this conjecture:

Anybody with high-school level knowledge can benefit from this video.

Counting Cards – I

Standard

You would have seen the bad consequences of “counting cards” in blackjack game in casinos in movies like Rain Man and 21. This method allows the player to play a perfect game so that the odds are in the player’s favour to win.

In this post, let’s first understand what is blackjack. Most parts have been shamelessly copied from http://www.bicyclecards.com/how-to-play/blackjack/ . You can consider this post to be a tl;dr. If not happy, consider SMMRY.

In the casino version, the house is the dealer. The dealer remains standing and the players are seated. The dealer is in charge of running all aspects of the game, from shuffling and dealing the cards to handling all bets. Between one and eight standard 52-card decks are shuffled together and the cards are dealt from a shoe (a box that allows the dealer to remove cards one at a time, face down, without actually holding one or more packs).  Each card has some value assigned to it. It is up to each individual player if an ace is worth 1 or 11. Face cards are 10 and any other card is its pip value.   A hand’s value is the sum of the card values. Each participant attempts to beat the dealer by getting a count as close to 21 as possible, without going over 21.

When all the players have placed their bets, the dealer gives one card face up to each player in rotation clockwise, and then one card face up to himself. Another round of cards is then dealt face up to each player, but the dealer takes his second card face down. Thus, each player except the dealer receives two cards face up, and the dealer receives one card face up and one card face down. If a player’s first two cards are an ace and a “ten-card” (a picture card or 10), giving him a count of 21 in two cards, this is a natural or “blackjack.”  If the dealer’s face-up card is a ten-card or an ace, he/she looks at his face-down card to see if the two cards make a natural. If the face-up card is not a ten-card or an ace, he/she does not look at the face-down card until it is the dealer’s turn to play.

The player to the left of the dealer goes first and must decide whether to “stand” (not ask for another card) or “hit” (ask for another card in an attempt to get closer to a count of 21, or even hit 21 exactly). Thus, a player may stand on the two cards originally dealt him, or he/she may ask the dealer for additional cards, one at a time until he/she either decides to stand on the total (if it is 21 or under) or goes “bust” (if it is over 21).  The dealer then turns to the next player to his left and serves him in the same manner.

When the dealer has served every player, his face-down card is turned up. If the total is 17 or more, he/she must stand. If the total is 16 or under, he/she must take a card. He/she must continue to take cards until the total is 17 or more, at which point the dealer must stand. If the dealer has an ace, and counting it as 11 would bring his total to 17 or more (but not over 21), he/she must count the ace as 11 and stand.

There are three special moves called splitting pairs, doubling down and insurance.

  • Splitting pairs is possible if a player’s first two cards are of the same denomination, such as two jacks or two sixes. The player may choose to treat them as two separate hands when his/her turn comes around. The amount of his/her original bet then goes on one of the cards, and an equal amount must be placed as a bet on the other card.
  • Doubling down is possible when the original two cards dealt total 9, 10, or 11. When the player’s turn comes, he/she places a bet equal to the original bet, i.e. doubling his/her bet, and the dealer gives him/her just one card, which is placed face down and is not turned up until the bets are settled at the end of the hand.
  • Insurance is possible when the dealer’s face-up card is an ace.  Any of the players may make a side bet of up to half the original bet that the dealer’s face-down card is a ten-card, and thus a blackjack for the house.  Insurance is invariably not a good proposition for the player unless he/she is quite sure that there are an unusually high number of ten-cards still left undealt.

Happy Birthday Ramanujam

Standard

Today is the 130th birthday of Srinivasa Ramanujam Iyengar.

I will discuss the easiest-to-follow work of Ramanujam, from G. H. Hardy’s Ramanujan: Twelve lectures on subjects suggested by his life and work.

A partition of n is a division of n into any number of positive integral parts. Thus, the sum of digits of 130 = 1+3+0=4 has 5 partitions:

\displaystyle{4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1}

The order in which the partitions are arranged is irrelevant, so we may think of them, as arranged in descending order. We denote the number of partitons of n by p(n); thus p(4) = 5. Also, by convention, we define p(0) = 1.

Very little was known about the arithmetical properties of p(n); when Ramanujam started his investigations. Though we still don’t know when p(n) is even or odd, there has been a lot of progress in this domain of research. For an overview, see the first section of Ken Ono’s “Distribution of the partition function modulo m” (it’s 17-year-old paper…)

Ramanujam was the first, and up to his death, the only, mathematician to discover the arithmetical properties of p(n). His theorems were discovered by observing Percy MacMahon‘s table of p(n) for the first 200 values of n. Ramanujan observed that the table indicated certain simple congruence properties of p(n). In particular, the numbers of the partitions of numbers 5m+4, 7m+5 and 11m+6 are divisible by 5, 7 and 11 respectively, i.e.

  • p(5m+4) \equiv 0 \pmod{5}
  • p(7m+5) \equiv 0 \pmod{7}
  • p(11m+6) \equiv 0 \pmod{11}

Hence, for example, for n=130+1 (Chinese way of calculating age) p(131) \equiv 0 \pmod{7}. And we can verify this using SageMath:

part

Now, to check its divisibility by 7, take the last digit of the number you’re testing and double it. Then, subtract this number from the rest of the remaining digits. If this new number is either 0 or if it’s a number that’s divisible by 7, then the original number is divisible by seven. [Derive it yourself!]

This process is lengthy but it converts the process of division by a simpler operation of subtraction.

Here, we have:

5964539504 \rightarrow 596453942\rightarrow 59645390\rightarrow 5964539\rightarrow 596435\rightarrow 59633\rightarrow 5957\rightarrow 581\rightarrow 56 = 7\times 8.

If you know how SageMath calculates the number of partitions, please let me know in the comments below.

Childhood Maths – II

Standard

I found two documents that I was very proud of as a child. Both were the result of trying to understand the kind of things Ramanujan did in free time, a result of the little AMTI books I read as a child. I will share the second document in this post and the other one was in the previous post.

Following document was created in MS Word on my old Windows XP desktop. The calculations were done using some Microsoft advanced calculator:

primes

I was not happy with the result though since the pattern didn’t continue which was supposed to continue according to Ramanujan.