Scacchiera e torri

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
mitchan88
Messaggi: 469
Iscritto il: 01 gen 1970, 01:00
Contatta:

Scacchiera e torri

Messaggio da mitchan88 » 09 ago 2007, 15:14

Su una scacchiera nxn sono posizionate delle torri in modo che, per ogni casella vuota, ci siano almeno n torri sommando quelle della riga e della colonna che contengono tale casella. Dimostrare che vi sono almeno n²/2 torri

Dall'engel :P
[url:197k8v9e]http://antrodimitch.wordpress.com[/url:197k8v9e]

Membro del fan club di Ippo_

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 09 ago 2007, 20:01

Wow forse ho trovato una soluzione molto bella!
D'ora in poi le torri si chiamano quadratini neri e gli altri quadratini sono invece bianchi.

Data una casella q, dove q sta per qualsiasi (bianca o nera), definiamo f(q) come la somma delle caselle con colore diverso dal suo che stanno sulla sua riga o sulla sua colonna.

Inoltre definiamo g(Q), dove Q sta per tutto il Quadratone, come la somma, su tutti i quadratini bianchi b, di f(b).

La cosa bella è che la funzione g è "simmetrica", cioè è uguale alla somma su tutti i quadratini neri n di f(n)!!
Infatti, prendiamo una riga. Ogni quadratino nero sulla riga, nel calcolo di g, è contato (come quadratino di colore diverso e sulla stessa riga) tante volte quanti sono i bianchi sulla riga. Lo stesso per le colonne. Concludiamo che:
g(Q) = (somma su ogni colonna di (quadratini neri nella colonna * quadratini bianchi nella colonna)) + (somma su ogni riga di (quadratini neri nella riga * quadratini bianchi nella riga)).

Ora, poichè la moltiplicazione è commutativa, è chiaro che la funzione g non cambia se invertiamo il colore di ogni quadratino, da cui l'affermazione di sopra è vera.

Inoltre, per ogni riga (o colonna), essendo bianchi + neri = n, otteniamo che:
bianchi * neri = $ \displaystyle \frac 14 \left( n \right)^2 - \frac 14 (\mbox{bianchi - neri})^2 $ (verificate pure... )

Essendo le colonne n e le righe n, otteniamo che:
$ \displaystyle g(Q) = \frac 12 n^3 - \frac 14 \left(\sum_{\mbox{righe}} (\mbox{bianchi} - \mbox{neri})^2 + \sum_{\mbox{colonne}} (\mbox{bianchi} - \mbox{neri})^2\right) $
dove bianchi, neri stanno per il numero di quad. bianchi,neri su quella riga o colonna.

Ho già dimostrato più di quanto serve per concludere. L'ipotesi dice che per ogni bianco b, $ \displaystyle f(b) \ge n $, quindi la somma sui quadratini bianchi b di f(b) è maggiore o uguale di bianchi totali * n.
Quindi $ \displaystyle g(Q) \ge \mbox{bianchi}\cdot n $.
D'altra parte, dalla formula scritta prima segue immediatamente che g(Q) è minore o uguale di $ \displaystyle \frac 12 n^3 $, che possiamo riscrivere come
$ \displaystyle n\frac{\mbox{bianchi + neri}}2 \ge g(Q) $.
Combinando le due disuguaglianze, otteniamo:
$ \displaystyle \frac{\mbox{bianchi + neri}}2 \ge \mbox{bianchi} $
Ovvero $ \displaystyle \mbox{neri} \ge \mbox{bianchi} $, che è la tesi.

Credo che non ci siano grandi problemi a generalizzare questa dimostrazione a k dimensioni.

Avatar utente
exodd
Messaggi: 728
Iscritto il: 09 mar 2007, 19:46
Località: sulle pendici della provincia più alta d'europa

Messaggio da exodd » 10 ago 2007, 10:01

