News for hackers. Stuff that matters.
Re:IMO Grand Challenge by saagarjha on Saturday October 26, 2019 @08:35AM (#21363256)
IMO problems are generally proof-based and don't always lend themselves well to brute force solutions using analytic geometry.
Re:IMO Grand Challenge by OscarCunningham on Saturday October 26, 2019 @09:56AM (#21363679)
The kind of problems I'm thinking of are those like 2 and 6 on this year's IMO.

You have a bunch of points, lines and circles in some configuration and you have to prove that some condition holds. So you assign symbols to represent the coordinates of each of these points and you represent each fact you are told about them by some equation. The condition you are trying to prove is also represented by some equation. After multiplying up to get rid of square roots each of these equations is setting a polynomial equal to 0. So you are just trying to prove that some polynomial must be 0 if a bunch of other polynomials are 0, which can be done algorithmically via Gröbner bases.

Re:IMO Grand Challenge by woopwoop on Saturday October 26, 2019 @04:35PM (#21366018)
There is a Mathoverflow thread [0] about this. Discussion in the comments expresses skepticism because olympiad questions usually involve questions about choosing specific real roots of polynomials, not just arbitrary roots. The discussion there mostly suggests using some principles in real algebraic geometry, but these seem to be too slow and complicated to use in practice at this time.

[0] https://mathoverflow.net/questions/337558/automatically-solv...

Re:IMO Grand Challenge by OscarCunningham on Saturday October 26, 2019 @04:42PM (#21366048)
That question was asked by Kevin Buzzard, who is on the IMO Grand Challenge committee. So we are really going over old ground here.
Re:IMO Grand Challenge by woopwoop on Saturday October 26, 2019 @05:14PM (#21366245)
I'm a little perplexed by the dismissiveness of your response (perhaps I'm misreading?). I'm not saying IMO problems will never be algorithmically approachable, just saying expressing these problems in terms of Grobner bases may be harder than is suggested here. Buzzard also expresses skepticism about using Grobner bases for these sorts of problems in the comments.
Re:IMO Grand Challenge by OscarCunningham on Saturday October 26, 2019 @06:04PM (#21366534)
I wasn't trying to be dismissive, just saying that I didn't have much to add that wasn't already said there (and separately pointing out the connection between Buzzard and this thread).
Re:IMO Grand Challenge by pfortuny on Saturday October 26, 2019 @01:00PM (#21364795)
Yes: those problems will boil down to: do some functions (polynomials) belong to an ideal (maximal, usually)?

Grobner it and you are done.

Re:IMO Grand Challenge by throwaway-ai-ai on Saturday October 26, 2019 @08:49AM (#21363321)
Many IMO geometry problems involves proving things like:

these three points are on one line

these three lines intersect at one point

these two lines are parallel

these four points are on a circle

these two angles are equal

etc ...

There are things that absolutely can be done via coordinates, if one can brute force large algebraic expressions.

Re:IMO Grand Challenge by lordnacho on Saturday October 26, 2019 @09:03AM (#21363396)
What do you mean "by coordinates"? If you are asked to show that three points are on a line, having an accurate diagram is not enough, is it? Isn't the task to use the constraints presented (these lines are parallel, this is a right angle, etc) in a step-based reasoning for whatever you're asked to prove?
Re:IMO Grand Challenge by owaty on Saturday October 26, 2019 @09:29AM (#21363533)
It is done using symbolic algebra, not just assigning specific coordinates if that's what you're asking.

Let's say you're given three parallel lines. You can put your x axis along the first line. Then its equation is y = 0. The other two lines necessarily have equations y = a and y = b for some reals a and b. Then you calculate the other quantities involved via a and b and other parameters you have to introduce. At the end you calculate the coordinates of your three points and verify, symbolically, that they lie on the same line.

Re:IMO Grand Challenge by lordnacho on Saturday October 26, 2019 @09:49AM (#21363649)
Yes, that's right. You end up with a system of equations and solve it. So what does "by coordinates" mean? Is the original commenter simply saying that the machine will always be able to solve that system? He's right if that is what he means. Originally it sounded like "the machine can read the diagram accurately".
Re:IMO Grand Challenge by OscarCunningham on Saturday October 26, 2019 @10:09AM (#21363750)
>Is the original commenter simply saying that the machine will always be able to solve that system?

Yes.

Re:IMO Grand Challenge by eru on Saturday October 26, 2019 @09:17AM (#21363463)
Well, you can do that reasoning algebraically as equations on the coordinates. So you translate the constraints into equations. See https://en.wikipedia.org/wiki/Analytic_geometry

If memory serves right, there's a certain subset of geometry that decidable in that way. Ie you can just run an algorithm.