Altro vecchio cesenatico

[ale.G]

E' data una "scacchiera infinita", la cui righe e le cui colonne sono numerate con i numeri positivi. In ogni casella della scacchiera si può collocare al più un gettone(si hanno a disposizione infiniti gettoni).

sono date due successioni $a_1,a_2...$ e $b_1,b_2...$ di numeri interi positivi.Dimostrare che si possono disporre i gettoni sulla scacchiera in modo che vi siano $a_1$ gettoni sulla prima riga,$a_2$ sulla seconda...,$b_1$ gettoni sulla prima colonna,$b_2$ gettoni sulla seconda colonna...

[exodd]

hint

Testo nascosto:

basta ordinarli..

[ale.G]

Bah, quando ho letto questo problema mi è sembrato estremamente facile (per questo mi sono venuti molti dubbi)...anche il numero 3 di cesenatico di quest'anno mi era sembrato facile,ma mi hanno dato 0 punti .
La mia idea è questa: data una qualsiasi successione numerica si possono disporre i gettoni considerando in primo momento solo le righe(o le colonne) e facendo in modo di rispettare le condizioni anche per le colonne(o righe).
mi spiego meglio: se entrambe le successioni sono $1,2,3...n$ allora si prendono inizialmente in considerazione le colonne.
ne devo mettere uno sulla prima e quindi lo posso porre nella casella $(1,1)$.
Due gettoni per la seconda colonna: nella prima riga non ci va più nulla, quindi poniamo i gettoni nelle caselle $(2,2)$ e $(3,2)$.
Tre gettoni per la terza: caselle$(2,3)$$(3,3)$$(4,3)$, e così via...


Il fatto è che non sono convinto che questo tipo di soluzione vada bene ai correttori, perchè mi sembra un po' troppo poco...

[ileo83]

la tua strategia e' una specie di tris?

[ale.G]

Mah,puoi chiamarlo tris, se vuoi, però è estremamente banale, e proprio per questo penso che manchi qualcosa,o addirittura che sia proprio errata, tu come l'avresti fatto?

[exodd]

Bah, quando ho letto questo problema mi è sembrato estremamente facile (per questo mi sono venuti molti dubbi)...anche il numero 3 di cesenatico di quest'anno mi era sembrato facile,ma mi hanno dato 0 punti .
La mia idea è questa: data una qualsiasi successione numerica si possono disporre i gettoni considerando in primo momento solo le righe(o le colonne) e facendo in modo di rispettare le condizioni anche per le colonne(o righe).
mi spiego meglio: se entrambe le successioni sono $1,2,3...n$ allora si prendono inizialmente in considerazione le colonne.
ne devo mettere uno sulla prima e quindi lo posso porre nella casella $(1,1)$.
Due gettoni per la seconda colonna: nella prima riga non ci va più nulla, quindi poniamo i gettoni nelle caselle $(2,2)$ e $(3,2)$.
Tre gettoni per la terza: caselle$(2,3)$$(3,3)$$(4,3)$, e così via...


Il fatto è che non sono convinto che questo tipo di soluzione vada bene ai correttori, perchè mi sembra un po' troppo poco...

Uhm.. Considera le colonne così: 1,2,2,2,...
e le righe così: 3,1....
Se comnci a sistemare le colonne, vedi immediatamente che qualcosa non va..

[ileo83]

io avrei fatto, appunto, una specie di tris.

[ale.G]

Bah, quando ho letto questo problema mi è sembrato estremamente facile (per questo mi sono venuti molti dubbi)...anche il numero 3 di cesenatico di quest'anno mi era sembrato facile,ma mi hanno dato 0 punti .
La mia idea è questa: data una qualsiasi successione numerica si possono disporre i gettoni considerando in primo momento solo le righe(o le colonne) e facendo in modo di rispettare le condizioni anche per le colonne(o righe).
mi spiego meglio: se entrambe le successioni sono $1,2,3...n$ allora si prendono inizialmente in considerazione le colonne.
ne devo mettere uno sulla prima e quindi lo posso porre nella casella $(1,1)$.
Due gettoni per la seconda colonna: nella prima riga non ci va più nulla, quindi poniamo i gettoni nelle caselle $(2,2)$ e $(3,2)$.
Tre gettoni per la terza: caselle$(2,3)$$(3,3)$$(4,3)$, e così via...


