#300 No entiendo bien tu pregunta, lo siento. ¿Puedes reformularla?
#301 Básicamente quiero que pienses en lo siguiente:
Aún cuando un paciente sabe que todos tienen cáncer si nadie dice que alguien tiene cáncer, qué puede llevarle a saber con certeza que el tambien lo tiene?
#273 Sólo por dar algo de info guay. Eso está basado en la paradoja del cumpleaños: http://es.wikipedia.org/wiki/Paradoja_del_cumplea%C3%B1os
Que es una de las bases de los ataques criptográficos a algunos algoritmos de hasheado y demás.
Ataque del cumpleaños: http://es.wikipedia.org/wiki/Ataque_de_cumplea%C3%B1os
La solucion al anterior es que había alumnos gemelos.
Problema 9: eslabones
Dificultad: 3/10
Un joyero le indica a su aprendiz que debe hacer una pulsera con 4 trozos de cadena de tres eslabones cada uno.
El aprendiz prepara material para hacer 4 soldaduras, pero el joyero le mira con desaprobación.
¿Qué debería hacer el aprendiz para ahorrar material en soldaduras?
#302 #304 El desencadenante es saber que tienes que suicidarte, no saber que > 1 persona tiene cáncer, porque eso ya lo saben. Igual que los monjes, que ya saben que hay > 1 que está marcado, pero lo que les hace 'peregrinar' es el hecho de que el padre les diga que deben peregrinar, no que les diga que hay > 1 marcado.
No se si no me estoy explicando. Si supieran con antelación que deben suicidarse, lo harían a los 100 días de conocerse/entrar al hospital, no cuando el médico les diga que hay 1 que tiene cáncer.
Resumiendo, no entiendo que me digáis que el desencadenante sea saber que x>1 para unas personas que YA saben que x>98 , salvo que x>1 tenga mayor grado de certeza que x>98. Pero entonces estamos hablando de que el enunciado es tramposo y se podría decir que los enfermos 'intuyen' que el resto tiene cáncer, no que lo saben.
PD: Entiendo la solución, no tengo ningún problema con ella ni con extrapolar a n. Lo que defiendo básicamente es:
O los pacientes NO saben quien tiene cáncer hasta el día en el que el médico habla con ellos.
O los pacientes NO saben que se tienen que suicidar hasta que el médico habla con ellos.
Si los pacientes SI saben que se tienen que suicidar y SI saben que el resto tiene cáncer, el desencadenante no puede ser jamás que el médico les diga que alguien está enfermo porque es algo que no cambia en absoluto las premisas que ya se conocían (salvo que entren a jugar grados de certeza como he comentado antes). No entiendo como se puede discutir esto último.
Un paciente no tiene ningún motivo para pensar que tiene cáncer hasta que se dice esa frase. Esa frase dispara la posibilidad de que ellos puedan tener cáncer.
#309 Es que no nos estamos entendiendo. No discuto la solución, sino el momento en el que se produce y lo que la desencadena.
¿Qué les impide suicidarse a todos el día 100, cuando se hayan dado cuenta de que los 99 restantes no se han suicidado en el día 99 porque hay alguien más? No hace falta la afirmación '1 al menos tiene cáncer'. Eso no es el desencadenante.
Desencadena la acción:
- El conocimiento del estado del resto de pacientes
- El conocimiento de como actuar cuando se conoce el propio estado
Básicamente, #290 lo explica perfectamente. La frase 'al menos 1 tiene cáncer' no es el desencadenante. Los pacientes se hubieran suicidado a los 100 días de entrar al hospital, no a los 100 días de esa frase.
#310 en el caso más sencillo (2 pacientes; tu y yo)
Qué puede hacer que yo conozca mi estado de salud antes de que el médico diga que, al menos, uno tiene cáncer?
Te veo todos los días y sé que tienes cáncer pero si no te suicidas es porque no lo sabes. Ademas no puedo decirtelo. Por qué ibas a suicidarte entonces sin una 'señal' externa?
El médico afirmando que, al menos uno tiene cáncer no revela información extra pero hace que el procedimiento lógico pueda iniciarse.
pd. Si aqui no llegamos a un acuerdo, significa que nunca vamos a hacerlo.
#311 El problema es que el enunciado dice que "todos tienen cancer" pese a que ellos no lo sepan, por lo tanto todos ven a pacientes con cancer y por tanto no necesitan el dato de "al menos 1 tiene cáncer" porque todos ellos ya lo ven cada día y ya lo saben.
Basicamente estas dando un dato que ya conocen.
Acabo de descubrir ahora este hilo, pero pillo asiento para futuras rayadas.
#313 Ya pero es que el supuesto no son 2 pacientes, son 99. Con 2 pacientes sí que necesitas ese dato, con 99 no, porque es un dato redundante.
Todo sea que el enunciado no esta bien redactado, ese "al menos 1" es efectivamente para hacer el caso base, pero en este enunciado sobra porque es información redundante.
#314 vale, imaginate que somos 99. Te vuelvo a plantear las preguntas de #311
Qué puede hacer que yo conozca mi estado de salud antes de que el médico diga que, al menos, uno tiene cáncer?
Veo a los 98 restantes todos los días y sé que teneis cáncer pero si no os suicidais es porque no lo sabeis. Ademas no os lo puedo decir. Por qué ibais a suicidaros entonces sin una 'señal' externa?
#315 Pero a ver, si tu ves que todos tienen cancer y desconoces tu estado y sois 99 tíos, algo es evidente: que todos veis como mínimo a un tío con cáncer.
Entonces que el médico diga "al menos uno tiene cáncer" es una redundancia a la información que ya tienes, pues todos ya sabíais que al menos uno tenía cáncer, no aporta ninguna información nueva. Y no solo todoso sabíais que al menos uno ya tenía cáncer, sino que además sabíais que los otros saben que al menos 1 tiene cáncer.
> El médico afirmando que, al menos uno tiene cáncer no revela información extra pero hace que el procedimiento lógico pueda iniciarse.
Mismo problema, dos pacientes.
No se dice que "al menos uno tiene cáncer" en público.
A piensa que B piensa que nadie tiene cáncer.
B piensa que A piensa que nadie tiene cáncer.
A sabe que al menos uno tiene cáncer.
B sabe que al menos uno tiene cáncer.
El director dice "al menos uno tiene cáncer".
¿Ha dicho algo que ambos sabían? Sí.
¿La información es redundante? No.
Esa frase aporta información. La información que proporciona es "hay al menos uno que tiene cáncer, Y PUEDES SER TÚ".
Porque lo que cada uno piensa es "hay al menos uno que tiene cáncer, Y NO SOY YO".
Así que aunque a priori parezca que no da información, sí que lo hace.
Estas dando mucho de si el enunciado de un problema lógico. Es como si nos pusieramos a discutir si los 99 pacientes llegaron a la vez o si como sabemos que se suicidaban antes si nadie les decía que tienen cáncer.
Ambos supuestos son válidos, zanjemos el debate.
No se cuantas veces lo he dicho ya pero el tema es el common knowledge.
Aqui #315 #316 #319 se discute (uno de los mejores matematicos del momento por cierto )
Aqui tambien.
#286 me has herido mi orgullo de matemático xD. Me siento tentado a dar explicaciones pero no entiendo el por qué de este ataque tan gratuito ni sé qué tienen que ver las matemáticas con estos problemas así que ahí lo dejo.
#286 Interesantísimo comentario! Sobre la parte del ingenio humano y mi solución, ojo que va más allá que ese simple trocito que comentas. Realmente, en cada entrevista, tienes tres posibilidades: que no esté repetida la combinación, que justo lo esté, o que lo esté y además tengas apuntada una repetición anterior. Todo esto es para controlar, estadísticamente, que hayan habido (o no) entrevistas a otros abducidos entre la anterior y la presente, y así variar el contador para acercar la cuenta a un número de entrevistados total a un número más probable.
Está claro que no es 100% probable, pero yo me quedo contento con ese porcentaje de error. Y por cierto, no me había imaginado que era más eficiente en cuanto a número de entrevistas que la solución original, suena interesante xD.
Igualmente es una chorradita, es decir, está súper mal programado, sin optimización ninguna, y sin hacer un análisis matemático-lógico de la funcionalidad.
PD: Van más de 100.000 simulaciones ya para 20 y todavía ni un sólo error!
#322 por cierto, creo que demostré que no puede haber una estrategia (no estadística) sin un observador privilegiado!
#323 Sí, es algo que ya me imaginaba como dije páginas atrás, al fin y al cabo dos interruptores con dos posiciones son sólo 4 posibles números, que incluso definiendo un protocolo binario de distancia 1 y cíclico pierde información.
Yo por eso me puse con el asuntillo este, porque me parecía interesante tratar de definir un protocolo cuya eficacia fuese elevada. Partiendo de la base de que es más eficiente que la solución normal en cuanto a entrevistas, y que para n=20 tiene una eficacia mayor al 99.999%, ¿cómo se consideraría de válido a nivel matemático? (también teniendo en cuenta que la mayoría de operaciones son un pifostio sin analizar ni nada hecho en un rato tonto xD) Tengo entendido que incluso las comunicaciones inalámbricas tienen más error, de ahí el uso de CRCs y el uso de bits de paridad en los paquetes.
#324 bueno, primero habría que demostrar que el protocolo tiene esa eficacia (no comprobar, sino demostrar xD). El problema es que tienes que asumir una distribución de probabilidad concreta en las llamadas para que tenga esta tasa de error, si vas a un worst-case scenario te sale que tu algoritmo no vale. Pero bueno, suponiendo que los llaman de manera uniformemente distribuida, y demuestras que tienes esa tasa de acierto (no parece excesivamente complicado), pues sería válido a nivel "ingenieril". A nivel matemático no hay tal cosa como válido o no válido xD, simplemente se dice la tasa de error y ya está.
Incluso podrías probar por ejemplo que en lugar de esperar 5 entrevistas (o lo que sea), a partir de la 4ta diga la frase con probabilidad p, a ver si mejora, empeora, etc.
Respecto a demostrar que no se puede, es un poco más complicado porque no sólo tienes esas 4 variables sino también el "contador" que guarda cada uno, que por poder ser puede ser un número real. Yo he tenido que usar http://en.wikipedia.org/wiki/Group_action esto para hacerlo bien aunque probablemente sea matar moscas a cañonazos XD.
#327 Es fácil caer en esa suposición, pero la respuesta sólo es una xD
http://en.wikipedia.org/wiki/Common_knowledge_%28logic%29#Answer
Piensa que el caso de n=3 se nutre del caso n=2, y conforme n asciende, la llamada recursiva al orden inferior del problema conforme pasen los días hará que llegue de nuevo a n=2.
Veo donde acaba esto porque he resuelto problemas de este estilo, pero cuando hago la comprobación manual no lo entiendo. Puedes echarle un ojo a ver si me lo aclaras?
Hipno, ya he visto donde está el fallo y es que siendo C no se si A sabe que B sabe que A está enfermo... Ok ok!
Sobre la paradoja del cumpleaños, en la wiki aparece la siguiente fórmula:
p = 365!/365n(365-n)!, que define la probabilidad para n personas de cumplir el mismo día.
Supongamos que el año tiene 2 días.
p = 1-2!/22(2-2)! y que metemos en una habitación a 2 personas. Creo que está claro que la probabilidad de que tengan cumpleaños el mismo día es 50%.
En este caso p = 1/2 ¡se cumple!
¿Y si tuvieramos 6 días y 6 personas?
p = 1-6!/66(6-6)! = 98%
wow! Aún aumentando el numero de personas y de días del año proporcionalmente, la probabilidad aumenta increíblemente.
Entonces, podremos decir que si 6 personas tiran un dado (tirada = cumpleaños) la probabilidad de que repitan un número es del 98% :o
#306 no entiendo el enunciado.
Tenemos O-O-O; O-O-O; O-O-O; O-O-O; y queremos... ¿ahorrar en material de aporte de soldadura?¿ahorrar en anillas? ¿hacer el mínimo de soldaduras?
P.D: el de los dioses se puede resolver con 14 dioses + 1 que sabes que es neutral.
