¿Cómo podemos demostrar que si dividimos N entre 1, 2, 3, …, N, entonces podemos obtener como máximo 2 * sqrt (N) diferentes cocientes enteros?

Answer 1

El conjunto de cocientes [matemática] Q: = \ left \ {\ left \ lfloor \ frac Nx \ right \ rfloor \, \ bigg | \; x \ in \ {1,2, \ dots, N \} \ right \} [/ math] es la unión de

[matemáticas] A: = \ left \ {\ left \ lfloor \ frac Nx \ right \ rfloor \, \ bigg | \; x \ in \ left \ {1,2, \ dots \ left \ lfloor \ sqrt {N} \ right \ rfloor \ right \} \ right \} [/ math] y

[matemáticas] B: = \ left \ {\ left \ lfloor \ frac Nx \ right \ rfloor \, \ bigg | \; x \ in \ left \ {\ left \ lfloor \ sqrt {N} \ right \ rfloor + 1, \ dots, N \ right \} \ right \}. [/ math]

[math] A [/ math] tiene un tamaño como máximo [math] \ left \ lfloor \ sqrt N \ right \ rfloor [/ math], ya que [math] x [/ math] está por encima de esos valores.

[matemática] B \ subseteq \ left \ {1,2, \ dots, \ left \ lfloor \ sqrt N \ right \ rfloor \ right \} [/ math], como [math] 1 \ leq \ left \ lfloor \ frac Nx \ right \ rfloor \ leq \ left \ lfloor \ sqrt N \ right \ rfloor [/ math] para [math] N \ geq x \ geq \ left \ lfloor \ sqrt N \ right \ rfloor + 1 [/ math]. Por lo tanto, a lo sumo hay [math] \ left \ lfloor \ sqrt N \ right \ rfloor [/ math] valores en [math] B [/ math].

Esto produce un total de cocientes [matemáticos] 2 \ cdot \ left \ lfloor \ sqrt N \ right \ rfloor [/ math] como máximo.

Dado [math] x [/ math], queremos encontrar el valor más pequeño [math] y = a [/ math] y el valor más grande [math] y = b [/ math] tal que [math] \ left \ lfloor \ frac Ny \ right \ rfloor = x [/ math]. Según la definición de [math] \ lfloor. \ Rfloor [/ math], esta ecuación es equivalente a

[matemáticas] x \ leq \ frac Ny <x + 1 [/ matemáticas].

Esto da

[matemáticas] \ frac N {x + 1} <y \ leq \ frac Nx [/ matemáticas].

Por lo tanto, [matemáticas] a = \ left \ lfloor \ frac N {x + 1} \ right \ rfloor + 1 [/ math] y [math] b = \ left \ lfloor \ frac Nx \ right \ rfloor. [/ Math ]