Nine Dots Puzzle extended to n1 X n2 X … X nk points under house arrest
Marco Ripà (July 2013)
sPIqr Society, Roma, Italia
Email: marcokrt1984@yahoo.it
Abstract (En). Here is the second and last part of the generalized solution to the extended “Nine Dots Puzzle”. In this paper I provide a non-trivial Lower Bound for the k-dimensional n1 X n2 X … X nk points problem. In this way, you can build a range in which certainly will fall all the best possible solutions to the problem we are considering. In conclusion, I provide a few characteristic numerical examples in order to appreciate the goodness of the result arising from the particular approach I have chosen.
Keywords: dots, straight line, inside the box, plane, upper bound, lower bound, graph theory, segment, points.
MSC2010: Primary 91A43; Secondary 05E30, 91A46.
Abstract (It). Ecco la seconda ed ultima parte della soluzione generalizzata al problema dei nove punti, il cosiddetto “Nine Dots Puzzle”. Nel presente articolo si definisce un Lower Bound non banale per la versione k-dimensionale del problema degli n1 X n2 X … X nk punti. In tal modo è possibile costruire un intervallo nel quale ricadano con assoluta certezza tutte le migliori soluzioni possibili al problema considerato. In conclusione, fornirò alcuni specifici esempi numerici al fine di far apprezzare la bontà dei risultati derivanti dal particolare approccio scelto.
Chiavi di ricerca: punti, linea, segmenti, inside the box, piano, limite superiore, limite inferiore, teoria dei grafi.
MSC2010: Primaria 91A43; Secondaria 05E30, 91A46.
1. Introduzione
Il presente articolo non è altro che la continuazione del precedente
[Nine-Dots-Puzzle-Extended-to-nXnX...Xn-Points]: mi propongo dunque di definire un Lower Bound (piuttosto solido e non banale) per il problema degli n1 X n2 X … X nk punti come definito nell’appendice 5 del paper summenzionato.
Il Lower Bound in questione scaturirà da considerazioni generali e pressoché ovvie e, assieme all’Upper Bound già definito nell’altro paper, fornirà un intervallo nel quale si collocheranno tutte le migliori soluzioni possibili al problema (al variare di ni e k nei naturali positivi).
2. Il problema degli n1 X n2 X … X nk punti agli arresti domiciliari
Consideriamo innanzitutto la struttura della nostra griglia per k=3 (n1≤n2≤n3): non è possibile intersecare più di (n3−1)+(n2–1)=n3+n2−2 punti con due linee consecutive; c’è però un’unica eccezione (che per comodità possiamo assumere come il caso delle prime due linee tracciate). In tale circostanza, è possibile intersecare n3 punti con la linea iniziale ed n2−1 con la successiva, proprio come avviene nel caso della soluzione della spirale rettangolare che ho proposto.
Osserviamo adesso che, giacendo (per definizione) ogni segmento su un piano, sarà necessario prevedere n1−1 linee di collegamento tra i vari piani che vengono affrontati in successione (di qualsiasi tipo): non c’è modo di evitare di spendere meno di n1−1 linee per collegare (al più) n1−1 punti ciascuna (sotto il vincolo definito in precedenza di connettere n3+n2−1 punti con i primi due segmenti rettilinei). Ciascuna di queste linee potrebbe interporsi tra altrettanti segmenti rettilinei capaci di connettere nk−1 punti alla volta.
Ragionando nello stesso modo, vediamo che il risultato di cui sopra, nel caso a k dimensioni (k≥3), non muta nella sostanza.
Sia hl il numero di segmenti rettilinei del nostro Lower Bound, per k≥3, risulta che
Si noti ora come è possibile migliorare il risultato della (2) considerando che le linee di collegamento tra i vari piani non possano effettivamente intersecare ni−1 punti ciascuna: per coprire tutti i piani della/e dimensione/i contraddistinta/e da meno punti allineati (i valori di ni con pedice più basso) è possibile infatti intersecare ni−1 punti con la prima linea, ni−2 punti con la seconda, ni−3 punti con la successiva, ecc…
3. Conclusione
