Got a bijection?

i = 1 n A B i + j = 1 m B A j = f ( n ) f ( m ) \large\sum _{ i=1 }^{ n }{ \left\lfloor \frac { A }{ B } i \right\rfloor } +\sum _{ j=1 }^{ m }{ \left\lfloor \frac { B }{ A } j \right\rfloor } = f(n)f(m)

Let A , B A,B be odd natural numbers that are relatively prime, and let n = B 1 2 n= \frac { B-1 }{ 2 } , m = A 1 2 m=\frac { A-1 }{ 2 } such that the equation above is fulfilled. If f f is a linear function with f ( 1 ) > 0 f(1) > 0 , what is the sum of the coefficients of f ( x ) f(x) ?


The answer is 1.

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

Ivan Koswara
Sep 22, 2015

This is an informal solution (informal for me, at least).

Consider a lattice grid, and look at the grid points. Draw the line y = A B x y = \frac{A}{B} x , and observe the rectangle bounded by y = 0 , y = A 2 , x = 0 , x = B 2 y = 0, y = \frac{A}{2}, x = 0, x = \frac{B}{2} . Note that the line y = A B x y = \frac{A}{B} x passes through two of the corners ( ( 0 , 0 ) (0,0) and ( A 2 , B 2 ) \left( \frac{A}{2}, \frac{B}{2} \right) ).

Now note that A B x 0 \left\lfloor \frac{A}{B} x_0 \right\rfloor counts the number of grid points below the line (but above the x-axis) in column x = x 0 x = x_0 , so the first summation gives the number of grid points within the rectangle, below the line (green region). Likewise, B A y 0 \left\lfloor \frac{B}{A} y_0 \right\rfloor counts the number of grid points to the left of the line (but to the right of the y-axis) in row y = y 0 y = y_0 , so the second summation gives the number of grid points within the rectangle, to the left of the line (purple region). But to the left of the line is equal to above the line. Also, no grid points other than those in the axes are passed by the sides or the line (because A , B A,B are relatively prime and odd). This means all grid points are accounted for. But the number of grid points is trivially m n mn . Thus f ( m ) f ( n ) = m n f(m)f(n) = mn , so f ( n ) = n f(n) = n .

Moderator note:

Nothing informal about this clearly presented solution.

This is the key fact used in several proofs of quadratic reciprocity, including Eisenstein's.

Patrick Corn - 5 years, 8 months ago

This solution is so clear. I set function to be ax+b and input m=4,n=5 and m=3,n=4 to know that f(x)=x.

Kelvin Hong - 3 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...