Wolfram Cloud Document

The difficulty of the selection problems in recent elite STEM programs are leveled up greatly. A list of problems chosen from the following programs and to give the audience a taste of how to use Wolfram Language to understand the problems and explore other possibilities: AIME, PROMYS, SUMAC and many other resources. Also as my previous talks, the selected problems fall in the categories: number theory, combinatorics/discrete calculus, and algebra/analysis.

The following problems are discussed in Wolfram Live R&D session on May 24 2023/Wednesday.

1. AIME Problem (2023)/Diametric seating

Five men and nine women sit equally spaced around a circle in random order. The probability that every man sits diametrically opposite a woman is

where

and

are relatively prime positive integers. Find

m+n

Please refer to this AOPS link for exact numerical result.

Random constrained permutations

◼

Visualize the arrangement as regular polygon vertices on unit circle:

In[]:=

(*mustbeevennumberbecausenotwopointsarediametricinregularpentagonforinstance*)n=14;allMembers=Range@n;indices=AssociationThread[allMembers->N[CirclePoints[n]]];

◼

Make 14 people into 7 diametric groups:

In[]:=

pairs=Array[{#,#+n/2}&,n/2]

◼

Assign men to five of seven brackets above and randomly choose one of the binary seating position for each bracket:

In[]:=

manPos=RandomChoice/@RandomSample[pairs,5];womanPos=Complement[allMembers,manPos];

◼

Add a dashed diameter to indicate which pair of man and woman sitting opposite diametrically after assignment:

In[]:=

diametricLink=Line[{indices[#],indices[Mod[#+n/2,n,1]]}]&/@manPos;

◼

Label the people and color-code gender to clear visualize the result that satisfies given constraint:

In[]:=

Graphics[{{Dashed,diametricLink},{Red,Disk[indices[#],.1]&/@manPos},{Blue,Disk[indices[#],.1]&/@womanPos},Table[Style[Text[k,indices[k]],White,Italic,12],{k,n}]}]//Framed

◼

Lets run it 16 times to see some random variations and quickly test our function:

In[]:=

SeedRandom[1234];Table[manPos=RandomChoice/@RandomSample[pairs,5];womanPos=Complement[allMembers,manPos];diametricLink=Line[{indices[#],indices[Mod[#+n/2,n,1]]}]&/@manPos;Graphics[{{Dashed,diametricLink},{Red,Disk[indices[#],.1]&/@manPos},{Blue,Disk[indices[#],.1]&/@womanPos},Table[Style[Text[k,indices[k]],White,Italic,10],{k,n}]}],16]//GraphicsGrid[Partition[#,4,4]]&

They all satisfy the diametric seating requirement from the problem. Notice that the algorithm does not waste any computation to test non-valid set-up, it is the most efficient way to create such random permutation.

Asymptotic probability with the diametrically seating requirement

Assume we have

people and

λn

men, where λ is between 0 and 1. The domain of λ is to make sure the number of man be strictly less than half of the group. Lets find the probability that every man sits diametrically opposite a woman again as

approaches infinity.

In[]:=

Asymptotic

Binomialn.,n.λ*2^n.λ

Binomial2*n.,n.λ

,n.->Infinity,Assumptions->0<λ<1

Out[]=

+n.λ

n.(-2Log[2]-Log[1-λ]+λLog[1-λ]+2Log[2-λ]-λLog[2-λ])



-((-2+λ)λ)

-((-1+λ)λ)

(-1+λ)λ

In[]:=

FullSimplify[%]

Out[]=

-n.

(4-4λ)

+n.λ

(2-2λ)

-n.(-2+λ)

(2-λ)

Lets replace

with 100 and see if the asymptotic expression agrees with our direct computation:

In[]:=

LogPlotEvaluate

-n.

(4-4λ)

+n.λ

(2-2λ)

-n.(-2+λ)

(2-λ)

/.n.->100,{λ,0.05,0.95},





Out[]=

Use direct computation:

In[]:=

DiscretePlot

Binomial[100,k*100]*2^(k*100)

Binomial[2*100,k*100]

,{k,0.05,0.95,0.02},



Out[]=

The two graphs show the identical trend as the proportion of man approaches half given that there are 200 people in total.

Special cases

◼

Half members of the group are male:

In[]:=

DiscreteAsymptotic

Binomial[n.,n.]*2^n.

Binomial[2*n.,n.]

,n.->Infinity

The contribution of

is negligible here and the probability of

In[]:=

LogPlot

-n.

,n.,10,50

Lets test again on 300 people with 150 males and 150 females:

In[]:=

exact=

Binomial[n.,n.]*2^n.

Binomial[2*n.,n.]

/.n.->150

In[]:=

asymp=

-n.

/.n.->150

Relative error is around 8 of 10000th

In[]:=

exact-asymp

exact

//N

◼

Quarter of the group are male:

In[]:=

DiscreteAsymptotic

Binomial[2n.,n.]*2^(n.)

Binomial[4*n.,n.]

,n.->Infinity

Out[]=

+n.

-3n.(2Log[2]-Log[3])



Test if the expression decays to zero:

50% chance for diametric seating: 200 vs 1000 people

◼

16 men/200 people: 8%

◼

37 men/1000 people: 3.7%

2. Repeating Integer (PROMYS 2023/Bangladesh MO 2001)

◼

Utility function (fast perfect square test from MSE)

◼

Here a quick test on the given number:

◼

Test all two digits candidates

◼

Test all 4 digits candidates

◼

Test all 6 digits candidates

Same argument as previous case

You might conclude there exist none. But obviously, by repeating

404958677685950413223140495867768595041322314049586776859504132231404958677685950413223140495867768595041322314049586776859504132231404958677685950413223140495867768595041322314049586776859504132231404958677685950413223140495867768595041322314049586776859504132231404958677685950413223140495867768595041322314049586776859504132231404958677685950413223140495867769,

the following number is a perfect square:

Key to the solution

Only 5 and 7 work because the result must have 11 digits:

Verification:

For instance lets look at 39. The factor 13 has order 2:

The prime numbers 5,7 and 11 work. They produce 39 digits:

The following number of repeating 715976....899409 is a perfect square

Remark-1

◼

There are infinitely many such number because the p-adic property:

Remark-2

Early occurrence of “large” primes: like 909091. The are small in terms of multiplicative order of 10 (remainder -1 = 9 mod 10). Smaller this measure, the earlier and the more frequently the prime shows up likely in the factorization sequence.

On a strange railway line, there is just one infinitely long track, so overtaking is impossible. Any time a train catches up to the one in front of it, they link up to form a single train moving at the speed of the slower train. At first, there are three equally spaced trains, each moving at a different speed. You watch, and eventually (after all the linking that will happen has happened), you count the trains. You wonder what would have happened if the trains had started in a different order (but each of the original three trains had kept its same starting speed). On average (averaging over all possible orderings), how many trains will there be after a long time has elapsed? What if at the start there are 4 trains (all moving at different speeds)? Or 5? Or n?

Analysis

To enumerate the possible number sections, it is best to think about two things

what are the sub-problems?

what is the invariant among the sub-problems?

Lets first think about the the slowest train with speed 1 and assume all train travels from left to right. Everything that are on the left hand side will eventually collide into one chain.

What about 2? well, it depends on whether its is used in the first chain or not. If we think about inductively about 3, 4,5,6 ... , it would be a nightmare to enumerate all possibilities.

The key takeaway

The key point here is NOT about the number but the position of the number so that it is possible or not to be the smallest number in the subsequence to right hand side of “1”. And replace “1” with the smallest number after discarding the slower chain of train.