Tricky lemma

Правка en1, от Fly_37, 2022-06-05 15:38:18

Hello!

Some time ago I created a problem for local programming competition. Unfortunately it turned out that I had incomplete proof of one lemma, that I can not show even to this day.

Lemma: Given an increasing array of $$$N$$$ arbitrary large numbers we define its cost as sum of lengths of all non-trivial, maximal arithmetic progressions starting at the first element. The cost of any array is $$$\mathcal{O}(N\log{N})$$$.

For example for array $$$[0, 2, 3, 4, 6, 8, 9]$$$ — the total cost is $$$|[0, 2, 4, 6, 8]| + |[0, 3, 6, 9]| + |[0, 4, 8]| + |[0, 6]| + |[0, 8]| + |[0, 9]| = 5 + 4 + 3 + 2 + 2 = 16$$$.

It is easy to see, that if we simply take $$$N$$$ consecutive natural numbers we get $$$\mathcal{O}(N\log{N})$$$ cost, but I was not able to prove that this is the worst case scenario.

Best complexity I can show is $$$\mathcal{o}(N^2)$$$, but still far from the goal...

Can anyone show if the lemma is true or false?

Теги proof, arithmetic sequence

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Fly_37 2022-06-05 17:24:51 5 Tiny change: '3 + 2 + 2 = 16$.\n\nIt i' -> '3 + 2 + 2 + 2= 18$.\n\nIt i'
en1 Английский Fly_37 2022-06-05 15:38:18 940 Initial revision (published)