buenas, Encontré esta solución del ejercicio pero hay una parte de la demo que marque en rosa que no me queda clara pero tampoco se me ocurre como finalizar la demostración, si me pueden dar una mano, gracias 
hola natasha,
sobre la prueba (está casi) comento un par de cosas:
- el objetivo de la prueba no se menciona y debería ser probar que k=m. es importante explicitarlo para que esté claro al lector y para que no perdamos el rumbo mientras intentamos construir una prueba que funcione.
por tanto, luego de probar que mi solución greedy "stays ahead" de una solución óptima, tengo que probar k=m. sugiero, comenzar pensando qué implica k>m respecto a la cobertura de las casas y llegar a un absurdo.
- el paso base no implica e1=e1*. es trivial probar que e1>=e1* porque elijo la posición de la primer antena lo más alejada posible de la primera casa y por tanto cualquier otra posición (en particular e1*) es menor o igual que e1.
- en la tesis inductiva, me sobra lo rosa. solamente agregaría al párrafo anterior que "como ei+1 se ubica los más lejos posible de forma de cubrir a todas las casas no cubiertas entre ei y ei+1, entonces ei+1>=e1+1*.
saludos
sobre la prueba (está casi) comento un par de cosas:
- el objetivo de la prueba no se menciona y debería ser probar que k=m. es importante explicitarlo para que esté claro al lector y para que no perdamos el rumbo mientras intentamos construir una prueba que funcione.
por tanto, luego de probar que mi solución greedy "stays ahead" de una solución óptima, tengo que probar k=m. sugiero, comenzar pensando qué implica k>m respecto a la cobertura de las casas y llegar a un absurdo.
- el paso base no implica e1=e1*. es trivial probar que e1>=e1* porque elijo la posición de la primer antena lo más alejada posible de la primera casa y por tanto cualquier otra posición (en particular e1*) es menor o igual que e1.
- en la tesis inductiva, me sobra lo rosa. solamente agregaría al párrafo anterior que "como ei+1 se ubica los más lejos posible de forma de cubrir a todas las casas no cubiertas entre ei y ei+1, entonces ei+1>=e1+1*.
saludos