News for hackers. Stuff that matters.
Re:At the International Mathematical Olympiad, computers pre... by im3w1l on Monday September 21, 2020 @01:18PM (#24545974)
> IMO problems are simple, but only in the sense that they don’t require any advanced math — even calculus is considered beyond the scope of the competition.

I kind of disagree. IMO problems require a lot of studying and theory that an average person wont know.

Re:At the International Mathematical Olympiad, computers pre... by lacker on Monday September 21, 2020 @05:38PM (#24548769)
Yeah, they do often require a lot of math. It's just a restricted set of topics. The IMO doesn't do any calculus or anything beyond calculus like real analysis, topology, etc. It does have a lot of geometry problems that use geometry that typically isn't in the American curriculum, and it has topics like number theory that aren't really in a standard high school curriculum either. But the topics are restricted so that they are pretty close to understandable by someone who has just done well in a standard high school mathematics curriculum.

Here's an example. For the problem they include in the article:

Let n be an integer greater than or equal to 3. Prove that there is a set of n points in the plane such that the distance between any two points is irrational and each set of three points determines a non-degenerate triangle with rational area.

This is a whole lot easier if you're familiar with Pick's Theorem, which gives you a formula for the area of a polygon whose corners are integer lattice points. In particular, any three integer lattice points define a triangle with rational area. So all you have to do is find n points that aren't colinear with each other and have irrational distance, and you'll solve the problem.

Technically, you could do this without Pick's Theorem, because you'll be able to find an equivalent formula for the area of these triangles. But it's much easier if you do know Pick's Theorem, and that's the sort of thing that you typically don't pick up in standard high school math, but you would pick up if you were practicing a bunch of different Olympiad-type problems.

Re:At the International Mathematical Olympiad, computers pre... by logicallee on Monday September 21, 2020 @06:24PM (#24549105)
Ha, Pick's theorem. Such hopelessly advanced problems (I'll give an example shortly) are well beyond what a cluster of ten thousand GPU's can solve today if trained for a thousand days on the types of math you've mentioned and then given a hundred hours to compute the answer to an infinitely, staggeringly and mind-bendingly intricate problem such as this one:

"Starting at 2, how many times must you double the number for the result to exceed 10?".

(Or a similarly trivial one.) Yeah. Really. Try it. They don't understand language at all. Just try to interact with any of the assistant or computational knowledge engines.

Here's what wolfram alpha gives you for that query:

Query:

Starting at 2, how many times must you double the number for the result to exceed 10?

Computed response:

1 | adjective | (especially of eyes) bulging or protruding as with fear 2 | adjective | appropriate to the beginning or start of an event 3 | noun | a turn to be a starter (in a game at the beginning)

Re:At the International Mathematical Olympiad, computers pre... by deanmen on Monday September 21, 2020 @07:02PM (#24549331)
https://imo-grand-challenge.github.io/

For the challenge, they give the AI a formal representation of the problem in Lean. To remove ambiguity about the scoring rules, we propose the formal-to-formal (F2F) variant of the IMO: the AI receives a formal representation of the problem (in the Lean Theorem Prover), and is required to emit a formal (i.e. machine-checkable) proof. We are working on a proposal for encoding IMO problems in Lean and will seek broad consensus on the protocol.

Re:At the International Mathematical Olympiad, computers pre... by logicallee on Tuesday September 22, 2020 @08:13AM (#24553559)
thanks. that's really not the IMO though, is it? coming up with a formal representation is a large part of the challenge, isn't it?
Re:At the International Mathematical Olympiad, computers pre... by im3w1l on Tuesday September 22, 2020 @01:34PM (#24557445)
∀n∈Z: n>=3 => ∃S∈(R^2)^n: [~∃p1∈S ∃p2∈S ∃p3∈S ∃a∈R: p1!=p2 & p2 != p3 & p3 != p1 & p1 + a(p2-p1) = p3] & [~∃p1∈S ∃p2∈S ∃a∈Z ∃b∈Z: |p1-p2| = a/b] & [∀p1∈S ∀p2∈S ∀p3∈S ∃a∈Z ∃b∈Z p1!=p2 & p2 != p3 & p3 != p1 => Area(p1, p2, p3) = a / b]

So far it's pretty much mechanical∗. The big question is how you will formalize Area(p1, p2, p3). Heron's could possibly make the problem much harder than cross product.

∗Although I may have made some or many mistakes.

Re:At the International Mathematical Olympiad, computers pre... by saagarjha on Monday September 21, 2020 @04:10PM (#24547875)
IMO problems are designed such that an average (ok, maybe slightly-above average) person can follow the solution, but it takes skill to come up with it in the first place. Just like calculus is standard curriculum for hundreds of thousands of high school students around the world, but we still think Isaac Newton and Gottfried Leibniz were genii for coming up with it.
Re:At the International Mathematical Olympiad, computers pre... by gowld on Monday September 21, 2020 @02:33PM (#24546829)
They are elementary. They don't require advanced theory, but they require an extremely large breadth of mathematical knowledge or creative.
Re:At the International Mathematical Olympiad, computers pre... by SketchySeaBeast on Monday September 21, 2020 @04:15PM (#24547933)
"and each set of three points determines a non-degenerate triangle with rational area" <- that's not language I knew in elementary school. Just being able to read what the question wants is a skill that isn't available to most elementary students.
Re:At the International Mathematical Olympiad, computers pre... by saagarjha on Monday September 21, 2020 @04:18PM (#24547977)
"Elementary" in the sense of "introductory", not in the sense of "taught in elementary school".
Re:At the International Mathematical Olympiad, computers pre... by SketchySeaBeast on Monday September 21, 2020 @04:31PM (#24548108)
I understand that, but elementary quantum physics is still grossly past the level of the students and required more advanced theory just to get to that elementary level understanding of the subject.
Re:At the International Mathematical Olympiad, computers pre... by saagarjha on Monday September 21, 2020 @04:34PM (#24548145)
Right, but this is elementary mathematics that is specifically chosen so that university-level mathematics is not required. (And rarely helps.)
Re:At the International Mathematical Olympiad, computers pre... by mciancia on Monday September 21, 2020 @05:22PM (#24548628)
Well, maybe not elementary school, but in highschool you should encounter those, especially second part. Non-degenerate in that case is fancy word for saying that those point cannot form a line (or a single point) - just that triangle is actually a triangle. This is pretty common term when it comes to math Olympiad so in would be extremely unlikely that someone can get to imo without encountering that in the past during training
Re:At the International Mathematical Olympiad, computers pre... by blueicecubes on Monday September 21, 2020 @05:14PM (#24548560)
"'Elementary' means that very little is required to know ahead of time in order to understand it, except to have an infinite amount of intelligence."
Re:At the International Mathematical Olympiad, computers pre... by dmurray on Monday September 21, 2020 @02:43PM (#24546920)
In practice, yeah, "an average person" wouldn't know where to begin. And a brilliant high schooler who hasn't studied maths beyond the high-school curriculum won't ace the test. Though he could get a medal, particularly if the geometry and combinatorics questions are friendly.

But the conceit of the IMO has always been that the problems are drawn from a very limited selection of fields, which are/were commonly taught in high schools around the world. No need for complex numbers, calculus, abstract algebra, or trigonometry (though any of these may end up used in an alternative solution).

Re:At the International Mathematical Olympiad, computers pre... by im3w1l on Monday September 21, 2020 @02:54PM (#24547035)
Can't say I've seen inequality-problems like IMO has anywhere else.
Re:At the International Mathematical Olympiad, computers pre... by singhrac on Monday September 21, 2020 @03:57PM (#24547748)
They show up in a few other areas, like probabilistic analysis of algorithms or sketching (e.g. Chernoff bounds and definitely the Cauchy-Schwartz ineq.). But you're right, nothing heavyweight like Muirheads has many applications.
Re:At the International Mathematical Olympiad, computers pre... by dmurray on Monday September 21, 2020 @08:05PM (#24549672)
But a surprising number of them can be solved with the insight only that x^2 >= 0. (Both Cauchy-Schwartz and AM/GM reduce to that if you squint hard enough). And that's accessible to any maths student.