Loading [MathJax]/jax/output/HTML-CSS/jax.js

Monday, February 17, 2025

Real root of 1=x+x3, powers and rational sums

 Let a be the unique real number that satisfies 1=a+a3.

Let S be any non-empty finite subset of the powers of a, i.e. S{a1,a2,a3,,}.

A ) Show that if the sum of elements of S is rational, then it is either 1 or 2.

B) Find two subsets which sum to 1 and 2 respectively.

C) Show that there are infinite such subsets.

.

.

.

The polynomial P(x)=x3+x+1 is irreducible over integers by Crohn's criteria, since P(2)=11. This implies P(x) is irreducible too. This basically means that a cannot be the root of either a linear or a quadratic equation with integer coefficients. This easily implies the same for rational coefficients. 

We will state the above explicitly as Lemmas.

Lemma 1: a is irrational

Lemma 2: a cannot be a root of Ax2+Bx+C=0, where A,B,C are integers.

Note: we can prove the above lemmas in a more elementary fashion but will not do that here.

To prove A)

Notice that n=1an=a1a=aa3=1a2

We can show that a>13 by using the fact that x3+x1 is monotonic. Thus any finite sum of powers of a is <3.

 Notice a2=1a1. This allows us to make the claim that:

Proposition: For any integer n0, there exist integers An,Bn,Cn such that

an=Ana+Bna+Cn

Proof: Easily proven by induction, using a2=1a1.

Thus the sum of any finite powers of a can be written as

Aa+Ba+C 

for some integers A,B,C.

If that is rational, by Lemmas 1 and 2, we must have that A=B=0, and thus the sum must be C which is an integer.

Since 0<C<3, it must be either 1 or 2.


Part B)

1=a+a3

2=a+a2+a3+a4+a5+a6+a7


Part C)

If N=aj1+aj2++ajk

with jk being the largest, rewrite as

N=aj1+aj2++ajk(a+a3)=aj1++ajk1+a1+jk+a3+jk

to get a representation with k+1 terms instead of k. Repeat to get infinite representations.


Monday, February 10, 2025

Writing 1 as the sum of golden ratio reciprocal powers

 Let φ=1+52 be the golden ratio.


For every positive integer n2, show that there is exactly one way to write 1 as the sum


ni=1φai


where a1<a2<<an are n distinct positive integers


For eg:


1=φ1+φ2=φ1+φ3+φ4






We will start with a few Lemmas.


Let t=φ1 and we will use powers of t for convenience.

Lemma 0: tk=tk+1+tk+2,k0

Proof: Easy to see.  

Lemma 1: For every n1

1=t2n+nj=1t2j1

Proof

We get 

t2n+nj=1t2j1=t2n+t2n1+n1j=1t2j1

=t2n2+n1j=1t2j1

(by applying lemma 0)

By using induction, and 1=t+t2, we are done.

Lemma 2: If a1<a2<a3<an are n distinct positive integers such that ai+1<ai+1,1i<n  (i.e, there aren't consecutive numbers in the ai), then

nj=1taj<1

Proof:

If am{2k1,2k} then tamt2k1

Since no ais are consecutive

nj=1taj<k=1t2k1=1


Now for the main result.

Proposition: Given a positive integer n2, there is exactly one way to write 1 as the sum 

1=nj=1taj

where a1<a2<an are n distinct positive integers.

Proof:

By Lemma 1, we see that there is at least one way.

For n=2 it is easy to see the uniqueness.

We now prove by induction on n.

 Assume uniqueness for n.

Now suppose

1=n+1j=1taj

with a1<a2<<an+1.

By Lemma 2, there is some i such that ai+1=ai+1.

Let i be the least i such that ai+1=ai+1. Note that i>1 (otherwise the whole sum = t+t2+>1).

By Lemma 0, we have that tai1=tai+tai+1. Since i was the least i, there is no j such that aj=ai1.

Thus, we now have a representation using n terms

a1<a2<ai1<ai1<ai+2<<an+1

By induction hypothesis this representation is unique, which must be as written in Lemma 1 and must be the same as 

1<3<5<2n3<2n2


If the newly created term ai1 is one of 1,3,5,,2n3, then we must have ai+1=ai+2 which is not possible.

Hence we see that the original representation using n+1 terms be

1<3<5<<2n3<2n1<2n

Wednesday, January 29, 2025

Nice defense by Arvind Ranasaria

 In the recently concluded Willingdon Swiss pairs tournament in Bombay, my partner from Seattle made a very nice defense.


Arvind had opened 2S (red vs white) with the spades being AKQT9x, and his LHO eventually ended up in 3NT.

I was on lead with 642 of spades and led the 2 of spades.

Dummy showed up with a void and declarer had J8xx.

Arvind smoothly played the SK and followed with the ST!

Declarer now had to guess whether I was leading from Qxx or not. If I had the Q, the correct play is to duck. If not, playing the J was the winning play.

Declarer guessed wrong, and was -2.

Very nice defense!

Friday, January 17, 2025

A cloning problem from a reddit math contest

 A cute problem from reddit.


You have 2n people standing in an infinite row at spots say 1,2,3,..,2n (one person at each spot). A scientist performs the following steps repeatedly.

Clone every person on the row, and move the clones one position the right i.e. if there were x people at position k, you create x clones and place them at position k+1. Note that this is done for every position in parallel (so no moving clones twice etc). Previously empty positions could see folks being moved there.


After 2n1 repeats of the above steps, how many people will be there at position n?

Scroll down for a solution.

.

.

.



Suppose there are pj people at position j (j>=1).

Then the steps is basically replacing pk+1 with pk+1+pk

This looks ripe for matrices, the steps are basically a linear transformation, but the matrix is large, of size 4n1 or so.


There is another way to look at this: polynomials!


Let f(z)=n=1pnzn

(Even though there is infinity, it is still a finite polynomial as all pi=0 after a certain point)


Then the steps are basically replacing f(z) by f(z)(z+1)

Initially f(z)=z+z2++z2n

After 2n1 steps we get

(z+z2++z2n)(1+z)2n1=

(z+z2++z2n)(2n1r=0(2n1r)zr)

(using binomial theorem on (1+z)2n1)

The number of people in row n is coefficient of zn and that comes out to be

nr=0(2n1r)=22n12=22n2

(using (2n1r)=(2n12n1r) and adding them up to get 22n1)


Wednesday, August 7, 2024

3 consecutive summing to 13

 You permute each of the digits 0,1,2,,9 and write them in a single row.


A) Show that no matter what the permutation, some 3 adjacent elements of the row sum to at least 13.

