OliForum Matematico

Un numero naturale $k$ si dice $n$-squadrato se, colorando comunque con n colori diversi le caselle di una scacchiera $2n × k$, esistono 4 caselle distinte dello stesso colore i cui centri sono vertici di un rettangolo avente i lati paralleli ai lati della scacchiera.
Determinare, in funzione di $n$, il più piccolo naturale $k$ che sia $n$-squadrato.



Allora,considero la scacchiera di base $k$ e di altezza $2n$. Per ora do per buono che il caso "migliore" che mi permette di trovare il giusto $k$ sia quello in cui in ogni colonna assegno due caselle ad ogni colore( non so ancora come dimostrarlo per bene, ma mi sembra funzioni, infatti se ad un colore assegno più di 2 caselle otterrò un rettangolo dopo un numero di colonne minore).
Non appena avrò una colonna che ripete almeno una coppia di caselle dello stesso colore nella stessa posizione rispetto ad una colonna precedente, avrò un rettangolo con i lati paralleli ai lati della scacchiera.
Allora, considerando una colonna qualunque con 2 caselle per ogni colore, se conto quante sono le "permutazioni" di questa colonna tali che non ripetano due caselle dello stesso colore nella stessa posizione , ottengo $k-1$. Infatti comunque io metta queste colonne l'una accanto all'altra, non troverò mai due caselle dello stesso colore ripetute nella stessa posizione ,e quindi non otterrò mai un rettangolo, e comunque io colori la colonna successiva a questo blocco di colonne otterrò invece una ripetizione perchè ho finito le permutazioni "buone".

Guardando la soluzione , (che mi sembra piuttosto distante dai ragionamenti che ho fatto fino ad ora), e sostituendo $n=2,3$ nella formula giusta mi torna (ho contato a mano i casi con 2 o 3 colori): ma non riesco a capire come contare per ogni $n$ queste "colonne" che ho descritto. Potete aiutarmi? Sempre che io non abbia toppato in pieno il ragionamento eh! xD In tal caso scusatemi.

Beh, se ho capito bene il tuo ragionamento, basta che poni $k= \binom {2n}{2} + 1= \frac {2n \cdot (2n-1)}{2} +1 = 2n^2 - n + 1$.
Ossia $k$ deve essere maggiore del numero di modi in cui puoi scegliere le due posizioni delle caselle dello stesso colore tra le $2n$ totali (che sono $\binom {2n}{2}$.
E dato che $k$ deve essere minimo, allora aggiungi solo 1 al coefficiente binomiale.
Il tuo ragionamento mi pare funzioni, ma dovresti dimostrare quella parte in cui dici che il caso migliore sia quando hai 2 caselle per ogni colore. Perchè ad occhio non mi pare sia detto che funzioni. (in realtà, quello perchè funzioni dovrebbe essere il caso peggiore, ossia il caso limite in cui colorando nel peggiore dei modi riesci sempre ad ottenere il rettangolo che vuoi con il k che trovi dalla formula).

Valenash ha scritto: (in realtà, quello perchè funzioni dovrebbe essere il caso peggiore, ossia il caso limite in cui colorando nel peggiore dei modi riesci sempre ad ottenere il rettangolo che vuoi con il k che trovi dalla formula).

Sì esatto, mi sono espresso male, per caso "migliore" intendevo quello che dici te:cioè se il mio scopo fosse ottenere un rettangolo il prima possibile, allora il modo più stupido in cui potrei colorare le caselle dovrebbe essere questo, e comunque alla colonna successiva comunque io abbia colorato le caselle precedenti otterrò per forza un rettangolo.

Comunque grazie per la formula, era proprio quella che cercavo, e a pensarci era più facile di quanti mi ero prospettato xD Adesso provo un po' a pensare a come dimostrare (sempre che sia vero) quel fatto, e vedo se riesco ad aggiustare il tutto (la soluzione ufficiale è delirante )