Back in 2019 some AI researchers and mathematicians came up with an ambitious
challenge, to create an AI that could win a gold medal at the International Mathematics
Olympiad. It was an ambitious challenge because winning a gold medal at this event puts you on
the world stage as having one of the best mathematical minds. Previous winners of the
gold medal include Terence Tao and Maryan Mirzakhani. The researchers called it the
IMO Grand Challenge and for an AI system to pass they proposed the following rules.
Each proof that the AI producers must be checkable in 10 minutes which is
approximately the amount of time it takes a human judge to judge a human solution.
The AI only has as much time as a human competitor which is four
and a half hours for each set of three problems and the AI must be open source
released publicly and reproducible. The AI cannot query the internet.
As of recording this we have met chat GPT and GPT-4 was released a couple of months ago. I'm
sure that we'll be continually amazed by what it's able to do but no AI including ChatGPT has yet won
or even competed in the IMO competition. Bets are on literally for if and when one might succeed.
GPT-4 is paraded around as having already aced many other exams including the SAT and the biology
Olympiad but it might never ace the IMO because the thing is that ChatGPT is actually not very
good at math. It's not good at counting or keeping track of multiple operations because after all it
is a language model that excels at predicting the next word in a sentence. Math questions on
the SAT can be quite predictable and formulaic and likely enough similar problems were included
in the training data set that it was able to get by but the IMO problems are different and
they're designed to test true understanding and creative problem solving. I'd like to understand
the likelihood of an AI passing this challenge soon but in order to do that I would first need to
understand the solution to an IMO problem myself on human terms then I would like to understand how
ChatGPT goes about solving it and then see if there are any better AI competitors out there.
Here's an IMO problem. This is the Olympics for math so these problems are some of the hardest
out there and can require creative solutions. This is problem six from the 2022 competition:
Let n be a positive integer. A Nordic square is an n times n board containing all the integers from 1
to n squared so that each cell contains exactly one number. Two different cells are considered
adjacent if they share a common side. Every cell that is adjacent only to cells containing larger
numbers is called a valley. An uphill path is a sequence of one or more cells such that the
first cell in the sequence is a valley. Each subsequent cell in the sequence is adjacent to
the previous cell and the numbers written in the cells in the sequence are an increasing order.
Find as a function of n the smallest possible number of uphill paths in a Nordic Square.
This is an example of a Nordic Square where n is equal to two. Here one is our valley and we
could have six possible uphill paths; one to two, then one to two to four which is counted
as a different uphill path, you could do one to three or one to three to four and we also have to
include the path of length one which is just the valley. We could have placed these numbers in the
squares in any the order it didn't have to be in this pattern it could have gone one, two, three,
four, and in fact you should play around with it now trying Nordic squares of different sizes and
different arrangements of the numbers to see what kinds of patterns might give you this smallest
number of total uphill paths. If you want to try it for yourself now is your time to pause. I don't
think it's possible for a human to look at this and know the solution instantly you really do have
to play around and try a bunch of random things to see if any patterns pop out. Here's an example of
a three by three Nordic Square which looks like it might have the minimum paths for the size.
Again we only have one Valley and it is our one but we could also have one two, one two six, one
two seven, one three, one three eight, one three seven, one five, one five nine, one five six,
one four, one four eight, one four nine, giving a total of thirteen path. You can easily find other
three by three arrangements that have more paths than this and the crux of the solution comes down
from recognizing two things; one is that for the minimum number of paths you want there to be only
one valley, like we have here our number one. And you also need to recognize that for every pair of
adjacent numbers there needs to be only one path back to the valley. Say here two and six are
adjacent numbers and from them there was only one path back down to our valley which was like this.
This essentially means you can have two paths coming to a common endpoint but you
can never have this two paths converging and then continuing on because that would
mean that from wherever this ends these two adjacent numbers will have multiple
paths back down to the valley so this is not allowed and we can call something like this,
our end point, a sink. With this we've given ourselves the golden ticket,
if every two adjacent numbers only have one path back to the valley then the minimum number of
paths in our Nordic Square would be equal to the number of adjacent numbers. Counting the pairs
of adjacent numbers here we have one, two, in each row and there's three rows so that would be
two times three, that's six adjacent numbers that are adjacent horizontally. Plus
one, two, three, four, five, six, going vertically so there'd be 12 pairs of adjacent numbers.
That's our number of minimum paths but we have to remember to add one because our valley, our single
valley will also be its own single length path giving 13 as the total minimum paths in this case.
To extend that for any number of n we will always have n minus 1 adjacent numbers on each row times
n rows and n minus 1 adjacent numbers on each column times the number of columns so that's
2 n times n minus 1 paths plus one to account for our valley. That's basically the answer here and
that will give you some points but more points will come from new harder task of describing how
to arrange the numbers to get this minimum and that part of the solution comes from describing
a tree-like structure like this. If you put the numbers in increasing order in these trees you end
up with only one Valley and for every adjacent pair of numbers only one path back to it. The
black numbers here represent numbers higher than 153 so you fill in all these ones first
and then go back and fill in the black spaces with the higher ones. These black numbers are
sinks and there might be multiple ways to end at the sink but there'll never be a way out.
Let's give the problem to ChatGPT and see what it does. The 2022 problem I picked wouldn't be
in the GPT training data set. I'm using the latest model GPT-4 and it gives me the wrong answer. It
says that the smallest number of paths is equal to n. I asked it how many valleys there should be to
minimize the number of paths and it immediately gives a square with three valleys. It says that
the minimum is n valleys which gives n paths and if you remember recognizing that there must only
be one valley is key to getting the solution. I asked it to make a Nordic square with only one
valley which it did but then it failed to count more than one path and when I asked it to do it
for larger squares it gave constructions that for each adjacent pair there were multiple paths back
to the valley and it just couldn't count paths correctly even when I tried to point
out mistakes. I don't think it would be able to score any points on this question at the moment.
This recent paper from Microsoft analyzed the abilities of GPT-4 and said there were sparks
of artificial general intelligence which refers to AI that is broadly intelligent
at or above human level and not just good at one specific task. They mentioned that ChatGPT
is trained on a massive amount of webtext data and uses at its core a self-supervised
objective of predicting the next word in a partial sentence. The paper also shows that
GPT-4 does not have the capacity required to conduct mathematical research. It does manage
to solve one IMO question in here but in many other problems it lacks critical reasoning and
the ability to examine each step of its arguments. They say one reason for this
might be that in most of the math solutions it's read on the internet, most just give the
correct answer but don't capture the thinking process. It doesn't make guesses or backtrack
because it can't backtrack. When predicting the next word it just needs to move forward
in a straight line. In essence it's bad at math because it lacks the ability to play around.
So ChatGPT fails for now but it's not the only competitor. The people at OpenAI,
in fact some of the same people who came up with the IMO Grand Challenge in the first place, work
on a different AI system. One that according to this paper published in 2022 has already managed
to solve some IMO problems. It's not a language model but instead is a proof-solving model that
speaks the language of formal math. Automated proof solvers have existed for a little while
but this one is trained to iteratively search for new proofs. It takes mathematical ideas that need
to be proved and breaks them down into smaller and smaller statements that are easier to prove until
there's nothing left to prove. This is what the formal math language looks like, it's not too easy
for a human to read but it's probably our best bet when creating a system that is actually useful
to mathematicians. It uses something called the lean theorem prover. The proofs that it creates
are machine checkable, following a series of logical laws. They say that their model and search
procedure are capable of producing proofs that chain multiple non-trivial reasoning steps and it
does require some creativity to invent lines like this. Combining an AI that can speak formal math
and correctly prove statements with something like ChatGPT to make it more user-friendly could really
make some waves in math and much more likely to pass the IMO Grand Challenge than a language
model alone. And as I mentioned while ChatGPT is still struggling with IMO problems it has already
passed a bunch of exams. There's a note here back in the Microsoft paper saying that GPT-4 does not
rely on memorizing the exact problem statement but on applying a general solution method. While
it is possible that GPT-4 memorizes the solution template this is not necessarily a flaw as it is
also a common way of solving math problems for humans. They're saying that GPT-4 has been able
to pass a bunch of exams by doing what many of us do which is kind of memorizing the structure of
common problems. Looking through past papers and solutions can often give you enough of what you
need to do well in an exam because the structures are usually pretty much the same and if this is
what ChatGPT is so good at too then perhaps this is the space in which exams will change
a bit. Perhaps for now exams will have to change to be a little bit more like the IMO to reward
creative problem solving and necessitate having to stop and play around with the problem. That
seems like it is still a uniquely human trait but I'm not sure for how long that will be the case.
Thanks for watching this video and thanks to my Patreon supporters for
making it possible. A special shout out to today's Patron Cat of the Day, Cathulhu.
[Music]