¿Es (a / b) /c igual a a/(b*c) para la división de enteros?

Question

Deje $\div$ denotar un operador binario que devuelve la parte entera del cociente de dos números enteros, es decir, (suponiendo que los números enteros son positivos) $a \div b = \left\lfloor \frac ab \right\rfloor$. Esto corresponde a la división de enteros operador en muchos lenguajes de programación (por ejemplo, el // operador en Python).

He observado que, cuando $a$, $b$ y $c$ son enteros positivos, los valores de $(a \div b) \div c$ $a \div (b \times c)$ son iguales.

He tratado de encontrar un contra-ejemplo mediante el siguiente código en Python, pero no fue capaz de encontrar uno:

from random import randint

while True:

    a = randint(1, 10000000000)
    b = randint(1, 10000)
    c = randint(1, 10000)

    lhs = a//b
    lhs = lhs//c

    rhs = a//(b *c)

    if lhs != rhs:
        print a, b, c
        break

Podría alguien por favor proporcione un contraejemplo si la afirmación que he hecho no es cierto o que una prueba que demuestra que es siempre verdadera?

Información Adicional:

1. Por favor, tenga en cuenta que todos los de la división de los operadores utilizados anteriormente corresponden a la división de enteros.
2. La versión de Python es 2.7.12.
3. Hice esta pregunta en StackOverflow y se sugirió que no, que me pregunte aquí.
4. Yo no era capaz de encontrar una etiqueta que dice entero de la división, así que yo no lo uso y sugerencias son bienvenidos.

Answer 1

Escriba $a=qb+r$, $0 \le r \lt b$, que $a \div b=q$.

A continuación, escriba $q=sc+t$, $0 \le t \lt c$, que $(a \div b) \div c=s$.

Ahora tenemos $a=b(sc+t)+r=bcs+bt+r$. Como $$\begin{aligned} bt+r &\le b(c-1)+(b-1) \\ &=bc-b+b-1 \\ &=bc-1, \end{aligned}$$ we have $a # \div (AC) = $s.

Answer 2

Es un poco más fácil hacer lo que Ross.

Que $q,r$ ser enteros tales que $a = b·c·q+r$ y $0 \le r < b·c$. Entonces $r \div b \le r / b < c$.

Entonces $( a \div b ) \div c = ( c·q + ( r \div b ) ) \div c = q + ( r \div b ) \div c = q = a \div ( b·c )$.

(Simplemente dos veces utilizamos el hecho fácil que $(d·x+y) \div d = x + y \div d$ % enteros $x,y,d$con $d > 0$.)

Answer 3

Otra forma de pensar acerca de esto es que dicen que usted tiene $N$ dulces que desea distribuir entre $a * b$ niños. ¿Cuál es el máximo número de caramelos que un niño puede conseguir, dado que distribuya los dulces igualmente.

La respuesta es $\Big\lfloor\frac{N}{a*b}\Big\rfloor$

Tenga en cuenta que usted puede dividir el $a * b$ de los niños en $a$ de las clases. Dado que cada estudiante obtiene un número igual de dulces, cada clase también se obtiene un número igual de dulces, que es $\le \left\lfloor\frac{N}{a}\right\rfloor$. Ahora, para cada clase, de distribuir estos muchos caramelos entre los $b$ de los niños, de modo que cada niño recibe

$$\left\lfloor\frac{\left\lfloor\frac{N}{a}\right\rfloor}{b}\right\rfloor$$

Por lo tanto,

$$\left\lfloor\frac{\left\lfloor\frac{N}{a}\right\rfloor}{b}\right\rfloor = \left\lfloor\frac{N}{a*b}\right\rfloor$$

---

Yo no demostrar que podemos dar a $\Big\lfloor\frac{N}{a}\Big\rfloor$ caramelos a cada clase y asegurarse de que cada alumno obtendrá el número óptimo de caramelos. Esto puede ser demostrado fácilmente. Digamos que cada clase se $Y$ dulces en la solución óptima. Entonces, tenemos:

$$ S * \le N \implica Y \le \frac{N}{a} $$

De ahí que podamos dar a cada clase de $\left\lfloor\frac{N}{a}\right\rfloor$ dulces para una óptima distribución.

Tenga en cuenta que cada clase puede también rechazar algunos caramelos.

Answer 4

$$a \text{\\} b \text{\\} c = d$$ $$\exists x.~~ a\text{\\}b = x ~~\land~~ x\text{\\}c = d$$ $$\exists x.~~ xb \in [a - b + 1 \dots a] ~~\land~~ cd \in [x - c + 1 \dots x]$$ $$\exists x.~~ xb \in [a - b + 1 \dots a] ~~\land~~ bcd \in [xb - bc + b \dots xb]$$ $$\exists x.~~ xb \in [a - b + 1 \dots a] ~~\land~~ bcd \in [(a - b + 1) - bc + b \dots a]$$ $$bcd \in [a - bc + 1 \dots a]$$ $$a\text{\\}(bc) = d$$

Answer 5

Esto parece funcionar siempre, porque es tautología matemática $-$ no una evidente aunque. Vamos a denotar la división entera $\div$ y decir que tenemos $(a\div b)\div c=s$. Esto significa que

$$a\div b=sc+r_c\quad\implies\quad a=(sc+r_c)b+r_b=sbc+\underbrace{r_cb+r_b}_R$$

donde $r_c\in\{0,...,c-1\}$ y $r_b\in\{0,...,b-1\}$ indican que el resto después de la división de $c$ y $b$ respectivamente. Por lo tanto tenemos

$$R=r_cb+r_b\le b(c-1)+b-1=bc-b+b-1=bc-1<bc.$$

Esto es suficiente para concluir que

$$a\div(bc)=(sbc+R)\div(bc)=s$$

desde $R$ es a pequeño para marcar la diferencia después de la división.