Un museo ha la pianta quadrata ed è suddiviso in $ n^2 $ stanze tutte uguali(n>1). Ogni coppia di stanze adiacenti, cioè con un muro in comune, comunica tramite una porta. (Guarda disegno per n=4)
Il guardiano notturno vuole organizzare il suo giro d'ispezione in modo da rispettare le seguenti regole: il guardiano parte da una certa stanza, dove rimane per un minuto, terminati il quale si sposta in una stanza adiacente, dove rimane per un altro minuto; il percorso prosegue collegando stanze adiacenti, in ognuna delle quali il guardiano rimane sempre esattamente un minuto prima di spostarsi. E' consentito ripassare più volte dalla stessa stanza, ma al termine del percorso (che non si trova necessariamente nella stanza d'inizio) il guardiano deve essere stato in ognuna delle $ n^2 $ stanze per esattamente k minuti.
Dire per quali n e k valgono le regole esposte.
Un guardiano molto preciso
Un guardiano molto preciso
- Allegati
-
- Schermata 04-2456026 alle 13.07.41.png (6.54 KiB) Visto 1315 volte
$ 2^{43 112 609} - 1 $
Re: Un guardiano molto preciso
per $ n = 2m $ va bene per ogni $ k $
per $ n = 2m + 1 $ va bene solo per $ k = 1 $
provo a dimostrarlo, se coloro a scacchiera la pianta dell'edificio trovo che per $ n $ pari il numero di bianco è uguale al numero di nero e siccome la mia guardia si muove da un bianco a un nero e viceversa alla fine può riuscire a entrare in ogni stanza, se $ n $ è dispari trovo che il colore che ho scelto per gli angoli è maggiore di 1 del colore degli altri, a questo punto devo trovare un sistema che dimostri che il primo giro può sempre farlo mentre gli altri sono impossibili, io faccio così, il guardiano in 2 minuti si muove di due stanze una bianca e una nera, allora se prendo tanti bastoncini grandi 2 stanze e li appoggio tutti all'interno della scacchiera mi accorgo che non ce la faccio a ricoprire l'intera scacchiera a meno che non sovrappongo su una stanza (una stanza con 2 mezzi bastoncini) ma, il primo giro è un giro diverso, posso vederlo in questo modo, il guardiano è fuori dall'edificio e poi entra. quindi un bastoncino (il primo) è per metà fuori e per metà dentro e se la prima stanza è del colore che si trova in quantità maggiore allora il guardiano ce la farà.
per $ n = 2m + 1 $ va bene solo per $ k = 1 $
provo a dimostrarlo, se coloro a scacchiera la pianta dell'edificio trovo che per $ n $ pari il numero di bianco è uguale al numero di nero e siccome la mia guardia si muove da un bianco a un nero e viceversa alla fine può riuscire a entrare in ogni stanza, se $ n $ è dispari trovo che il colore che ho scelto per gli angoli è maggiore di 1 del colore degli altri, a questo punto devo trovare un sistema che dimostri che il primo giro può sempre farlo mentre gli altri sono impossibili, io faccio così, il guardiano in 2 minuti si muove di due stanze una bianca e una nera, allora se prendo tanti bastoncini grandi 2 stanze e li appoggio tutti all'interno della scacchiera mi accorgo che non ce la faccio a ricoprire l'intera scacchiera a meno che non sovrappongo su una stanza (una stanza con 2 mezzi bastoncini) ma, il primo giro è un giro diverso, posso vederlo in questo modo, il guardiano è fuori dall'edificio e poi entra. quindi un bastoncino (il primo) è per metà fuori e per metà dentro e se la prima stanza è del colore che si trova in quantità maggiore allora il guardiano ce la farà.