Giochino con linee e punti

[Igor]

Premetto che questo problema non è tratto da alcun testo e non ne conosco la
soluzione, ammesso che esista, ma è un 'dubbio' che mi è sorto facendo un gioco con un mio compagno di classe durante l'ora di italiano .

Il gioco comincia con un certo numero di punti posti a caso in un piano.Una mossa consiste nell'unire due di questi punti con una linea, non necessariamente retta,appartenente sempre allo stesso piano, e di segnare un altro punto su di essa.Questa linea però non può intersecare altre linee disegnate in precedenza.Quando un punto è collegato ad altri tre, esso non può più essere usato.Il gioco finisce quando un giocatore non può più effettuare mosse valide.

La mia domanda è questa:se partiamo con n punti, quanti punti abbiamo alla fine?

L'ho messo in Matematica non Elementare perchè mi sembra estremamente complesso.Spero che qualcuno possa darmi almeno qualche chiarimento.

[MindFlyer]

La mia domanda è questa:se partiamo con n punti, quanti punti abbiamo alla fine?

La domanda sottointente un po' di cose: che il gioco termina in un numero finito di mosse, e che il numero di punti finali è indipendente dalla scelta delle mosse.
Sono entrambi fatti ovvi? O comunque li hai già dimostrati?

[Igor]

Il fatto che il gioco termini in un numero finito di mosse dovrebbere essere vero,
perchè giocando innumerevoli volte (sempre nell'ora di italiano), si è sempre verificato,tuttavia non sono riuscito a dimostrarlo.

Il numero finale di punti invece dipende dalla scelta delle mosse, perchè giocando più volte e partendo dallo stesso numero di punti, ho ottenuto configurazioni finali
che avevano un diverso numero di punti.

In effetti la domanda è più precisamente questa:

Detto n il numero iniziale di punti e m quello finale determinare i valori che può assumere m.

Scusa Mind per le mie imprecisioni, ma essendo un problema da me inventato,
ho avuto difficoltà anche a formularlo

In effetti, prima di rispondere alla mia domanda, bisognerebbe provare che il
gioco finisce effettivamente in un numero finito di mosse.

[HumanTorch]

Per quanto riguarda la presenza della fine del gioco, con la postilla che un numero deve essere usato per non più di tre volte e con un numero finito di punti iniziali $ n $, se non ho misinterpretato, non considerando i nuovi aggiunti, le linee tracciabili (che possano essere o meno accettate nel gioco) sono finite.
Per il resto, il problema mi ricorda il dilemma dei tubi del gas e dell'elettricità: difatti, è dimostrato che, preso un rettangolo e su di esso i vertici e due punti su due lati opposti in modo che i tre punti sullo stesso lato siano simmetrici a quelli sull'opposto rispetto all'asse del rettangolo, non è possibile, almeno nel piano, mandare $ 3 $ linee da uno dei punti di un lato ai tre del lato opposto senza che alcune delle $ 9 $ linee tracciate si intersechino.
P.S.Ma si possono collegare due punti più volte, con più linee?

[MindFlyer]

Per quanto riguarda la presenza della fine del gioco, con la postilla che un numero deve essere usato per non più di tre volte e con un numero finito di punti iniziali $ n $, se non ho misinterpretato, le linee tracciabili (che possano essere o meno accettate nel gioco) sono finite.

Dimentichi che per ogni linea che tracci devi aggiungere un punto.

Comunque basta contare il numero k di archi uscenti da ciascun nodo che devono ancora essere tracciati, e vedere che ad ogni mossa questo numero decresce di 1. Infatti, ogni nuovo arco fa diminuire di 1 il numero di archi uscenti da tracciare dai suoi estremi. Mentre il nuovo nodo aggiunto ha già 2 archi uscenti, e fa quindi incrementare k di 1.
Dunque, se all'inizio vi sono n punti, il gioco durerà al più 3n-1 mosse (perché quando k=1 non si può più muovere).

Mentre la seconda domanda, quella su "quanti punti vi possono essere alla fine, al variare delle mosse", è ancora mal posta. Infatti non è chiaro che forma debba avere la risposta. Perché la domanda abbia un senso dovresti trasformarla in qualcosa del tipo "dimostrare che il numero di punti finali è della forma...". In questo modo è chiaro cosa bisogna dimostrare.

[Igor]

Allora, non ti posso chiedere che il numero finale m di punti abbia una certa forma,
perchè m può assumere valori diversi:ad esempio per n=2, si può raggiungere sia
m = 6 che m = 7.

Quello che chiedo è di esplicitare l'insieme di tutti e soli i valori di m raggiungibili
partendo con n punti.

Meglio di così non riesco a formularla.

Ripeto che, non conoscendo la soluzione, non posso chiederti in antipico di dimostrare che questo insieme abbia una particolare forma.

[MindFlyer]

Allora bisognerebbe chiarire cosa significa "esplicitare".
E' ovvio che se non hai ben chiaro in mente cosa vuoi che si dimostri, il problema resta insensato.

[MindFlyer]

Ok Igor, per venirti incontro propongo di dimostrare che per ogni n esiste una successione di mosse che permette di massimizzare m.
Ovvero, che per ogni n esiste una partita che termina con 4n-1 punti.

[Igor]

Provo a dimostrarlo per induzione.

Per n=2 è semplice trovare una partita che termini con sette punti.

Ammettiamo ora che per un generico n esista una partita che termini con 4n-1
punti.

Vogliamo dimostrare che per n+1 esista una partita che finisca con 4(n+1)-1=4n+3
punti.

Consideriamo dunque la partita iniziata con n e terminata con 4n-1 punti.
Di questi 4n-1 punti, 4n sono inutilizzabili, mentre uno,che chiameremo P, è unito ad altri due, e quindi permette ancora una mossa.
Aggiungiamo ora punto in questa partita, supponendo che sia uno dei punti
iniziali, e chiamiamolo con A.
Eseguiamo ora le seguenti mosse:

1)uniamo A con P e disegnamo su questa linea un punto B.
Ora P è occupato, A è collegato ad un solo punto e B è collegato a due.
2)uniamo B con A e segniamo su questa linea un punto C.
Ora B è occupato, mentre A e C sono collegati entrambi a due punti.
3)uniamo A con C, e segniamo su questa linea un punto D.
La partita termina perchè ci resta il solo punto D.

