OliForum Matematico

In una griglia di 4 colonne e 6 righe, 12 dei 24 quadretti devono essere colorati in modo che in ogni riga ci siano 2 quadretti colorati, e in ogni colonna 3. Sia $ N $il numero di griglie colorate in modo diverso che rispettino le limitazioni date. Quanto vale il resto di $ N $diviso $ 1000 $?

Visto che non sono sicuro di aver tradotto giusto, allego il testo originale:

In the $ 6 \times 4 $grid shown, $ 12 $of the $ 24 $squares are to be shaded so that there are two shaded squares in each row and three shaded squares in each column. Let $ N $be the number of shadings with this property. Find the remainder when $ N $is divided by $ 1000 $.

Penso di essere sicuro che la risposta sia

Chiamiamo le colonne A B C D e le righe 1,2,3,4,5,6

Dal momento che per ogni lettera ci stanno al massimo 3 numeri e per ogni numero ci sono 2 lettere, possiamo immaginare di disporre di:

AAA BBB CCC DDD
11 22 33 44 55 66

Il nostro problema ora è abbinare le lettere ai numeri, di modo che ogni gruppo di lettere non colleghino gli stessi numeri e poi togliendo le permutazioni all'interno degli stessi gruppi di lettere ("AAA" "BBB")

Ora creiamoci una nostra tabella

A_ _ _
B_ _ _
C_ _ _
D_ _ _

Il problema ora sta in distribuire i dodici numeri in quegli spazi, di modo che non ci siano due numeri uguali nella stessa riga.

Ora opero una ritirata strategica, trovo tutte le possibilità della tabella sopra, 12!, cerco le disposizioni errate e le tolgo.

Tutti i modi in cui i due numeri possono trovarsi nella stessa riga sono 3 per ogni numero per ogni riga disponibile. Facciamo finta per semplicità che sia solo una la possibilità, dato che se c'è un numeroo ripetuto, non ce ne possono essere altri nella stessa riga.

Dobbiamo quindi ora inserire sei elementi ("11" "22"...) in quattro righe. Sono 6x3 x 5x3 x 4x3 x 3x3, quindi 81x360

Ora faccio 12!-29160, e poi divido 478 972 440 per 1000, ed il resto è 440

440 è la risposta?

Spero di non aver tralasciato nulla all'inizio.

Penso di aver trovato! Edito il messaggio sopra!

OriginalBBB ha scritto:Penso di essere sicuro che la risposta sia

Chiamiamo le colonne A B C D e le righe 1,2,3,4,5,6

Dal momento che per ogni lettera ci stanno al massimo 3 numeri e per ogni numero ci sono 2 lettere, possiamo immaginare di disporre di:

AAA BBB CCC DDD
11 22 33 44 55 66

Il nostro problema ora è abbinare le lettere ai numeri, di modo che ogni gruppo di lettere non colleghino gli stessi numeri e poi togliendo le permutazioni all'interno degli stessi gruppi di lettere ("AAA" "BBB")

Ora creiamoci una nostra tabella

A_ _ _
B_ _ _
C_ _ _
D_ _ _

Il problema ora sta in distribuire i dodici numeri in quegli spazi, di modo che non
ci siano due numeri uguali nella stessa riga.

Ora opero una ritirata strategica, trovo tutte le possibilità della tabella sopra, cerco le disposizioni errate e le tolgo.

Una soluzione un po' diversa è questa:
Tutte le possibilità sono $ \displaystyle \frac {12!}{{2!}^{6}} $ dato che ci sono due 1, due 2,..., due 6

OriginalBBB ha scritto:
Tutti i modi in cui i due numeri possono trovarsi nella stessa riga sono 3 per ogni numero per ogni riga disponibile. Facciamo finta per semplicità che sia solo una la possibilità, dato che se c'è un numeroo ripetuto, non ce ne possono essere altri nella stessa riga.
Dobbiamo quindi ora inserire sei elementi ("11" "22"...) in quattro righe.

Io proporrei di posizionare 4 elementi ("11" "22"...), $ \displaystyle {{6} \choose {4}} $, moltiplichiamo per i modi di disporsi nelle 4 colonne$ \displaystyle {4!} $, e posizioniamo i restanti 4 numeri in $ \displaystyle {\frac {4!}{2!2!}} $ modi. Ah quasi dimenticavo, il tutto per $ \displaystyle {3^4} $

Quindi in totale:
$ \displaystyle \frac {12!}{{2!}^{6}} $ - $ \displaystyle {{6} \choose {4}}\cdot{4!}\cdot \frac {4!}{2!2!}\cdot{3^4} $ = $ 7484400-174960 \equiv 400-960 \equiv -560 \equiv 440 \pmod {1000} $

C'è qualcosa che non mi torna nelle vostre soluzioni... a meno che non abbia capito male il testo.

Un modo "rozzo" per risolvere il problema potrebbe essere quello di sistemare prima due colonne e poi, a seconda dei diversi casi, sistemare le ultime due in modo furbo. Ho diversificato le possibilità e fatto i conti e mi viene un risultato diverso, ma non è questo il punto...

In quanti modi posso colorare tre caselle in una colonna? 20. Immaginiamo di colorare tre caselle a caso in ciascuna colonna: è una cosa stupida da fare, perché contiamo anche i casi in cui non abbiamo due caselle colorate in ogni riga. Però intanto abbiamo un numero sopra il quale sappiamo che la soluzione non può stare. Ma 20^4=160000 è molto più piccolo di 7484400-174960, quindi c'è qualcosa che non torna...

