Quanti rettangoli possono essere realizzati all'interno dei confini di a$5 \times 5$quadrato?

Aug 22 2020

Io e il mio amico stiamo progettando un gioco e stiamo cercando di capire quante mosse possibili ci sono. In questo gioco c'è una griglia 5x5 e il giocatore deve disegnare un rettangolo con dimensioni naturali positive all'interno di quella griglia. Quanti possibili rettangoli si possono disegnare? Ecco un esempio, qualsiasi rettangolo rosso sarebbe una mossa valida (fingi che i rettangoli rossi abbiano dimensioni naturali):

Pensavamo che ogni riga ne avesse 5! larghezze possibili e ogni colonna ne ha 5! altezze possibili e ogni rettangolo può iniziare in una delle 25 posizioni possibili, ma non siamo sicuri di come gestire il fatto che un 2x2 non possa essere disegnato se inizia in tre degli angoli (per esempio).

Risposte

2 AidenChow Aug 22 2020 at 02:12

Puoi fare qualcosa del genere:

Si noti che le due coppie di righe e colonne rappresentano un rettangolo (vale a dire, un quadrato uno per uno). Quindi qualsiasi coppia di linee verticali e linee orizzontali risulterà in un rettangolo unico. Ci sono$\binom62=15$modi per scegliere le linee verticali, e$\binom62=15$modi per scegliere le linee orizzontali. Che dà un totale di$15\cdot15=\boxed{225}$modi per formare un rettangolo.

4 alduan Aug 22 2020 at 02:07

Questo è un classico problema di combinatoria. Pensa a come potresti creare un tale rettangolo. Un rettangolo si forma scegliendo due linee verticali distinte e due linee orizzontali distinte. Questi determinano univocamente un rettangolo.

Ci sono$\binom62=15$modi per scegliere due linee verticali e$\binom62=15$modi per scegliere due linee orizzontali. Poi ci sono$15^2=\boxed{225}$modi in totale.

MarkBennet Aug 22 2020 at 03:33

Ecco un altro modo di pensarci.

Scegli due vertici diagonalmente opposti: il primo può essere arbitrario ($36$possibilità) e la seconda non può trovarsi nella stessa riga o colonna (moltiplicare per$25$possibilità). Quindi ogni rettangolo ha quattro modi possibili per scegliere una diagonale (ogni diagonale può essere scelta in due modi), quindi dividi per$4$ottenere$225$come hanno fatto altri.

È bello vederti pensare al problema. In questi problemi combinatori, fare una scelta attenta su cosa contare e in quale ordine può semplificare le cose. Inoltre, non importa se conti lo stesso oggetto più volte in un semplice calcolo, a condizione che ti ricordi di deduplicare. Questa deduplicazione può far fallire un approccio apparentemente semplice. Ho inserito questo metodo suggerito perché mostra entrambi gli aspetti e rimane abbastanza semplice. A volte offre la migliore via d'uscita.