Disporre i numeri da 1 a 30

[milizia96]

Questo l'ho trovato difficile:

Sia $N$ il numero di modi diversi in cui si possono inserire i numeri interi da 1 a 30 nella seguente tabella:

in modo che ogni casella contenga un numero diverso e che il numero contenuto in ciascuna casella sia maggiore sia di quello che gli sta immediatamente a sinistra sia di quello che gli sta sotto.
Dire quanto vale $N/{29*23*7}$

Premetto che non l'ho risolto personalmente, ma posseggo la soluzione.

[marco99991]

Perchè $N/(29*23*7)$ e non N? Può essere d'aiuto questo forse?

[marco99991]

In pratica bisogna determinare il numero di modi in cui posso scegliere 12 numeri interi diversi compresi tra 1 e 30 (da mettere nella riga in alto) sapendo che il primo numero deve essere maggiore o uguale a 2, il secondo maggiore o uguale a 4, ..., il dodicesimo maggiore o uguale a 24. Gli altri 18 numeri li piazzo nella riga sottostante in ordine crescente da sinistra verso destra. Il conto è un po' complesso, ci devo pensare un attimino...

naturalmente i 12 numeri devono essere scritti in ordine crescente

[milizia96]

"marco9999":Perchè $N/(29*23*7)$ e non N? Può essere d'aiuto questo forse?

Ho preso l'esercizio da una gara a squadre. In questo tipo di gara la risposta è sempre un intero compreso tra 0000 e 9999: se non chiedesse di dividere per $29*23*7$ il risultato sarebbe troppo grande e supererebbe il limite delle quattro cifre.

[marco99991]

Ho capito. In ogni caso non mi aiuta molto visto che avevo già la sensazione che il numero da trovare fosse abbastanza piccolo. Sto cercando di fare conti con pochi numeri per provare poi a generalizzare nel caso di 30 numeri. In ogni caso, basta il risultato e non il procedimento in quel tipo di gara, no?

[milizia96]

Certamente: nella gara a squadre basta il risultato.
Però qui gradirei se possibile anche il ragionamento

Comunque il numero da trovare non è affatto piccolo.

[marco99991]

Sì, è vero. Avevo fatto dei conti molto approssimativi. E' tosto questo problema, sarebbe bello che qualche altro utente provasse a dare qualche idea. Comunque tu hai solo la soluzione o anche la spiegazione?

[milizia96]

Pensa che questo problema è stato proposto in una gara online il mese scorso a cui parteciparono 81 squadre da tutta Italia, ma nessuno consegnò la risposta corretta...

"marco9999":Comunque tu hai solo la soluzione o anche la spiegazione?

Anche la spiegazione.

[marco99991]

Ah però, nessuno è arrivato alla soluzione...proprio facile questo problema Comunque ho provato di tutto ma non riesco a trovare il risultato. L'idea ce l'ho, e l'ho anche scritta, ma più di così non riesco. Scommetto che ci sarà una dimostrazione tanto semplice quanto elegante, e che prende una strada diversa dalla mia. Non è che magari potresti darmi un hint?

[milizia96]

E va bene...

Immagina di riempire la tabella un numero alla volta, mettendo prima 1, poi 2 ecc.
Ovviamente riempirai le due righe a partire da sinistra: è lì che si devono trovare i valori più bassi.
Indicando ad esempio con A e B rispettivamente la riga superiore e la riga inferiore, possiamo scrivere tante stringhe, ognuna delle quali è composta da 12 'A' e 18 'B' e individua univocamente un modo di riempire la tabella: leggendo da sinistra verso destra una stringa, quando incontriamo 'A' inseriamo il numero successivo nella riga sopra, se incontriamo 'B' inseriamo il numero nella riga sotto.
Viceversa, una tabella già riempita individua una sola stringa di quel tipo.

Quindi un problema equivalente a quello originale potrebbe essere quello di contare quante sono le stringhe che individuano configurazioni "corrette" nella tabella.

Vedi un po' se vedendo il problema in questo modo riesci a cavarne qualcosa...

[marco99991]

Sì, avevo già pensato a questa possibilità. Il problema è che comunque non so come contare queste stringhe. Non è semplice, ci penserò ancora, grazie

[xXStephXx]

Non ho la soluzione, scusate dunque per l'OT, ma son curioso.. Questo problema è tratto dalla gara a squadre di Tor Vergata.. Era proprio l'ultimo problema E non sono sicuro, ma credo che a giudicare dal valore a cui era arrivato alla fine direi che è rimasto irrisolto anche da noi! Mi hanno detto che successivamente lo stesso testo è stato usato per un'altra gara a squadre.. Siccome sul sito di tor vergata non hanno ancora pubblicato i testi, e dopo aver fatto la gara non ho più avuto modo di reperire i testi con le soluzioni, qualcuno (milizia ) sa per caso se questi testi sono stati pubblicati da qualche parte?