se non ho capito male, riassumendo, hai detto che basta mettere una torre in ogni casella nera, vero?
Tutto è possibile: L'impossibile richiede solo più tempo
julio14 ha scritto: jordan è in realtà l'origine e il fine di tutti i mali in $ \mathbb{N} $
EvaristeG ha scritto:Quindi la logica non ci capisce un'allegra e convergente mazza.
ispiratore del BTA

in geometry, angles are angels

"la traslazione non è altro che un'omotetia di centro infinito e k... molto strano"

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 10 ago 2007, 10:34

Non ti pare che se bastasse scrivere solo quello avrei scritto solo quello invece che la schifezza la sopra? :? Mi sa che hai capito male.

darkcrystal
Messaggi: 699
Iscritto il: 14 set 2005, 11:39
Località: Chiavari

Messaggio da darkcrystal » 10 ago 2007, 14:51

Questa dimostrazione (ammesso che funzioni) forse è un po' più semplice...
Diciamo che sulla riga o colonna che contiene meno torri ci siano t torri e che su tutta la scacchiera ci siano T torri.
Allora prendendo la riga (o colonna, ma non lo riscriverò più per semplicità) che contiene t torri abbiamo (n-t) caselle vuote, corrispondenti a (n-t) colonne ognuna delle quali deve contenere almeno (n-t) torri, di modo che la somma delle torri su riga e colonna faccia almeno n (il che è l'ipotesi).
Allora abbiamo in (n-t) colonne almeno (n-t)^2 torri; il che vuol dire che restano da distribuire su t colonne al massimo $ T-(n-t)^2 $ torri.
Siccome t è il minimo delle torri su una colonna, si deve avere $ \lfloor \frac{T-(n-t)^2}{t} \rfloor \geq t \rightarrow \frac{T-n^2}{t} \geq 2(t-n) \rightarrow T \geq n^2+2t^2-2tn $. Supponiamo ora per assurdo che sia $ T < \frac{n^2}{2} $. Otteniamo quindi $ n^2/2 > n^2+2t^2-2tn \leftrightarrow (\frac{n}{2}-t)^2 < 0 $ che mi sembra improbabile.

Ciao!
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein

Membro dell'EATO

Avatar utente
mattilgale
Messaggi: 372
Iscritto il: 01 gen 1970, 01:00
Località: Lucca
Contatta:

Messaggio da mattilgale » 10 ago 2007, 15:25

LOOOL :D :P

questa è una versione leggermente modificata di IMO1971/6
ecco la mia soluzione

ad ogni riga e colonna associamo un numero pari al numero di torri su quella riga o su quella colonna.

chiamiamo$ r_1,r_2,\dots $ le righe

ad ogni riga $ r_i $associamo una colonna $ c_i $ diversa da $ c_{i-1},\dots,c_1 $ nel seguente modo:

supponiamo di aver già scelto $ c_i\ \forall i\leq k $ e di dover scegliere $ c_{k+1} $

se esiste sulla riga una casella vuota che non appartiene a$ c_i\ \forall i\leq k $ allora $ c_{k+1} $ sarà la colonna che contiene quella casella, se non esiste una tale casella chiamiamo t il numero di $ r_{k+1} $ ponendo n>t. Allora $ n>t\geq n-k $ infatti se fosse t<n-k avremmo almeno k+1 caselle vuote su$ r_{k+1} $ e quindi almeno una casella vuota che non appartiene a nessuna delle $ c_i $ con $ i\leq k $. poniamo t=n-k+x

Adesso consideriamo una qualsiasi colonna non ancora scelta con numero s, se $ t+s\geq n $ allora tale colonna sarà $ c_{k+1} $, altrimenti avremo che $ s<n-t=k-x $quindi sulla colonna ci sono almeno n-k+x+1 caselle vuote, consideriamo adesso le intersezioni della colonna scelta con $ r_i $ per ogni$ i\leq k $, vedremo che esse sono esattamente k e quindi almeno x+1 di queste saranno vuote. Consideriamo le righe a cui appartengono queste x+1, supponiamo che una di queste x+1 appartenga a $ r_g $, se l'intersezione di $ c_g $con $ c_{k+1} $ è vuota allora $ c_g\rightarrow c_{k+1} $ e la colonna che avevamo scelto diventa $ c_g $, se non esiste una tale g allora le caselle piene su $ r_{k+1} $ sono $ n-k+x=t\geq n-k+x+1 $ assurdo.
Pertanto possiamo sempre fare in modo che r_i+c_i\geq n e quindi

$ \displaystyle \mbox{numero torri}=\frac{1}{2}\sum_{i=1}^n|r_i|+|c_i|\geq\frac{n^2}{2} $
"la matematica è il linguaggio con cui Dio ha plasmato l'universo"

Galileo Galilei

Avatar utente
mitchan88
Messaggi: 469
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da mitchan88 » 10 ago 2007, 15:28

Ok la mia soluzione è all'incirca quella di darkcrystal... prendiamo una colonna con t torri: su questa ci saranno n-t buchi, per cui contando le righe di quedti buchi ci saranno almeno (n-t)² torri. Considerando invece le righe contenenti le t torri della colonna scelta, in ognuna di queste ci saranno almeno t torri (per come è stato definito t), per cui in totale ne avremo almeno (n-t)²+t², che è il risultato di darkcrystal sotto mentite spoglie :P
La condizione oltre che necessaria è anche ovviamente sufficiente (basta posizionare le torri "alfieramente" partendo da un angolo)
Ultima modifica di mitchan88 il 10 ago 2007, 15:50, modificato 2 volte in totale.
[url:197k8v9e]http://antrodimitch.wordpress.com[/url:197k8v9e]

Membro del fan club di Ippo_

Avatar utente
mattilgale
Messaggi: 372
Iscritto il: 01 gen 1970, 01:00
Località: Lucca
Contatta:

Messaggio da mattilgale » 10 ago 2007, 15:29

bella soluzione :!:
"la matematica è il linguaggio con cui Dio ha plasmato l'universo"

Galileo Galilei

Avatar utente
ipparco
Messaggi: 58
Iscritto il: 24 gen 2007, 10:44
Località: Verona

Messaggio da ipparco » 13 ago 2007, 16:01

Propongo la mia soluzione.
Supponiamo che sulla scacchiera ci siano meno di $ \frac{n^2}{2} $ torri; questo vuol dire che ci sono più caselle vuote che occupate. Una riga della scacchiera, presenterà quindi in media più caselle vuote che occupate, così in media le caselle vuote avranno meno di $ \frac{n}{2} $ torri in orizzontale. Analogo ragionamento si può fare per le colonne. Sommando le medie, si avrà che le caselle vuote, in media, sono "tenute in scacco" da meno di n torri. Da questo consegue che deve esserci almeno una casella vuota con meno di n torri.

TADW_Elessar
Messaggi: 145
Iscritto il: 21 mag 2006, 00:18
Contatta:

Messaggio da TADW_Elessar » 13 ago 2007, 17:48

Stesso ragionamento per me, ma senza assurdo:

Siano le torri degli uno in una matrice quadrata nxn:

Immagine

Il testo dice che presa una qualsiasi casella $ ~a_{\alpha\beta} $ si ha:
$ \displaystyle \sum_{j=1}^n a_{\alpha j} + \sum_{i=1}^n a_{i\beta} \geq n $

Ovvero, dividendo per 2n, la media aritmetica di una "croce" (riga più colonna) di "centro" $ ~\alpha,\beta $ è $ ~\geq 1/2 $.

La media aritmetica di queste n medie aritmetiche sarà ovviamente $ ~\geq 1/2 $. E quest'operazione equivale a calcolare:

$ \displaystyle \frac{1}{n^2} \left\{\sum_{i=1}^n\sum_{j=1}^n a_{ij}\right\} \geq \frac 1 2 \qquad \qquad \Box $.

Rispondi