Scacchiera e torri

[mitchan88]

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

[edriv]

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.

[exodd]

se non ho capito male, riassumendo, hai detto che basta mettere una torre in ogni casella nera, vero?

[edriv]

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]

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!

[mattilgale]

LOOOL

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} $

[mitchan88]

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
La condizione oltre che necessaria è anche ovviamente sufficiente (basta posizionare le torri "alfieramente" partendo da un angolo)

[mattilgale]

bella soluzione

[ipparco]

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]

Stesso ragionamento per me, ma senza assurdo:

Siano le torri degli uno in una matrice quadrata nxn:



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 $.