Problema con Algoritmo de la División.

KoRMuZ

Buenas noches MVeros y MVeras.

Me han mandado un ejercicio de matemática discreta hoy, para entregar mañana, y despues de darle mil doscientos millones de vueltas, no se por donde meterle mano.

El ejercicio en cuestión es del bloque de teoría de números, y dentro de este, correspondiente al algoritmo de la división.

Este es el enunciado:

  • Dados dos números enteros cualesquiera, "a" y "b", demostrar que si " c = a2 + b2 ", es impar, entonces " c = 4k + 1 ", con k perteneciente a los enteros positivos.

Si alguien puede echarme un cable, se lo agradezco :)

Kartalon

Será cierto si a y b no pueden valer cero, porque si a o b puede valer cero entonces podemos obtener c=1 y c=3 y obviamente estos es distinto de 4k+1 para todo k natural positivo.

Lo segundo expresa los impares mayores que 5 saltándose uno, supongo que de ahí podrás expresarlo formalmente.

(Y, sinceramente, no se que tiene que ver este ejercicio con los algoritmos de división, algo que yo además nunca he dado en discreta, supongo que entre otras cosas porque mi temario de esta asignatura era distinto, pero vamos, que para mi >50% de discreta era grafos.)

KoRMuZ

Pues no tengo ni idea, pero en nuestro programa, la verdad, hemos tocado por encima los grafos unicamente.

Rabbitter

No acabo de entender exactamente qué se tiene que demostrar. Me explico, esa afirmación es cierta pero no sé de qué manera se puede demostrar. Yo lo veo algo así como que venga alguien y me diga, demuestra que 2·2 son 4. Es un convenio, se definieron los números así y por tanto esa igualdad es cierta por definición.

La primera frase de #2 no es cierta. El caso de c=1 se puede dar con k=0, ya que 0 se acepta como entero positivo (por ejemplo se daría con a=0 y b=1). El caso de c=3 no se puede dar nunca puesto que no hay ningún número entero que cumpla "c" y a la vez dé 3. Lo mismo pasa con el 7, el 11 etc... de ahí que haya un 4 multiplicando la k.

A ver, los números impares se acostumbran a definir siempre como a=2k+1, donde "k" es un número entero positivo, incluyendo el 0. Esto, como he comentado antes es por definición puesto que es una manera de "generar" todos los números impares ya que, por su naturaleza, viene implícito que se vayan alternando pares e impares. De ahí el "+1", puesto que cualquier número multiplicado por 2 será par, también por la definición de estos.

Es decir, este problema sería lo mismo que uno de "generar" números impares pero al tener dos números involucrados, puesto que c=a2+b2, en vez de un 2 multiplicando, aparece un 4.

Para obtener un número "c" impar hace falta que a2 sea par y b2 impar (o viceversa, lo cual no es importante) ya que la suma de dos pares o de dos impares siempre da un número par (repito otra vez, por tal y como se define un número par). Esto implica que uno debe ser par y el otro impar.

Siento meterte este tocho y no poder ayudar, puesto que no te he resuelto nada xD. Simplemente quería decir que no sé exactamente cuál es la intención del profesor al preguntar eso. Quizás quiera una explicación como la que he dado yo, pero esto de demostración matemática tiene -3.

Kartalon

#4 Tienes razón, se me fue la pinza (mucho xD).

Y en el resto pienso igual que tú, no se qué les pide, si formalizar esa demostración o qué...

Y vamos, dentro de la matemática discreta sólo le veo sentido en algún tipo de introducción de conjuntos o algo así.

KoRMuZ

Gracias Rabbiter, a esa misma conclusión es a la que he llegado yo, y estoy en las mismas que tú.

Kartalon, supongo que es formalizar la demostracion como dices tu, y para explicarme de forma brusca, el profesor supongo que busca algo del tipo:

Supongamos que c = a2 + b2, de aqui tenemos que

a2 + b2 = 3 (qsub1 + qsub2) + la raiz cuadrada de un balón de futbol.

Al ser a mayor que w y menor que 99, tenemos que si c es impar es de la forma 4k + 1.


No se si me habré explicado bien xD

Kartalon

Como te he dicho por el IRC no se si esto tiene mucho que ver, pero bueno, aquí te dejo un intento de inducción con mis óxidadas matemáticas xD

4k + 1 = a2 + b2

Para k=0

1 = a²+b² -> para a=1, b=1 se satisface la igualdad

Para k+1

4(k+1)+1 = a² + b²

4k+5 = a² + b²

Suponiendo demostrado 4k + 1 = a2 + b2

4k+5 = 4k+1

4k+4=4k

k+1 != k

Por lo tanto no podemos demostrar por inducción 4k+1 = a2 + b2
(lógico, sólo es igual para los impares)

Suponiendo que ambos tienen que ser impares como pone en lo que me has pasado pues podemos poner:

4k + 1 = (2a+1)2 + (2b+1)2

o algo similar para obligarlos a ser impares, aunque no se si ahí ya estamos modificando el problema.

No se, aquí te dejo mis divagaciones sobre como puede ser la demostración formal de esto, por si te ayudan en lo más mínimo.

PD: Por lo que dices qué andáis deduzco que los tiros no van por aquí, pero bleh, ya que he estado divagando aquí lo dejo para deshonra propia xD

Rabbitter

Bien, una vez más, #7 lo ha intuido, pero le ha faltado atinar completamente xD. Gracias a lo que ha dicho he podido sacar lo que creo que se busca.

Como ya he dicho uno tiene que ser par y otro impar, no los dos impares. Es decir, que según #7 se podría hacer lo siguiente:

c=4k+1
c=a2+b2

Por tanto,

4k+1=a2+b2

Se fuerza a que "a" sea par y "b" impar, esto es:

a=2t
b=2r+1 donde "t" y "r" son cualquier entero positivo.

Por lo que

4k+1=(2t)2+(2r+1)2

Desarrollando

4k+1=4t2+4r2+1+4r

Que agrupando

4k+1=4(t2+r2+r)+1

Es decir, que la k valdría t2+r2+r

(a y b son intercambiables, por lo que esta demostración es general)

Espero que te sirva.

2 comentarios moderados
werty

#8 = fin

podemos añadir al principio que:

(1)"imparimpar=impar"
(2)"par
par=par"
(3)"par+impar=impar"

por lo que si c=impar -> (3), "a²" impar y "b²" par ó "a²" par y "b²" impar, y por (1) y (2), "a" impar y "b" par ó "a" par y "b" impar.

KoRMuZ

Gracias a todos, creo que me habéis salvao la asignatura!

Panch

De nada, para eso estamos !

J

Un placer.

Soltrac

Joder, hace 450000 millones de años q no doy estas cosas, pero este tipo de ejercicios no se resolvía con lo de........se demuestra para K = 0.

Suponiendo q es verdad para K = n, se demuestra para K = n+1? O estoy mezclando gilipolleces? XDDDD

KoRMuZ

Bueno, como desenlace a todo esto, simplemente me gustaría dar las gracias a todos los que habéis echado una mano.

Acabo de ver las notas y un 10 en el ejercicio, y también, en la asignatura :D

GRACIAS MEDIAVIDA

Rabbitter

#16 Me alegro que al final fuera eso, ya que no estaba muy claro si era lo que pretendían que hicieras.

Usuarios habituales

  • Rabbitter
  • KoRMuZ
  • Soltrac
  • Panch
  • werty
  • Hurtiek
  • Kartalon