Analizziamo ora questa partita;

Essa inizia con n+1 punti,gli n della partita iniziale più quello che abbiamo aggiunto noi.

Ai 4n-1 finali della partita precedente, dobbiamo ora aggiungerne 4(A,B,C,D), dunque la partita termina proprio con 4n-1+4=4n+3 punti, che era quello che volevamo dimostrare.

[MindFlyer]

Sì, ok.
Hai tralasciato di dire che esiste sempre una scelta di A per cui sia possibile quella successione di mosse, ma si tratta di un fatto piuttosto evidente.

Qualche congettura sul minimo m?

[Igor]

Credo di aver trovato qualcosa di interessante.

Se n è pari, posto cioè n=2K, allora

min(2K)=7k-1, dove min(n) restituisce il minimo numero finale m di punti raggiungibile partendo da n punti.

Provo a spiegare brevemente come sono arrivato a questo risultato,anche se la
dimostrazione non è ancora completa.

Per n=2 il minimo è 6(una partita con m=6 esiste, e dovrebbere essere semplice
vedere che m=5 non è raggiungibile)

Questa partita(se provate a disegnarla è più facile), ha un punto 'morto',( cioè un
punto da cui partono meno di tre linee, ma circondato da una linea chiusa sulla quale tutti i punti sono occupati), un punto che permette ancora una mossa e tutti gli altri occupati.

Ora l'idea è quella di ottenere il minimo di 2k combinando K di queste partite da 2.

Proviamo infatti a disegnare queste k partite, in modo che non si intersichino tra loro :

I punti ancora utilizzabili sono k, uno per ogni partita, ed ognuno di questi permette
di disegnare solo un'altra linea.Inoltre anche i nuovi punti segnati sulle linee
possono essere utilizzati solo un'altra volta.Ad ogni mossa dunque il numero di
punti rimasti decrementa di 1(ne occupiamo due e ne segniamo uno).Il numero di mosse restanti è dunque al massimo K-1.

Dimostriamo ora che non è possibile effettuarne un numero minore.

Infatti,affinchè questo si verifichi, devono venirsi a formare dei punti 'morti'.
Un punto morto si forma quando intorno ad esso si trova una figura chiusa, sulla quale tutti i punti sono occupati.Vediamo se nel nostro caso è possibile.

Consideriamo dunque un punto dell'ipotetica linea che dovrebbe 'circondare' il
nostro punto morto.Ora questo punto dovrebbe essere collegato ad altri due.
Ma tutti i punti che ci restano sono utilizzabili una sola volta,assurdo.

Riepilogando, il numero finale di punti è 6*k(i punti delle k partite) + k-1 (aggiunti
in seguito) = 7K-1.

Osserviamo però che una partita non massimale partendo da n punti punti può essere raggiunta anche in altri modi(ad esempio una partita per n=6 si può ottenere sia combinando 3 partite da 2, ma anche combinandone 2 da 3).Tuttavia credo che si possa dimostrare che il minimo assoluto venga raggiunto quando la partite che si combibano sono da 2(forse ho già una mezza dimostrazione).

Più in generale si potrebbe dimostrare che min(n) si ottiene combinado n/k partite
da k punti, dove k è il più piccolo divisore primo di n.


Che ne pensate?Sto prendendo un grosso granchio o ho scritto qualcosa di sensato?

[MindFlyer]

No, non mi pare giusto.
Usando la stessa idea e raggruppando i punti a 3 a 3 si riesce a trasformare ogni terna di punti in 10 punti. Il rapporto è quindi 10/3, che è minore del 7/2 che si ottiene col tuo metodo.

[MindFlyer]

E indovina un po': prendendoli a 4 a 4 si ottiene 13/4, che è ancora minore.