Il fatto è che non sono convinto che questo tipo di soluzione vada bene ai correttori, perchè mi sembra un po' troppo poco...

Uhm.. Considera le colonne così: 1,2,2,2,...
e le righe così: 3,1....
Se comnci a sistemare le colonne, vedi immediatamente che qualcosa non va..

Ehm...in realtà penso di non aver capito molto bene cosa intendi
Mi stai dicendo di disporre 1 gettone sulla prima colonna e due su tutte le altre, e contemporaneamente 3 sulla prima riga,1 sulla seconda e 2 su tutte le altre?
In questo modo si può fare mettendo 3 gettoni in fila sulla prima riga a partire dalla casella $(1,1)$, poi un gettone sulla casella $(2,2)$.
Poi se ne mette uno sulla casella $(2,3)$ e da quella in poi si mette alternandoli uno nella casella a destra e uno in quella sotto al precedente.
Ma sono sicuro che non intendevi questo...

[paga92aren]

@exodd non credo sia necessario ordinarli...

@ale la tua non è una soluzione. Potrebbe essere un'idea se espressa meglio. Per fare una dimostrazione basta creare un'algoritmo che per ogni successione ti permetta di disporre i gettoni.

Propongo la mia soluzione: oltre ai gettoni mi procuro infiniti zeri.
1) prendo la prima riga $j$ non ancora sistemata, deve contenere $a_j$ gettoni. Sistemo gli $a_j$ gettoni nelle prime $a_j$ caselle libere e degli zeri nel resto della riga. Poi se per caso una colonna $i$ ha $b_i$ gettoni la completo con gli zeri.
Ripeto il procedimento per ogni riga e ho completato la scacchiera. Per ogni riga non ancora sistemata ci sono infinite caselle vuote quindi è sempre possibile eseguire il procedimento.

[ale.G]

. Poi se per caso una colonna $i$ ha $b_i$ gettoni la completo con gli zeri.
Ripeto il procedimento per ogni riga e ho completato la scacchiera. Per ogni riga non ancora sistemata ci sono infinite caselle vuote quindi è sempre possibile eseguire il procedimento.

Scusami ma questa due affermazioni proprio non le ho capite

[paga92aren]

Io riempio riga per riga tutta la scacchiera. Per evitare di riempire troppo una colonna, quando ha abbastanza gettoni completo la colonna con gli zeri.
Spero di essere stato più chiaro.

Con l'altra frase volevo motivare il fatto che è sempre possibile eseguire il procedimento 1. Ciò è abbastanza intuitivo.
L'unico punto che potrebbe essere non eseguibile è quando dico di riempire $a_j$ caselle con gettoni. Questo perché non è detto che ci siano $a_j$ caselle libere su quella riga, ma la riga è infinita quindi non ci sono problemi.

[ale.G]

Chiarissimo grazie mille

[Tess]

Volendo ho qua un modo, secondo me, più veloce.
Prendo la prima casella (1,1) e scelgo l'intero più piccolo tra $ r_1 $ e $ c_1 $ (che sono i gettoni che devono andare in quelli righe\colonne) e ci metto questi gettoni sulla casella.
Ora mi dimentico della riga o colonna che ho sistemato e passo a riempire la prima casella in alto a sinistra con lo stesso procedimento (al secondo passaggio potrebbe essere (1,2),(2,1),(2,2) a secondache fosse $ c_1>r_1,r_1>c_1,r_1=c_1 $. Ovviamente sull'altra colonna\riga ho già usato alcuni dei gettoni disponibili. E vado avanti così...

[Drago96]

Volendo ho qua un modo, secondo me, più veloce.
Prendo la prima casella (1,1) e scelgo l'intero più piccolo tra $ r_1 $ e $ c_1 $ (che sono i gettoni che devono andare in quelli righe\colonne) e ci metto questi gettoni sulla casella.

In ogni casella ci va al massimo un gettone...