Just opposite!

Let f ( n ) f(n) return the maximum possible sum (of values of edges) of an Euler path of a graph with n n vertices (numbered 1 to n n and each edge numbered with the sum of vertices it joins).

Then for how many n n does : f ( n ) 2013 ( m o d n ) ? f(n)\equiv2013\pmod n?

Inspiration


The answer is 12.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Mark Hennings
Jul 19, 2020

If n n is odd, then every vertex of the complete graph K n K_n has even valency, and hence an Eulerian cycle is possible. Clearly, using the complete graph will give the maximum edge sum. Thus every vertex contributes to the value of n 1 n-1 edges, and hence f ( n ) = ( n 1 ) i = 1 n i = 1 2 n ( n + 1 ) ( n 1 ) f(n) \; = \; (n-1)\sum_{i=1}^n i \; = \; \tfrac12n(n+1)(n-1) Thus f ( n ) 0 ( m o d n ) f(n) \equiv 0 \pmod{n} , so if f ( n ) 2013 ( m o d n ) f(n) \equiv 2013 \pmod{n} then 2013 0 ( m o d n ) 2013 \equiv 0 \pmod{n} , and hence n n divides 2013 2013 . Since 2013 = 3 × 11 × 61 2013 = 3 \times 11 \times 61 , there are 2 3 = 8 2^3 = 8 divisors of 2013 2013 , and all of these are odd.

If n = 2 n=2 , then K 2 K_2 possesses an Euler path, and f ( 2 ) = 3 2013 ( m o d 2 ) f(2) = 3 \equiv 2013 \pmod{2} .

If n 4 n\ge4 is even, then all the vertices of the complete graph K n K_n have odd valency. To be able to have an Euler path, we need to remove edges from K n K_n so that n 2 n-2 vertices have their valencies made even, and we wish to do this in a way which minimizes the reduction to the edge sum. We do this by removing one edge from each of the vertices 1 , 2 , . . . , n 2 1,2,...,n-2 ; since n n is even, this can be done without any repetition of vertices, for example by removing ( 1 , 2 ) (1,2) , ( 3 , 4 ) (3,4) , ..., ( n 3 , n 2 ) (n-3,n-2) . This means that f ( n ) = 1 2 n ( n + 1 ) ( n 1 ) 1 2 ( n 2 ) ( n 1 ) = 1 2 ( n 1 ) [ n ( n + 1 ) ( n 2 ) ] = 1 2 ( n 1 ) ( n 2 + 2 ) = 1 2 n 2 ( n 1 ) + n 1 f(n) \; = \; \tfrac12n(n+1)(n-1) - \tfrac12(n-2)(n-1) \; = \; \tfrac12(n-1)\big[n(n+1) - (n-2)\big] \; = \; \tfrac12(n-1)(n^2 + 2) \; = \; \tfrac12n^2(n-1) + n - 1 and so we note that f ( n ) 1 ( m o d n ) f(n) \equiv -1\pmod{n} this time. If f ( n ) 2013 ( m o d n ) f(n) \equiv 2013 \pmod{n} then 2013 1 ( m o d n ) 2013 \equiv -1 \pmod{n} , so that n n divides 2014 = 2 × 19 × 53 2014 = 2 \times 19 \times 53 . Thus there are 4 4 even divisors of 2014 2014 , and 3 3 of these are greater than 2 2 .

Thus there are 8 + 1 + 3 = 12 8 + 1 + 3 = \boxed{12} positive integers n n such that f ( n ) 2013 ( m o d n ) f(n) \equiv 2013 \pmod{n} (the eight divisors of 2013 2013 , and the four even divisors of 2014 2014 ).

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...