Non sapevo dove metterlo, spero di non sbagliare

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Vinci
Messaggi: 159
Iscritto il: 30 gen 2015, 18:38

Non sapevo dove metterlo, spero di non sbagliare

Messaggio da Vinci »

Nel parlamento di Sikinia, ogni membro ha al massimo tre nemici. Dimostrare che il parlamento può essere diviso in due case in modo che ciascun membro ha al massimo un nemico nella sua casa.
Vorrei dire che lo ho trovato e non sono riuscito a risolverlo, quindi lo metto qui perchè vorrei tanto trovare una soluzione.
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Non sapevo dove metterlo, spero di non sbagliare

Messaggio da Gerald Lambeau »

L'inimicizia è considerata vicendevole? Cioè, se $A$ è nemico di $B$, $B$ è nemico di $A$?
"If only I could be so grossly incandescent!"
Vinci
Messaggi: 159
Iscritto il: 30 gen 2015, 18:38

Re: Non sapevo dove metterlo, spero di non sbagliare

Messaggio da Vinci »

Mmm, l'esercizio non lo dice. :/
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Non sapevo dove metterlo, spero di non sbagliare

Messaggio da Gerald Lambeau »

Di solito è così e, per come l'ho risolto, è un'ipotesi necessaria (poi magari non serve davvero, ma in quel caso non saprei come procedere).
Ad ogni modo, vuoi la soluzione o solo degli aiuti?
"If only I could be so grossly incandescent!"
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Non sapevo dove metterlo, spero di non sbagliare

Messaggio da Gerald Lambeau »

Sono andato a controllare l'esercizio (mi sono ricordato che è uno degli esempi del primo capitolo dell'Engel), effettivamente non lo specifica, ma per come lo risolve (praticamente come l'ho fatto io, infatti mi pareva di ricordare un esercizio del genere XD) quell'ipotesi serve.
"If only I could be so grossly incandescent!"
Vinci
Messaggi: 159
Iscritto il: 30 gen 2015, 18:38

Re: Non sapevo dove metterlo, spero di non sbagliare

Messaggio da Vinci »

Dammi la soluzione, ci ho ragionato abbastanza xD
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Non sapevo dove metterlo, spero di non sbagliare

Messaggio da Gerald Lambeau »

Facciamo che la divido in piccoli indizi prima di scriverla tutta, così puoi confrontare con le idee che ti sono venute.
Testo nascosto:
Il primo capitolo dell'Engel, dove questo problema viene usato come esempio, è sugli invarianti.
Testo nascosto:
Alcuni invarianti variano.
Testo nascosto:
Alcuni invarianti variano in modo controllato, ripetendo un pattern, assumendo cioè la stessa sequenza di valori ripetuta in loop, altri invece vanno sempre in una direzione, cioè aumentano sempre o diminuiscono sempre, per poi doversi fermare perché rappresentano una quantità che non può eccedere nella direzione presa. Quale di queste due tipologie ci servirà?
Questo spoiler è, a mio avviso, il più importante.
Testo nascosto:
È un invariante che va sempre in una direzione quello che ci serve. Ti dirò di più, è l'invariante più comune (o almeno il primo che viene in mente) di quella tipologia: è un invariante che rappresenta una quantità non negativa che va sempre a scendere. Ma qual è? Come usarlo?
Dire qual è l'invariante farebbe capire subito come usarlo e porterebbe alla soluzione, quindi eccola.
Testo nascosto:
Formiamo le due case a caso. Consideriamo la seguente quantità: la somma di quanti nemici ciascun parlamentare ha nella sua stessa casa (se serve spiego più dettagliatamente come contare la nostra quantità). Chiaramente, tutti gli addendi sono $\ge 0$, quindi la somma è $\ge 0$. Supponiamo per assurdo che tutte le configurazioni non soddisfino i nostri obiettivi. Allora, partendo dalla nostra configurazione a caso, possiamo sempre trovare qualcuno con almeno due nemici nella sua casa, quindi possiamo fare all'infinito la seguente mossa: spostare quel qualcuno nell'altra casa. Se questa mossa facesse diminuire la quantità, dato che quest'ultima ha un limite inferiore, prima o poi saremo costretti a fermarci, il che però ci dirà che avevamo ragione noi! Vediamo perché. Due casi:
i) il tizio ha due nemici qui e uno nell'altra casa: se lo spostiamo, lui passa da 2 nemici a 1, il nemico della seconda casa aumenta di 1, i due nemici della prima casa diminuiscono tutti e due di 1, quindi la quantità in totale scende di 2;
ii) il tizio ha tre nemici qui e nessuno nell'altra casa: lui passa da 3 a 0, nessuno aumenta nella seconda casa, tre diminuiscono di 1 nella prima casa, in totale si diminuisce di 6.
Quindi è vero, la quantità scende, ma vogliamo essere precisi: come diciamo che arrivare a un limite inferiore non ci premette più di muovere? Facile! Nel primo caso, per diminuire di 2, il tizio aveva due nemici nella sua casa, quindi la quantità è almeno 2 (almeno 4 in realtà) e si può diminuire, stessa cosa nel secondo caso, aveva tre nemici, quindi conta 3, e ciascuno di loro contava 1, quindi 6, e si può scendere.
Quindi: o ci fermiamo prima perché non ci sono più tizi con troppi nemici e quindi abbiamo vinto, oppure si fa scendere la quantità fino ad arrivare sotto al 3, e se la quantità è 0 nessuno ha nemici, se è 2 ci sono solo due nemici, nemici fra loro e con nessun altro, nella stessa casa (1 non è possibile che si realizzi come quantità) e abbiamo vinto ugualmente.
Domanda: sai dirmi perché senza l'ipotesi di vicendevolezza tutto questo bel discorso anche fin troppo lungo non funziona?
"If only I could be so grossly incandescent!"
Vinci
Messaggi: 159
Iscritto il: 30 gen 2015, 18:38

Re: Non sapevo dove metterlo, spero di non sbagliare

Messaggio da Vinci »

Non funziona perchè non è detto che, quando sposto una persona che in una casa ha 2 o 3 nemici all'altra, il numero di nemici di ciascuna persona diminuisca. Ad esempio se ho una persona che in una casa ha tutti e tre i suoi nemici, e la sposto nell'altra casa, non so quante persone nell'altra casa hanno quella persona come nemico (potrebbero essere 3 o più!).
Giusto?
Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: Non sapevo dove metterlo, spero di non sbagliare

Messaggio da Gerald Lambeau »

Giusto!
"If only I could be so grossly incandescent!"
Rispondi