Escribir 100 como suma de dos enteros positivos

Question

Escribe $100$ como la suma de dos enteros positivos, uno de ellos es un múltiplo de $7 dólares, mientras que el otro es un múltiplo de $11$.

Desde $100$ no es un número grande, he seguido el sencillo razonamiento de la escritura de todos los múltiplos de hasta $100$ de $11$ o $7$, y luego encontrar el complemento que es también un múltiplo de la otra. Así que, a continuación, $100 = 44 + 56 = 4 \times 11 + 8 \times 7$.

Pero es la manera inteligente de hacerlo? Es la forma en que se suponía que iba a resolverlo? Estoy pensando acerca de una situación con un número realmente elevado que convierte mi plug-en el método de ordenación de imprudente.

Answer 1

De Bezout del Lexema, tenga en cuenta que dado que $\gcd(7,11) = 1$, que divide a $100 de$ existe $x,y \in \mathbb{Z}$ tal que $7x+11y=100$.

Un candidato de la solución es de $(x,y) = (8,4)$.

El resto de la solución está dada por $(x,y) = (8+11 m,4-7m)$, donde $m \in \mathbb{Z}$. Ya que estamos buscando enteros positivos como soluciones, necesitamos $8+11 m > 0$ y $4-7m>0$, lo que nos da $-\frac8{11}<m<\frac47$. Esto significa que el único valor de $m$, cuando restringimos $x,$ y para enteros positivos es de $m=0$, lo que nos da $(x,y) = (8,4)$ como la única solución en los enteros positivos.

---

Si no te gusta adivinar su candidato solución, más algorítmico procedimiento es el uso de Euclides' algoritmo para obtener la solución a $7a+11b=1$, que es como sigue.

Tenemos \begin{align} 11 & = 7 \cdot (1) + 4 \implica 4 = 11 - 7 \cdot (1)\\ 7 & = 4 \cdot (1) + 3 \implica 3 = 7 - 4 \cdot (1) \implica 3 = 7 - (11-7\cdot (1))\cdot (1) = 2\cdot 7 - 11\\ 4 y = 3 \cdot (1) + 1 \implica 1 = 4 - 3 \cdot (1) \implica que 1 = (11-7 \cdot(1)) - (2\cdot 7 - 11) \cdot 1 = 11 \cdot 2-7 \cdot 3 \end{align} Esto significa que la solución a $7a+11b=1$ el uso de Euclides' algoritmo es de $(-3,2)$. Por lo tanto, el candidato de la solución de $7x+11y=100$ es $(-300,200)$. Ahora todas las posibles soluciones están dadas por $(x,y) = (-300+11n,200-7n)$. Ya tenemos $x$ y $y$ a ser positivo, necesitamos $-300+11n > 0$ y $200-7n > 0$, lo que nos da $$\dfrac{300}{11} < n < \dfrac{200}7 \implica 27 \dfrac3{11} < n < 28 \dfrac47$$ El único entero en este rango es de $n=28$, que a su vez da $(x,y) = (8,4)$.

Answer 2

Un esfuerzo para evitar cualquier enumeración o la ocultación de un salto inductivo para la respuesta.

$7a + 11b = 100: a,b \in N$

$ 11b \leq 100 - 7 = 93$

$\implica 1 \leq b \leq 8$

$ 7(a+b) = 100 - 4b$

$\implica 100 - 4b \equiv 0 \mod 7$

$\implica 25 - b \equiv 0 \mod 7 $

$\implica b \equiv 25 \mod 7 $

$\implica b \equiv 4 \mod 7$

$ \implica b = 4 + 7n$

Sabemos que $ 1 \leq b \leq 8 $.

Así que tenemos un total de $b \equiv 25 \mod 7$, entonces $ b = 4$ y por tanto $a = 8$.

Answer 3

Pero es la manera inteligente de hacerlo?

Se le pedirá que encontrar un y b , de modo que $7a+11b=100\iff7(a+b)+4b=100\ffi$

$4\big[(a+b)+b\big]+3(a+b)=100\iff3\Big\{\big[(a+b)+b\big]+(a+b)\Big\}+\big[(a+b)+b\big]=$ $100$.

Pero $100=99+1=3\cdot33+1$, entonces $a+2b=1\iff2a+4b=2$, y $2a+3b=33$. De ello se sigue que $b_0=-31$ y $a_0=63$ es una solución. Pero, de nuevo, por lo que son todos los números de la forma $a_k=63-11k$ y $b_k=-31+7k$, con $k\in$ Z. Todo lo que tenemos que hacer ahora es coger un par de cuyos componentes son positivos. La primera ecuación implica $k<6$, y el segundo, $k>4$.

Answer 4

Desde $\operatorname{mcd}(7,11)=1$ , usted puede encontrar $a,b \in \mathbb Z$ con $7a+11b=1$. Ahora multiplique ambos lados de la ecuación por $100$ para conseguir uno (y por lo tanto todo es posible) resultados:

$$700a+1100b=de$100 a$

Una vez que usted tiene una solución para $700a+1100b=100$, usted tiene todas las soluciones:

$De$700 (+11k)+1100(b-7k)=de$100 a$

Usted puede encontrar $k$, de modo que ambos coeficientes son positivos.

Answer 5

Aunque ciertamente no es el ideal de la solución, este problema es, sin duda, en el ámbito de la Programación entera. Como muchos otros han señalado, hay más directa enfoques. Sin embargo, sospecho que la ILP solucionadores podría operar de manera eficiente en su caso, y requiere menos el pensamiento de capital".