Problema/Gioco - "I chinotti trepidano"

In un tranquillo e soleggiato giorno di Marzo,

nel brevissimo periodo felice e spensierato che segue una devastante sessione di esami, mi imbattei in questo simpatico problema pubblicato dalla rivista "Rudi Mathematici":

Rudi Mathematici - Numero 194 - Marzo 2015


I Chinotti trepidano... ma non ci pare ancora il caso di riaprire il campo di tiro: rischiamo di dover mettere la sciarpa di lana alle frecce, e la cosa non è molto funzionale: quindi, le attività di Doc si stanno rivolgendo al vicino appezzamento, che brama dall’essere piantumato.
Al momento il prato è un quadrato, e speriamo lo resti per tutta la durata del problema (sapete, quando Doc si dà da fare nulla può essere dato per scontato): l’idea, visto che ci aspettiamo un’estate piuttosto calda , è quella di piantare degli alberi di alto fusto che siano in grado di fornire un poco di ombra agli esausti arcieri: non solo, ma quest’anno la falange arcieristica dovrebbe anche aumentare il numero delle sue componenti, quindi Rudy finalmente la smetterà di essere secondo.
Dicevamo: sul prato Doc intende piantare in modo regolare 169 alberi, in modo da ottenere un reticolo 13x13; quello che non lo convince è che, tra il fatto che il prato è un quadrato e il reticolo regolare, la cosa sta diventando piuttosto noiosa e ripetitiva, e sta cercando consigli per vivacizzare la cosa: l’ultima gli è stata suggerita dal vivaista (che non vedeva l’ora di disfarsi di robaccia che languiva in magazzino), con la proposta di mettere 53 alberi diversi dagli altri (quindi, 116 di un tipo e 53 di un altro: giusto? Giusto), sempre sui punti del reticolo ma piazzati in un modo piuttosto casuale.
La cosa ha immediatamente entusiasmato Doc che, in attesa del disgelo (sì, dalle sue parti riesce anche a gelare), sta progettando disposizioni casuali-ma-non-troppo dei 53 alberi diversi: il motivo del “ma-non-troppo” è che, per sottolineare la casualità, il Nostro richiede che non ci siano quattro alberi del gruppo di 53 che siano ai vertici di un rettangolo con lati paralleli ai lati dell’appezzamento (nulla viene detto sugli altri: invecchiando, un minimo di ripetitività fa comunque piacere). Fornito di un ragionevole numero di biglie (di due colori diversi) e di una sandbox, stiamo riuscendo a tenerlo tranquillo, ma lo rivorremmo tra gli umani per l’ora di cena. Riuscite ad aiutarlo? E, se riusciste a generalizzare, potreste anche renderlo felice: in un quadrato di lato n, quanti punti potete scegliere al massimo in modo tale che nessuno gruppo di quattro sia sui vertici di un rettangolo di lati paralleli al quadrato originale?


(Se avete avuto la pazienza di leggere tutto il testo avrete capito che il problema in poche parole consiste nel disporre su una scacchiera 13x13 53 oggetti uguali con la condizione che 4 oggetti non vengano a trovarsi ai vertici di un rettangolo (o quadrato) con lati paralleli ai bordi della scacchiera. )


 
Il problema dall'aspetto così carino e simpatico degenerò in breve tempo in causa di turbamento perenne, isolamento diurno e notti insonne.

Pagine e pagine di quaderni furono sprecate invane alla ricerca di una soluzione, ore e ore di programmazione ed elaborazione al computer alla disperata ricerca di una soluzione tramite ignorante bruteforce, ma il problema sembrava proprio essere irrisolvibile.

Ne nacque addirittura un giochino, "Rector" lo chiamai, non so per quale ben preciso motivo, forse    perchè ricordava la condizione di non generare rettangoli...


("Rector" - Download)

<------ (Screenshot del programma)








Alla fine mi arresi e sconsolato mi rivolsi al mio grande e onniscente professore di Analisi I il quale mi dimostrò come fosse impossibile trovare una disposizione di 53 oggetti in quanto 52 era il numero massimo...

  Questa è la storia di come persi il mio periodo di calma e spensieratezza post-esami invernali alla ricerca ostinata di una soluzione che neanche esisteva, e di come imparai a stare ben attento e a diffidare da ciò che dicono i matematici, in quanto amano fare scherzi di cattivo gusto a chi è poco attento alle loro parole.

PS: Il programma è stato compilato per linux, nel caso aveste windows o voleste avere il codice basta contattarmi per email.

PPS: Nel caso foste tanto temerari da voler vedere la dimostrazione del sommo professore di analisi basta avere una piccola dose di pazienza per contattarmi tramite email.