B) Can you find a permutation where no 3 adjacent elements sum to more than 13?


Scroll down for solution



.


.


A) Say the permutation is x0,x1,,x9.


Now one of x0 or x9 is <9. We can assume x0<9.

Let Si=xi+xi+1+xi+2.

Since x0<9 we must have that S1+S4+S7>36 and thus max{S1,S4,S7}>12.


B)  9 3 1 7 4 2 6 0 5 8


Tuesday, July 9, 2024

Peter Winkler's factorial problem

 A cute problem from Peter Winkler's collection of math puzzles.


S={n!|1n100,nN}

Can we remove a single element from S such that the product of the elements of the resulting set is a perfect square?


Scroll down for a solution.




Product of elements of S is

P=1!2!99!100!

Pair up terms (2n1)!(2n)!=((2n1)!)22n

Thus


P=(1!3!5!99!)2(2.4.6100)

=(1!3!5!99!)2.250.50!


Thus removing 50! from S will give us the desired result.

Friday, May 31, 2024

Volume of an n dimensional region

 What is the volume of the region in Rn defined as follows


Vn={(x1,x2,,xn)Rn|xi0 and xi1}


Scroll down for a clever proof (if you know the source, please comment)

.

.

.


Transform the space with yj=1ijxi


This is a linear transformation that gives a new region defined as


Wn={(y1,y2,,yn)Rn|0y1y2yn1}


Wn is just a subset of the hypercube [0,1]n. The hypercube can be split into n! regions of equal volume, each region corresponding to a sort order among the coordinates. Wn is one of them.


Thus volume of Wn is 1n!


Since the determinant of the linear transformation from Vn to Wn is 1, the volume of Vn is 1n! too!

Saturday, April 6, 2024

Exactly 80% success

A basketball player is practising free throws. Their current success rate (ratio of successful throws to total) is exactly 70% (or 0.7 in terms of ratio). After a few more throws that success rate is 90%. 

Show that at some point the success rate was exactly 80%.


Scroll down for a solution




.


Look at (misses, hits) on the integer lattice and x-y coordinate plane. If a miss occurs, we increment x coordinate, else we increment y coordinate.

Initially we are on the line 3y=7x (70% hit rate) and reach the line y=9x (90% hit rate), crossing the line y=4x (80% hit rate) at some point, with some hit (i.e by incrementing the y-coordinate).,

The only way to cross the line y=4x vertically is to actually land on it first (every x = N line intersects y = 4x at (N, 4N) which is part of the integer lattice. Thus we achieve exactly 80%,

Wednesday, February 21, 2024

Product of three consecutive positive integers

 Can the product of three positive consecutive integers be a perfect square?




Scroll down for a solution



.


Assume the three integers are n1,n,n+1 and that (n1)n(n+1)=n(n21) is a perfect square.


Since n is relatively prime to both n1 and n+1 (and hence their product n21), we must have that n21 is a perfect square too.

Friday, January 19, 2024

A problem from INMO

 In a triangle ABC (sides a,b,c opposite A,B,C), angle A is twice B.


Show that a2=b(b+c)


Try not to use trigonometry if possible.



Scroll down for a solution



.


.

Let AD be the angular bisector of A, D lying on BC (might help to draw a figure).


Then by angular bisector theorem

BD=acb+c,DC=abb+c

BAD is isosceles, with AD=BD. Also triangle ADC is similar to triangle BAC.

AD/AB=DC/AC gives the result.


There are non-trigonometric proofs of the angular bisector theorem. For eg, prove for right angled triangles and use affine transform etc.

Sunday, December 24, 2023

An accessible problem from Donald Newman's book

 "A problem Seminar" by Donald J Newman has many excellent problems which require math undergrad/grad knowledge. Below is one of the more accessible problems, solveable by a non-math person.


Each coin is either 10 or 9 grams. Given 4 such coins, find the weight of each using a scale (not a balance, a scale which gives the true weight) no more than 3 times.



Scroll down for a solution.



Suppose the coins are A,B,C,D.

Weigh A+B. It must be 19, otherwise it is trivial. Now weigh A+C. It must be 19, otherwise it is trivial.

Now we must have B=C. Now weigh B+C+D = 2B+D. This has the same parity (odd or even) as D. Thus we know D, which gives us B=C and then A.

Tuesday, August 15, 2023

Sum of squares of distances from vertices of a triangle

 If ABC is a triangle with centroid M, and P is any point then show that


PA2+PB2+PC2=3PM2+13(AB2+BC2+AC2)



Scroll down for a surprising solution.



Let A1,B1,C1 be the midpoints of BC,AC and AB respectively.

Triangle A1B1C1 (referred to as medial triangle of ABC) is similar to ABC 


Using Appolonius theorem we get


PA2+PB2=2(PC21+AC21)=2PC21+2AB24

PB2+PC2=2(PA21+BA21)=2PA21+2BC24

PC2+PA2=2(PB21+CB21)=2PB21+2AC24


Adding we get


PA2+PB2+PC2=PA21+PB21+PC21+AB24+BC24+AC24


Thus if AnBnCn is the medial triangle of An1Bn1Cn1  (ABC=A0B0C0) we have that


PA2n1+PB2n1+PC2n1=PA2n+PB2n+PC2n+An1B2n14+Bn1C2n14+An1C2n14

 

We can easily show that An,Bn,Cn all converge to M (AnM=3An+1M), and observing the above is a telescoping series and that sides of a medial triangle are half the original triangle leads us 


PA2+PB2+PC2=3PM2+AB2+BC2+AC24(1+14+142+)

=3PM2+13(AB2+BC2+AC2)

Tuesday, August 1, 2023

Allow opponents to make a mistake

 Long time no bridge hand!


Here is a puzzle.


You end up in 4S playing a team game (bidding and hands below, you are South).

IMPS 
N/S 
 Partner
♠ xxx
♥ xxx
♦ Kxx
♣ Kxxx

      


 You
♠ QJT9xx
♥ Qx
♦ AQx
♣ AQ

W N E S
1S
P2SP4S
PPP


LHO leads a low heart to RHO's Ace, who leads a heart back to LHO's King and a third heart which you ruff.


You have lost two hearts and have two spades to lose. Situation is hopeless. But, is there anything you can do? If you want to think about it, don't scroll further.




There are no legitimate chances and need a defensive error. If the spades divide Ax opposite Kx, you must hope to induce a first round duck and then crash the A and K together. How could you do that?

The opponents don't know you have a 6 card suit. Consider what might happen if you lead a diamond to dummy's K and then play a spade to the Q! (has to be the Q, no other card will do)

LHO looking at Ax of spades might very well duck, thinking you have KQT9x and have a guess in spades (they hope you go to dummy with CK next and play a spade to the K, setting up partner's J for the setting trick). If you indeed have KQT9x and they win the A from Ax, then you are forced to take the winning line of finessing their partner for the J.

It is a slim chance which is more likely to work against better opponents than not, but then what have you got to lose?

Wednesday, June 14, 2023

Parabola Arc Length

 Here is a problem with a cute solution.


Show that the arc length of the parabola y=x2, from (0,0) to (1,1) is not greater than 1.5.



Scroll down for a solution.




.


The arc length of f(x) is given by the integral 1+(f(x))2.

In our case, we are looking at

101+4x2

This can actually be evaluated without much trouble, and comes out to 14(5+sinh1(2))1.47

That is one way of trying to prove the 1.5 upper bound but we will go for the "cute" proof with very little computations here.

Write 

1+4x2=(2x+1)24x=2x+1+2x2x+12x

Let f(x)=2x+1+2x and g(x)=2x+12x

We apply the integral version of Cauchy-Schwartz inequality

fgf2g2

To get

101+4x210(2x+1+2x)10(2x+12x)

=1+1+431+143=209<32