Loading [MathJax]/jax/element/mml/optable/Latin1Supplement.js

33 votos

Escribir 100 como suma de dos enteros positivos

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.

37voto

Leg Puntos 14825

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).

11voto

Keith Puntos 889

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.

3voto

Derick Bailey Puntos 37859

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.

2voto

Gary. Puntos 1727

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=de100 a

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

De700 (+11k)+1100(b-7k)=de100 a

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

1voto

Jonny Puntos 1970

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".

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X