Olimpiada IMO 2019 Problema C8

Alicia tiene un mapa de Wonderland, un país que consta de $n \geq 2$ ciudades. Para cada par de ciudades, hay una carretera estrecha que va de una ciudad a la otra. Un día, todas las carreteras se declaran de 'una sola vía'. Alicia no tiene información sobre la dirección de las carreteras, pero el Rey de Corazones se ha ofrecido a ayudarla. Se le permite hacerle una serie de preguntas. Para cada pregunta a su vez, Alicia elige un par de ciudades y el Rey de Corazones le dice la dirección de la carretera que conecta esas dos ciudades. Alicia quiere saber si hay al menos una ciudad en Wonderland con como máximo una carretera saliente. Demuestra que siempre puede averiguarlo haciendo como máximo $4n$ preguntas.

25

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados