Problema gare a squadre Parma 2012

[simone256]

Ciao a tutti... Sto cercando di risolvere il problema 19 di questa gara:
-In un isola ci sono 10000 abitanti tra cavalieri (dicono il vero) e furfanti (dicono il falso)
-Vengono fatte delle domande a 5 persone di cui è ignota l'identità sul numero dei furfanti nell' isola, ricevendo tali risposte:
il numero dei furfanti diviso per 56 dà come resto 19
il numero dei furfanti diviso per 132 dà come resto 23
il numero dei furfanti diviso per 105 dà come resto 13
il numero dei furfanti diviso per 162 dà come resto 17
il numero dei furfanti diviso per 156 dà come resto 37
-Le informazioni date dai cavalieri permettono di stabilire la risposta in modo unico

Ho diviso ogni affermazione in un sistema di congruenze per determinare eventuali contrapposizioni... A metà del problema però mi sono fermato pensando perchè data una congruenza si possa scomporla in 2 congruenze con modulo uguale a fattori che costituivano il modulo iniziale mentre se il modulo è una potenza di un numero primo non si può farlo!
Mi spiego con un esempio:

x congr 19 (mod 56) =>

....x congr 19 (mod 7)
=>
....x congr 19 (mod 8 )

.................................x congr 19 (mod 7)
Che tuttavia è diverso da: x congr 19 (mod 4)
.................................x congr 19 (mod 2)

...Si capisce a intuito che è un passaggio inutile se non "dannoso" perchè nel secondo caso 47 è accettabile mentre non lo è nel primo... Ma perchè allora si può scomporre solo per numeri come 7 e 8?
Qual è l'esatto motivo e qual' è l'esatto discriminante che specifica in che casi si può scomporre la congruenza?
grazie

[Ertool]

Ciao simone, cerco di spiegarti in parole povere. Quando hai un sistema di congruenze mod $ m_1,m_2,...,m_k $ puoi usare il Teorema Cinese solo se per ogni coppia $ \;a\ne b\; $ abbiamo che$ \;m_a,m_b\; $ sono coprimi. Facendo il percorso a ritroso, puoi riscrivere una qualsiasi congruenza come un sistema di congruenze modulo le potenze dei primi che compaiono nella fattorizzazione del modulo, in questo caso $ \;x\equiv19 \;(mod\;56)\; $ diventa

$ x\equiv19\equiv5 \;(mod\;7) $
$ x\equiv19\equiv3\; (mod\;2^3) $

Perchè non puoi dire che $ x\equiv3\:(mod\;2^2)?\;\; $ Beh in realta lo puoi dire e di per sè non è sbagliato, però in questo modo vai ad aumentare il numero delle soluzioni della congruenza. Esempio, $ x\equiv3\;(mod\;8) $ ha soluzioni $ \;x=8k+3\; $ mentre la congruenza modulo 4 ha le soluzioni della forma $ \;x=4k+3 $ che come vedi sono più di quelle modulo 8, quindi è normale che 47 sia accettabile nel secondo caso e non nel primo, hai preso un sistema non equivalente alla congruenza di partenza...

[xXStephXx]

Poi conviene sfruttare anche il fatto che il minimo comune multiplo dei numeri per cui dividi deve essere necessariamente maggiore di $ 5000 $, altrimenti la soluzione non sarebbe unica nell'intervallo $ [0, 10000] $.
Con questa considerazione ti rimangono solo due casi possibili.. Uno è stratosferico, l'altro è più piccolo e verifichi che quello più piccolo va bene.