Wolfram Mathematical Olympiad problems database
By Miroslav Marinov
Wolfram Summer School 2022
m.marinov1617@gmail.com
By Miroslav Marinov
Wolfram Summer School 2022
m.marinov1617@gmail.com
We build a database of problems from mathematical olympiads which are interesting not only when attempted by hand, but also when the Wolfram language is used as an assistant. These should be of interest not only to those who wish to train in certain areas of mathematics, but also to people interested in how the language performs against such problems. In this manner strengths or weaknesses of particular functions of the language could be exposed and one could have a thought of how to make a more automated approach to obtain a nice solution which really relies on the language, but also hopefully gives insight on how would a human find it on their own. Included also are problems for which we do not know how to utilize the language to help, even though it seems likely to be possible. We also intend to build an application which generates training problem sets based on keywords input by the user.
Introduction
Introduction
What does the database contain?
What does the database contain?
Currently there are a few written problems, with variety in area, difficulty and school group. A definitive goal would be to have at least 100 problems before the database becomes official. Each problem has a precise source, which is always either the LinkedIn Mathematical Olympiads group or a recognized competition or book.
Keywords for the problems
Keywords for the problems
Each problem shall be in a separate cell which is to be tagged with keywords.
In terms of area of mathematics we mainly follow the Wolfram MathWorld classification. The types of problems we cover are with the following keys:
◼
Algebra, Number Theory, Inequalities, Functional Equations, Sequences, Diophantine Equations, Divisibility, Polynomial Equations, Integer Polynomials, Floor function, Probability
Part of future work could be to incorporate additional keywords which represent very particular techniques used in the problem: Modular Arithmetic, Bounds, Factoring, AM-GM, Prime Numbers, Cauchy-Schwarz, Substitutions, Summation, Induction, Symmetric functions. In the user application these words should be searchable but not visible in the cell tag - so for example if the user types Inequalities, they may not like to have a spoiler of the technique used in the problem they receive. Note that such an option would certainly not be available if the user searches for particular problems via the "Cell" menu in Mathematica, as "CellTags" does not have specific options for hiding tags, to my knowledge.
In terms of Difficulty, we think of the following classification:
◼
Easy - Reasonable (but not trivial) to write down in the Wolfram Language, not easy to solve by hand, but there should be a way to motivate the idea.
◼
Medium - Harder to do with the Wolfram Language and by hand, but there is a way of doing it.
◼
Hard - We do not really know how to utilize the language to get a nice proof, even though it seems likely to be possible somehow. Nevertheless, the problem itself is of good quality.
In terms of school group we intend to work with the following:
◼
Junior, Senior, Undergraduate
The main areas in Olympiad Mathematics nowadays are Algebra, Euclidean Geometry, Number Theory, Combinatorics. This project seems to address Algebra and Number Theory in a promising manner. In Combinatorics the problems are very wordy and in fact quite often even a human cannot write down a 100% rigorous proof - but at least problems in the Probability branch could be nicely tackled. Finally, one may notice that we do not address Euclidean Geometry at all - the reason for this is that there already exist very serious results in this area, see Patrik Bak's work at Automated Generation of Planar Geometry Olympiad Problems.
On the Application Interface
On the Application Interface
Currently this has not been discussed a lot, partly because both the author and Paul feel that this should not be a central part of this project when it is in its Proof of Concept stage. We went for a bit into previous work of one of the mentors, Daniel Robinson, to see how problem sets could be generated in a user-friendly way based on some CBM code. Unfortunately, this was not helpful enough for the situation here. A future step would be to talk in depth with specialists with problem generation, CellTags and TaggingRules, e.g. John Fultz, Lou D’Andria, and Larry Adelston.
In the very worst case, a user could at least use the Find Cell Tag command in Mathematica (though not in the Wolfram Cloud) in order to scroll easily through the notebook and find whatever is of interest.
In the very worst case, a user could at least use the Find Cell Tag command in Mathematica (though not in the Wolfram Cloud) in order to scroll easily through the notebook and find whatever is of interest.
Problems
Problems
Consider the sequence a0=a1=1,an+1=14an-an-1. Prove that for all non-negative integers n the integer 2an-1 is a perfect square.
Consider the sequence ==1,=14-. Prove that for all non-negative integers the integer is a perfect square.
a
0
a
1
a
n+1
a
n
a
n-1
n
2-1
a
n
Source: Bulgaria Festival of Young Mathematicians 2014
Tags: Sequences, Easy, Senior
Tags: Sequences, Easy, Senior
In[]:=
2*RecurrenceTable[{a[n+1]==14*a[n]-a[n-1],a[0]==1,a[1]==1},a,{n,0,8}]-1
Out[]=
{1,1,25,361,5041,70225,978121,13623481,189750625}
In[]:=
Sqrt[%]
Out[]=
{1,1,5,19,71,265,989,3691,13775}
So these are the first few terms of the square root. Now one may guess that this sequence should also have a linear recurrence and in fact the Wolfram Language could assist with finding it.
For example, for the Fibonacci sequence in which each terms is the sum of the two previous ones (corresponding to coefficients 1 and 1) we indeed have
For example, for the Fibonacci sequence in which each terms is the sum of the two previous ones (corresponding to coefficients 1 and 1) we indeed have
In[]:=
FindLinearRecurrence[{1,1,2,3,5,8,13,21}]
Out[]=
{1,1}
(Open question: Can you find a method which does not need the suspicion for a linear recurrence? I personally tried FindSequenceFunction but it did not work equally well.)
Notice how we omitted the first term 1! In fact, if you try with {1, 1, 5, 19, 71, 265} you will not get a result. The insight behind this is that the correct first term is actually (-1)!
So let's suppose we have not noticed that - we can again solve the problem. The most straightforward way would be by comparing the explicit forms.
So let's suppose we have not noticed that - we can again solve the problem. The most straightforward way would be by comparing the explicit forms.
In[]:=
B[n_]:=RSolveValue[{b[n+1]==4b[n]-b[n-1],b[1]==1,b[2]==5},b[n],n]B[n]
Out[]=
-
(1++-
3
)2n
(2-
3
)3
n
(2-
3
)n
(2+
3
)2(2+
3
)In[]:=
A[n_]:=RSolveValue[{a[n+1]==14a[n]-a[n-1],a[1]==1,a[2]==13},a[n],n]A[n]
Out[]=
(2++4+
3
)7n
(7-4
3
)3
n
(7-4
3
)n
(7+4
3
)4(7+4
3
)In[]:=
FullSimplify[B[n]^2-2*A[n]+1==0,n>0&&Element[n,Integers]]
Out[]=
True
(Minor remark: if we omit the == 0 in "FullSimplify" then for some reason it will not simplify the expression completely and hence will not output 0.)
Solve x3-y7=2 in non-negative integers.
Solve -=2 in non-negative integers.
x
3
y
7
Source: Germany VAIMO 2010
Tags: Diophantine Equations, Medium, Junior
Tags: Diophantine Equations, Medium, Junior
In[]:=
Solve[3^x-7^y==2&&x≥0&&y≥0,{x,y},Integers]
Out[]=
Solve[-2&&x≥0&&y≥0,{x,y},]
x
3
y
7
So it seems the solve function cannot handle this one. What is more surprising is that it cannot even handle a simple example like the following one.
(However, one can separately check that a Wolfram Alpha query would work perfectly on it.)
(However, one can separately check that a Wolfram Alpha query would work perfectly on it.)
In[]:=
Solve[3^x==13,x,Modulus19]
Out[]=
Solve[13,x,Modulus19]
x
3
If you look at Modulus examples of Solve online you will see that the illustrations are with polynomial equations rather than exponential - and as we see here, for some reason exponentials are harder to work with. Another difficulty here is that our main equation actually has solutions (check some small values of the variables to see this).
So let's consider this approach (we invite the reader to think about how to automatize it even more - both in terms of ideas and implementation). We iterate y from 0 to 100, say, and see what solutions we can find - in this case x = 1, y = 0 and x = 2, y = 1. Then for the range of y for which we have not found a solution, we can do a loop to see whether we can find a modulo which gives a proof that the equation has no solution. We shall use MemberQ - here is a toy example.
In[]:=
MemberQ[Table[Mod[2^i,7],{i,10}],1]
Out[]=
True
Catch[Do[If[MemberQ[ArrayReshape[Table[Mod[3^x-7^y-2,m],{x,1,EulerPhi[m]},{y,2,EulerPhi[m]+1}],{1,EulerPhi[m]^2}][[1]],0]==False,Throw[m]],{m,4,2590}]]
Out[]=
2107
So we found 2107 = 43 . 49 as our lucky number. Note however that the last execution was very slow and so one should really think on how to speed up such ideas. (For a start - perhaps replace the Throw-Catch approach with a nicer structure.)
Finally, let us ponder on why this lucky number makes sense to work. Firstly, it is divisible by 49 and indeed any power of 7 for which we did not find a solution is divisible by 49. Now one may check from modulo 49 that the exponent of 3 has to be 26 (mod 42). On the other hand, 3^(42) = 1 (mod 43) by Fermat's little theorem, so unless the very concrete 3^(26) = 2 (mod 43) holds, we get a contradiction. Well, it is false (the left-hand side is congruent to 1), so we are done!
Solve n-1a+n-1b+n-1c=n! in positive integers.
Solve ++=n! in positive integers.
n-1
a
n-1
b
n-1
c
Source: IMO 2021 Shortlist, Problem N5
Having in mind what the solution to this problem is, it seems very hard to be implemented, though I would not count it out. In the meantime, one could develop techniques such as "compare powers of primes in factorials or with the Lifting the Exponent lemma whenever possible". Here are the key steps for a full solution.
1) By comparing a^{n-1} with n!, justify that a ≤ (n-2)/2 (and the same for b and c).
2) If n is odd, by mod 4 we have that a, b, c are even, but then comparing powers of 2 in both sides we get a contradiction. (For the factorial one could use Legendre's formula.)
3) If n is even and all of a+b, b+c, c+a are powers of 2, obtain that the two smallest among a,b,c are equal to 2 and get a contradiction with moduli 5 and 8.
4) If n is even and e.g. a+b has an odd prime divisor p, justify as in 3) that p does not divide a and b, then apply Lifting the Exponent Lemma to a^{n-1} + b^{n-1} and by comparing with the power in n! - c^{n-1} (equals that of n!) see that a + b and n - 1 must be the only multiples of p less than n. But a + b < n - 1 by 1), so n - 1 = 2p which is impossible since n is even.
Solve 4x+7y=1031 in integers.
Solve += in integers.
4
x
7
y
10
31
Source: Bulgaria 2011, Team Selection Test for Balkan Mathematical Olympiad
In[]:=
Solve[x^4+y^7==31^{10},{x,y},Integers]
Out[]=
y
So it seems that Solve cannot handle this equation. One may do a check on values of y up to +-100 and will get no solution, so wild guess - the equation has no solution at all. What we will do here is try to find a modulo for which this equation has no solution. As a toy example to have in mind, note that if a modular congruence has no solution we should get an empty object (of length 0).
In[]:=
Length[Solve[x^3==4,x,Modulus9]]
Out[]=
0
In our case
In[]:=
Catch[Do[If[Length[Solve[x^4+y^7==31^{10},{x,y},Modulusm]]==0,Throw[m]],{m,2,60}]]
Out[]=
29
So this was easy with the language, but why did it work? It is not too much of a coincidence - by Fermat's little theorem we have z^{p-1} = 1 for any prime p not dividing z and so for z^{(p-1)/k} there are at most k+1 possible values modulo p (including zeroes). If k is small then there are not many possibilities so it's reasonable to be the case that the equation is not satisfied. (In our case, p = 29 and k = 4 and k = 7, with x^4 and y^7 attaining 5 and 8 values, respectively.)
Find all positive integers m such that every term of the sequence a1=a2=1,a3=4,an=m(an-1+an-2)-an-3 is a perfect square.
Find all positive integers such that every term of the sequence ==1,=4,=m(+)- is a perfect square.
m
a
1
a
2
a
3
a
n
a
n-1
a
n-2
a
n-3
For a,b,c,d>0 determine the minimum possible value of (a+b)(b+c)(c+d)(a+b+c+d)abcd
For determine the minimum possible value of
a,b,c,d>0
(a+b)(b+c)(c+d)(a+b+c+d)
abcd
For a,b,c>0 prove the inequality 2(b+c)2a+bc+2(a+c)ac+2b+2(a+b)ab+2c≥6
For prove the inequality +bc++≥6
a,b,c>0
2
(b+c)
2
a
2
(a+c)
ac+
2
b
2
(a+b)
ab+
2
c
For a,b,c>0 with a+b+c=1, show that a+bc+12a+1+b+ac+12b+1+c+ab+12c+1≤3910.
For with , show that +1++1++1≤.
a,b,c>0
a+b+c=1
a+bc+1
2
a
b+ac+1
2
b
c+ab+1
2
c
39
10
Given x1=12 and xn=2+xn-11-2xn-1 prove that and that the terms are well defined, non-zero and distinct.
Given = and = prove that and that the terms are well defined, non-zero and distinct.
x
1
1
2
x
n
2+
x
n-1
1-2
x
n-1
Find all functions f: such that 2f(a)+2f(b)+2f(c)=2(f(a)f(b)+f(b)f(c)+f(c)f(a)) for all integers a,b,c such that a+b+c=0.
Find all functions such that ++=2(f(a)f(b)+f(b)f(c)+f(c)f(a)) for all integers such that .
f:
2
f(a)
2
f(b)
2
f(c)
a,b,c
a+b+c=0
The function f: is strictly increasing and satisfies f(f(n))=2n+2. What is f(2022)?
The function is strictly increasing and satisfies . What is f(2022)?
f:
f(f(n))=2n+2
If f: is such that f(x)+f11-x=arctan(x), compute 0∫1f(x)dx.
If is such that , compute f(x)dx.
f:
f(x)+f=arctan(x)
1
1-x
0
∫
1
Choose a random k-element subset X of {1,2,...,k+a} uniformly and, independently of X, choose random n-element subset Y of {1,2,...,k+a+n} uniformly.Prove that the probability (min(Y)>max(X)) does not depend on a.
Choose a random -element subset of uniformly and, independently of , choose random -element subset of uniformly.Prove that the probability does not depend on .
k
X
{1,2,...,k+a}
X
n
Y
{1,2,...,k+a+n}
(min(Y)>max(X))
a
Random Polynomials
Random Polynomials
Keywords
Keywords
◼
Language Testing
◼
Mathematical Olympiads
◼
CellTags
◼
TaggingRules
Acknowledgments
Acknowledgments
I would like to thank my project mentors Daniel Robinson and Paul Abbott for suggestion of the topic, as well as for helpful comments and discussions on technical details. I also express my gratitude to Stephen Wolfram and the whole Wolfram community for the possibility to be in Wolfram Summer School 2022.
References
References
◼