Hi!

Recently I've met next problem: set of n lines is given, and they are in general position: no two lines are parallel, no three of them intersect at one point. This set of lines cuts plane into regions, some of which have finite area. Lest calculate an amount of triangles. Let f(n) be a minimal possible number of triangel, and g(n) — is a maximal number of triangles, which can occur.

It is true that f(n) = n - 2 for n ≥ 3. It's been unproven for hundred years, while somebady manage to use tricky matrix method (see article "Triangles and disasters").

Unfortunetely I can't find any inequalities for g(n) in the Internet. One can obtain trivial inequality using Euler formula: let's rewrite a picture as planar graph — where are vertices are line intersections, and edges are segments between vertices(which aren't intersect with some other segments inside). Let amount of vertices be V, amount of edges be E, and amount of faces (parts with finite area) be F. On given picture V = 10, E = 15, F = 6. Actually it's easy to get that g(5) = 5.

As it's known from Euler formula, V - E + F = 1(we don't count a face which is placed "outside"). It can be calculated easily that V and E equal and n(n - 2), respectively, that's why amount of parts with finite area is equal to — In fact, that gives a trivial inequality on g(n) as something of order .

So, we have a trouble — is this estimation good? Does an example with cn² triangles exist, or maybe there some better estimation? To show, how this problem is untrivial, I'll show you an example which proves, that g(9) ≥ 14:

So, a challenge for society: I can prove (with example) that g(n) > c * nlog(n), where c is some predeterminated constant. Can somebody build an example with same amount of triangles? With better amount?:)

update: Examples which prove that was found by Endagorion and Ripatti, so, the topic is closed:) Example: let's draw a table with n rows and n columns, which almost parallel to each other. Than it's easy to draw 2n - 1 line, which are almost parallel to diagonal of this square, so that i'th line cuts i'th diagonal, so the amount of triangles is quadratic.

Hello, CodeForces! On 20 August at 19:30 MSK will take place 262 (Div. 2) round. Div1 — participants can take part out of competition, as usual.

The problems were prepared by Victor Vasilevsky(vitux) and Aliaksei Semchankau (me). We'd like to thank Gerald Agapov (Gerald) for help of preparation of this round, Michael Mirzayanov (MikeMirzayanov) for comfortable platformes Codeforces and Polygon, and Mary Belova (Delinur) for translation of statements.

In this round you will help to different good people. We sure that every participant will find an interesting problem for him:)

gl & hf!

UPD: It will be used a standard scoring.

UPD2: Also we'd like to thank Vitaly Aksenov(Aksenov239) who helped a lot in fixing of Russian statements.

UPD3: We'd like to congrat top-5 participants!:

1) buptcjj

2) 6wr1

3) ladpro98

4) shaojj

5) linjek

Also we'd like to congrat jellygendut, who got 20th place and solved problem Е — It has been solved by 3 participants. Nobody has solved all problems, but every problems were solved by participants succesfully.