Problema 8 · L'ascensor estrany
Estratègia en el pitjor cas: comptar viatges imprescindibles.
Resposta entera de 4 xifres com a màximEn un hotel de 20 plantes els 10 primers pisos són de color verd, de l'onzè al vintè són vermells. L'hotel no té escales i per canviar de pis només es pot utilitzar un ascensor estrany que es comporta de la manera següent: qui entra a l'ascensor en un pis verd anirà a la planta que demana. Qui entra a l'ascensor en un pis de color vermell anirà a un pis del mateix color que el que selecciona, però no necessàriament en el pis seleccionat; en qualsevol cas, l'ascensor canvia de planta. Sigui quin sigui el pis, si demanem l'ascensor, hi arribarà lliure. Una persona ha de visitar tots els pisos, començant pel primer i tornant de nou al primer. Si l'ascensor es comporta en el pitjor dels casos, quin és el nombre mínim de viatges, viatjant dins de l'ascensor, que haurà de fer per aconseguir l'objectiu?
Solució raonada
Idea clau: des d'un pis verd controlem perfectament la destinació; des d'un pis vermell només controlem el color de la destinació.
Els viatges imprescindibles. Cada pis vermell només es pot garantir entrant-hi des d'un pis verd (des d'un vermell, l'ascensor tria). Calen, doncs, $10$ viatges verd → vermell, i després de cadascun cal sortir-ne: $10$ viatges més vermell → verd (demanant un pis verd; aterrem en algun verd). Ja en portem $20$.
Els pisos verds. En el pitjor cas, totes les sortides dels pisos vermells ens deixen al pis $1$ (o en verds ja visitats): cap regal. Ens queden $9$ pisos verds per visitar ($2$ a $10$), i des d'un verd hi anem amb un viatge exacte cadascun: $9$ viatges més. La tornada final al pis $1$ no costa cap viatge extra: ordenem el recorregut perquè l'última sortida d'un pis vermell (que en el pitjor cas ens duu al pis $1$, l'únic «càstig» que l'adversari repeteix) sigui el final del trajecte — i si l'adversari ens deixa en un altre verd, és que aquell verd ens l'ha regalat abans, estalviant-nos un viatge que ara gastem per tornar a l'$1$.