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)