Rileggendo la vostra soluzione, anche se (sarà anche colpa dell'ora) non capisco un paio di calcoli, mi viene il sospetto che, tanto per cominciare, quel 12! sia sbagliato, anche dividendolo per 2^6: avete giustamente tenuto conto del fatto che possiamo invertire due numeri uguali senza che cambi nulla, ma possiamo anche cambiare l'ordine dei numeri associati ad una lettera. Ad esempio, se associamo alla colonna A le righe 1,3,4, questo è equivalente ad associare alla colonna A le righe 4,1,3, ma il vostro calcolo se non ho capito male li considera casi distinti. Non si può neanche semplicemente dividere il numero per (3!)^4, perché a questo punto le coppie di numeri uguali assegnati alla stessa lettera cambiano le carte in tavola.

RedII ha scritto:In quanti modi posso colorare tre caselle in una colonna? 20. Immaginiamo di colorare tre caselle a caso in ciascuna colonna: è una cosa stupida da fare, perché contiamo anche i casi in cui non abbiamo due caselle colorate in ogni riga. Però intanto abbiamo un numero sopra il quale sappiamo che la soluzione non può stare. Ma 20^4=160000 è molto più piccolo di 7484400-174960, quindi c'è qualcosa che non torna...

Infatti, c'è qualcosa che non torna. Il risultato non è 440, pur essendo venuto a due persone diverse in due modi diversi.

RedII ha scritto:quindi c'è qualcosa che non torna...

Iuppiter ha scritto: Infatti, c'è qualcosa che non torna. Il risultato non è 440

Ook, domani appena avrò un po' di tempo, ricontrollerò la soluzione...ora proprio non posso dato che ho ancora circa 100 anni di storia da studiare e domani devo essere interrogato

Eh sì che me l'ero segnato, ma mi sono dimenticatoo di farlo ( Togliere le permmutazioni all'interno delle righe), ma allla luce di ciò ho cambiatoo lla seconda parte del processo, non mi esce ancora giusto (1860?) ma a questoo punto non so proprio perché. Non conoscendo la risposta scomettereii il mio braccio.

Data la tabella abbiamo 12! di dispore 12 segni alll'interno

A_ _ _
B_ _ _
C_ _ _
D_ _ _

Dividiamo per le copie, causate dalle copie di numeri (11 22 ...) [2^6] e dall'equivalenza delle soopracitate permutazioni (123 132 321 231...) all'interno dellla riga [6^4]

Ora le combinazioni invalide non sono più 360 per 3^4, dato che l'ordine dei numeri non conta più (sono già stati eliminati dall 6^4),, ma solo 360.

Quindi la formula risolvete dovrebbbe essere 12!/(2^6 x 6^4) – 360 = 5415

Ora usate la tabella sopra e date i valori più disparati rispettando i limiti presenti nella formula, poi risportata nella griglia 6x4 come fosse batttaglia navale (A2, B1, C4, C5)e vedrete che la tabellla regge, se vale lì, valle anche nellla griglia.

Dunque mi rimetto a voi.

OriginalBBB ha scritto: Data la tabella abbiamo 12! di dispore 12 segni alll'interno
A_ _ _
B_ _ _
C_ _ _
D_ _ _
Dividiamo per le copie, causate dalle copie di numeri (11 22 ...) [2^6] e dall'equivalenza delle soopracitate permutazioni (123 132 321 231...) all'interno dellla riga [6^4]

Secondo me non si può fare semplicemente diviso $ 6^4 $, perchè se ad esempio nella colonna A ci sono 112, le permutazioni a quel punto sono 3, e non più 6 come nel caso 123. Cercare di contare quindi in questo modo è molto più difficile, che fare come ha suggerit RedII

RedII ha scritto: Un modo "rozzo" per risolvere il problema potrebbe essere quello di sistemare prima due colonne e poi, a seconda dei diversi casi, sistemare le ultime due in modo furbo.

Scusa se ti rubo l'idea

Vediamo un po' se stavolta esce:
le possibilità per le prime 2 colonne sono 4:
A 123 123 123 123
B 123 124 145 456
nel senso che data la prima colonna 123, ci sono 4 diverse possibilità per la seconda: tutti uguali, 2 uguali, 1 uguale, 0 uguali alla prima

nel caso A123 B123 per la 3° e 4° colonna la scelta è obbligata: C456 D456

nel caso A123 B124 le scelte sono 2: C356 D456 ... 5 e 6obbligati,3 e 4 si cambiano di posto

nel caso A123 B145 le scelte sono 6: C236 D456 ... 6 obbligato, 2,3,4 e 5 si cambiano di posto

nel caso A123 B456 le scelte sono 20: C123 D456 ... scegliere 3 numeri fra 6 che vanno in C

quindi le possibilità sono:
$ {6 \choose 3}+{6 \choose 3}\cdot3\cdot3\cdot2+{6 \choose 3}\cdot3\cdot{3 \choose 2}\cdot6+{6 \choose 3}\cdot20=20+360+1080+400=1860 $

Almeno ora spero sia giusto

Giusto...bravo, hai trovato la soluzione.