[milizia96]

Ho cercato anch'io, ma purtroppo non ho trovato né testi né soluzioni su internet.
Ho solamente il foglio dei quesiti che mi consegnarono durante la gara a squadre online.

[milizia96]

Siccome nessuno si fa avanti faccio un passo in più:

Supponiamo che leggendo la stringa, a un certo punto abbiamo letto più A che B: ciò significa che abbiamo inserito più numeri nella riga superiore: sotto alcuni di questi c'è ancora una casella vuota. Ma queste caselle vuote saranno riempite necessariamente da numeri maggiori rispetto a quelli nella riga sovrastante, e ciò contraddice le ipotesi del problema.

Invece le stringhe in cui man mano che si legge da sinistra verso destra si incontra un numero di B maggiore o uguale al numero di A, rispettano tutte le condizioni imposte: le stringhe da contare sono proprio queste.

[milizia96]

Un altro passo:

Potrebbe essere d'aiuto lavorare sul piano cartesiano, mettendo $A$ sull'asse delle x e $B$ sull'asse delle y.
Inizialmente abbiamo 0 A e 0 B: il punto individuato è $(0,0)$
Man mano che leggiamo una lettera della stringa, il nostro punto si sposterà di 1 unità a destra oppure in alto. Alla fine coinciderà con $(12,18)$
Abbiamo detto che il numero di $B$ deve rimanere sempre maggiore o uguale al numero di $A$. Ciò significa che il "tragitto" che il nostro punto compie sul piano cartesiano non deve mai incrociare la bisettrice del 1° quadrante (ma può eventualmente "toccarla" senza oltrepassarla).
Resta quindi da determinare il numero di percorsi che godono di queste proprietà.

[FreddyKruger]

Dopo una marea di conti mi è venuto fuori

3120

E' corretto?

[milizia96]

Caspita, questo problema l'avevo proprio dimenticato!
Comunque mi dispiace deluderti, ma la soluzione dovrebbe essere un'altra
che metto in spoiler

6825

Però il risultato esce fuori da due conti che ho improvvisato adesso, perché purtroppo ho perso il foglio dove avevo scritto la soluzione Quindi potrei anche sbagliarmi.

Continuo con un altro suggerimento che continua il discorso di 6 mesi fa:

Il percorso non deve oltrepassare la bisettrice del primo quadrante: ciò equivale a dire che NON può SFIORARE la retta parallela alla suddetta bisettrice passante per $(1,0)$.
(sembra un'osservazione banale, ma vi assicuro che guardandolo così il problema è molto più facile da risolvere!)
Si può continuare calcolando TUTTI i percorsi che vanno da $(0,0)$ a $(12,18)$ (cosa facile) e poi sottrarre quelli che toccano questa retta (un po' meno facile ma fattibile soprattutto se viene un'intuizione particolare...).

Sono necessari un bel po' di conti solo se si calcolano a mano i fattoriali che vengono fuori... altrimenti con la calcolatrice si fa in un attimo.

[FreddyKruger]

Io avevo usato molta forza bruta,disegnando un rettangolo 12x18 e levando la metà in alto del quadrato iniziale 12x12 (spero che si capisca ciò che ho detto ) da qui ho contato ogni casella considerando il fatto che il numero da scrivere in ognuna è la somma della casella immediatamente a sinistra+la casella immediatamente in basso.
Quando mi è venuto un numero divisibile per 29,23 e 7 ho fatto salti di gioia

[FreddyKruger]

La differenza è che io ho contato i percorsi da (0,0) a (18,12) e non (12,18)

[Umby2]

Si potrebbe usare anche il triangolo di Catalan, che porta i seguenti risultati:

742900 1931540 4345965 8947575 17298645 31865925 56448210 96768360 161280600 262256280 417225900 650872404 ......

il primo numero 742.900 rappresenta il 12+13 (12 prima linea e 13 la seconda, quindi su 25 numeri)
il secondo numero 1.931.540 rappresenta il 12+14 (quindi su 26 numeri..)
...
...
...
il sesto numero 31.865.925 si tratta della ns. condizione (12+18 = 30 numeri)

[FreddyKruger]

Umby,potresti specificare meglio il procedimento che usa il triangolo di catalan? E in ogni caso qualcuno potrebbe dirmi dov'è l'errore nel mio ragionamento? Grazie mille