Truco de 17 camellos

Question

Los siguientes popular matemática parábola es bien conocido:

Un padre dejó a 17 camellos a sus tres hijos y, de acuerdo a la voluntad, el hijo mayor debe ser dado de la mitad de los camellos, el hijo del medio de la una tercera parte y el hijo más joven de la novena. Esto es difícil de hacer, pero un hombre sabio ayudó a los hijos: agregó su camello, el hijo mayor tomó 18/2=9 camellos, el segundo hijo tomó 18/3=6 camellos, el tercer hijo 18/9=2 camellos y el hombre sabio tomó su propio camello y se fue.

Pido para aplicaciones de este método: cuando algo es añadido artificialmente, de alguna manera utilizan y, después de que, llevado (como fue este 18^th camello de un hombre sabio).

Permítanme comenzar con dos ejemplos de la teoría de grafos:

1. Sabemos de la Sala lema: si alguna de las $k=1,2,\dots$ de los hombres en una ciudad como al menos $k$ mujeres en el total, entonces todos los hombres pueden casarse, de modo que cada uno de ellos le gusta a su esposa. Cómo concluir la siguiente versión generalizada?

   Si alguna de las $k$ a hombres como a menos $k-s$ mujeres en el total, pero entonces todos los $s$ hombres pueden casarse.

   Prueba. Agregar $s$ extra de las mujeres (camello-mujeres) querido por todos los hombres. Aplicar habitual Sala de lema, después de que decir perdón a los maridos de extra de las mujeres.

2. Esto es debido a Noga Alon, recientemente popularizada por Gil Kalai. Cómo encontrar un perfecto maridaje en un bipartito $r$-regular multigraph? Si $r$ es una potencia de 2, esto es fácil por inducción. De hecho, hay un ciclo Euleriano en cada componente conectado. Tomando los bordes también tienes la opción de partición de nuestro gráfico en dos $r/2$-regular multigraphs. Por otra parte, tenemos una partición de bordes en $r$ perfecto elecciones. Ahora, si $r$ no es una potencia de 2, tomar un gran $N$ y escribir $2^N=rq+t$, $0<t<r$. Reemplazar cada borde de nuestro multigraph en $q$ bordes, también añadir bordes formados por arbitraria $t$ perfecto elecciones. Esta nueva multigraph puede ser dividido en $2^N$ perfecto elecciones, y si $N$ es lo suficientemente grande, que algunos de ellos no contienen bordes.

Answer 1

Variables de holgura en la programación lineal. Cita del enlace:

En un problema de optimización, una variable de holgura es una variable que se agrega a una restricción de desigualdad para transformarla en una igualdad. La introducción de una variable de holgura reemplaza una restricción de desigualdad con una restricción de igualdad y una restricción de no negatividad.

Answer 2

Multiplicadores de Lagrange: para extremize $f(x,y)$ sujeto a la restricción $g(x,y)=0$, agregar una variable $\lambda$ y

introducir una función auxiliar $$ {\mathcal {L}}(x,y,\lambda )=f(x,y)-\lambda \cdot g(x,y) $$ y resolver [sin restricciones!] $$ \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0. $$ Tenga en cuenta que esto equivale a la solución de tres ecuaciones con tres incógnitas. Este es el método de multiplicadores de Lagrange. Tenga en cuenta que $\nabla _{\lambda }{\mathcal {L}}(x,y,\lambda )=0$ implica $g(x, y) = 0$. Para resumir $$ {\displaystyle \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0\ffi {\begin{cases}\nabla _{x,y}f(x,y)=\lambda \nabla _{x,y}g(x,y)\\g(x,y)=0.\end{casos}}} $$

Answer 3

Tal vez este ejemplo es demasiado elemental para este sitio, pero diría que la prueba de que un subconjunto cerrado de un conjunto compacto es compacto en sí se parece a esto. Dada una cubierta abierta de un$A$ donde$A$ es un subconjunto cerrado de un conjunto compacto$K$ agregamos$K\setminus A$ a la cubierta, obtenga una subcubierta finita usando la compacidad de$K$ y luego descarte el conjunto extra ya que no es necesario para cubrir$A$.

Answer 4

El AM-GM de la desigualdad (así como de otras desigualdades, por ejemplo, la versión discreta de la desigualdad de Jensen) puede ser probado con el siguiente truco debido a Cauchy, conocido como "adelante-atrás de la inducción":

Deje $P(n)$ ser la proposición "Para cualquier $n$ positivos reales, $\frac1n \sum a_i \geq (\prod a_i)^{1/n}$" (AM-GM de la desigualdad con $n$ términos).

La prueba se compone de tres partes.

1. Demostrar $P(2)$ directamente.
2. El uso de $P(n)$ e $P(2)$ a probar $P(2n)$ (por lo tanto, por inducción podemos ahora demostrar $P(2^k)$ por cada $k$).
3. Dado $n$ términos de $a_1,a_2,\dots, a_{n}$, el uso de $P(n+1)$ sobre el $n+1$ términos de $a_1,a_2,\dots, a_n, \frac1n \sum a_i$ a derivar $P(n)$, con un par de manipulaciones.

Así que cuando queremos demostrar a $P(n)$ para un genérico $n$, usamos la parte 3 para agregar varios "fantasma" condiciones iguales a $AM=\frac1n \sum a_i$ hacer $n$ una potencia de 2, entonces el uso de piezas de 1+2.

La prueba se describe en más detalle aquí.

Answer 5

La forma habitual para demostrar la Fuerte Nullstellensatz de los Débiles Nullstellensatz es el llamado Rabinowitsch truco.

En resumen, añadiendo un extra de variable nos permite aplicar el "débil" de la versión del teorema; entonces podemos volver a la menor polinomio anillo y obtener el "fuerte" de la versión basta con borrar denominadores.

Ver también este MO pregunta.