Skip to content

Latest commit

 

History

History
61 lines (32 loc) · 3.91 KB

README.md

File metadata and controls

61 lines (32 loc) · 3.91 KB
Raw

Automated Generation of Planar Geometry Olympiad Problems (Patrik Bak)

This software can generate geometry problems of various difficulties suitable for mathematical contests including the IMO. See the list of already proposed problems.

It was developed as my master thesis.

An example of a non-trivial generated problem whose wording, and figure were entirely generated by the software:

Alt text

Generated problems

Here is a list of problems that have been created with the aid of the software. Many of them have been generated during the "big experiment" described in the thesis, page 56.

  1. IMO 2022, P4 (statement) -- the story how the software helped to generate it is in the solution thread

  2. ISL 2020, G6 (statement) -- generated in the big experiment and stated without modification

  3. ISL 2020, G3 (statement) -- generated in the big experiment in a version where D was the reflection of B in the midpoint of AC, then generalized after solving

  4. IGO 2020, A2 (statement) -- generated in the big experiment and stated without modification

  5. MEMO 2021, I3 (statement) -- generated in the big experiment in a version where D was the projection of A onto BC, then generalized after solving

  6. CPS 2021, P2 (statement) -- generated in the big experiment and stated without modification

  7. CPS 2020, P1 (statement) -- generated in the big experiment and slightly restated

(The list is not exhaustive, it does not include many easier problems used in Czech-Slovak local competitions)

See also the examples from Appendix of the thesis.

How it works in a few words

There are two major steps:

1. Generation of geometry problems

The main idea is to start with a geometry configuration (such as a triangle) and keep adding new objects (lines, points, circles) into it.

The algorithm sounds simple, but deep down, the algorithm turns out to be fairly complex. The combinatorial explosion is massive and one needs to do a lot of tricks to mitigate it.

The theorems are then verified probabilistically using analytic geometry. In practice, if a geometry theorem holds in 5 random figures, it must holds all the time.

2. Filtering unsuitable problems

This is done by utilizing geometry theorem proving methods. The main idea of this part is this: If we can prove a theorem, it is not hard enough, as we aim for the hardest problems.

Therefore, the prover is built to prove as many theorems as quickly as possible, unlike the standard problem in theorem proving, which is to prove as many theorems as possible without caring too much about how long it takes.

There also is a heuristic ranking system. The 4 rated aspects are selected based on the author's years of experience in writing geometry problems.

Technical readme

For technical notes regarding the code, installation, and running, see this.

Contact

If you are interested in my project, or if you have any other question, contact me via email.