Problem 713

Comments

I never took a course in graph theory (outside of some simple things in algebra class, but nothing formal) so a lot of the articles I read online were over my head. I want to try to expand my math horizons as much as I can, so I did my best to learn something new here.

I started by draw dots on a piece of paper and trying to figure out how many tries it should take me to find the fuses I am looking for. I wasn’t sure if I was doing it optimally because some of the numbers seemed a bit large, but I eventually came up with this table for n and m:

n\m 2   3   4   5
2:  1
3:  3   1
4:  6   2   1
5:  10  4   2   1

I also looked up “turan fuse problem” on Google and came to the concept of the Turan Graph (https://mathworld.wolfram.com/TuranGraph.html). This seemed a lot like what I was after, the name obviously being a clue! The problem was I couldn’t figure out how to match the graphs they show in the article to the ones I was drawing myself. Instead I turned to OEIS and found https://oeis.org/A134546 which matches my table precisely. I used the generating function they gave and was able to get to the answer.

After reading the thread when you complete the problem, I learned more about how to match my graphs to the ones that Turan made. I was essentially looking for the “inverse” (for lack of a better word) of his graphs. Assuming the maximal graph (the one where all vertices connect to all others) and remove from it the edges shown in Turan’s graph. This number of edges is the answer I was looking for. Exactly how the math works out I am still trying to understand and will probably spend a bit of time this evening trying to get to the bottom of it.

Completion of this problem also got me to Level 7!! I’ve now completed 175 problems 🎉🥳🎊

Code

def T(n, k):
    n -= 1
    k -= 1
    return k * (n // k) * ((n + k) // k) // 2 - (n // k) * (k - 1 - (n % k))

def solve(n):
    total = 0
    for k in range(2, n + 1):
        total += T(n, k)
    return total

if __name__ == '__main__':
    import sys
    n = eval(sys.argv[1])
    print(solve(n))

Tests

import pytest
from problem import solve, T

_test_T = (
        (3, 2, 3),
        (8, 4, 7),
)

@pytest.mark.parametrize('n,m,expect', _test_T)
def test_T(n, m, expect):
    assert expect == T(n, m)

_test_solve = (
        (10**3, 3281346),
)

@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
    assert expect == solve(n)