Batterie ungheresi difettose

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Simo_the_wolf
Moderatore
Messaggi: 1019
Iscritto il: 01 gen 1970, 01:00
Località: Pescara

Batterie ungheresi difettose

Messaggio da Simo_the_wolf » 10 mag 2005, 22:58

A.A.A. batterie buone cercasi....

Il problema stuzzicante posto dall'ungherese era questo:

Dato un transistor e 8 batterie (indistinguibili) di cui 4 buone e 4 cattive determinare il minimo numero di prove che si devono fare per far emettere un fastidioso suono al transistor (il fastidioso suono viene emesso se e solo se due batterie buone vengono collegate al transistor)

Per chi era a Cesenatico, completare la dimostrazione dell'ungherese senza citare teoremi conosciuti (??? secondo lui, forse)

Buon divertimento!

MindFlyer

Messaggio da MindFlyer » 11 mag 2005, 02:22

La dimostrazione del team leader ungherese (o chi cappero era) usava il Teorema di Turan.
Ovviamente, visto che si tratta di esaminare un numero finito di casi (e nemmeno tanti), ricorrere a teoremoni non è assolutamente necessario.

Mi ricordo che una tecnica prevedeva di dividere le batterie in 3 gruppi: da 3, da 3 e da 2, e quindi di effettuare tutte le prove possibili all'interno di ciascun gruppo. Il totale è 7 prove, e mi sembra che Tizio ne abbia dimostrata l'ottimalità.

Per lo meno, Marco che era vicino a me ha asserito che con 6 prove non si poteva, e mi sembrava sufficientemente convinto. :wink:

jabberwocky
Messaggi: 163
Iscritto il: 01 gen 1970, 01:00

Messaggio da jabberwocky » 11 mag 2005, 09:28

d'accordo, ora dimostriamo però che con 6 prove non è possibile, deve esserci una diostrazione più semplice di quella dell'ungherese, ne sono quasi sicuro.
simone, tu l'hai risolto?
l

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 29 giu 2005, 15:59

UP!! Allora, chi riesce a fare funzionare la radio di Jan Pataki?
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 30 giu 2005, 11:57

Ho dedicato un po’ di tempo a questo problema… Allora, prima di tutto definisco cosa è una “tecnica”. Numeriamo le batterie da 1 a 8. Qualsiasi tecnica consiste nel definire 6 coppie (a,b) con 1<=a,b<=8 e a<>b e provare questi incontri. Per dimostrare che non esiste tecnica utile, si deve trovare almeno un caso per ogni tecnica in cui quest’ultima non funziona. Per fare ciò, disegno un grafo con 8 vertici ed ognuna delle 6 coppie è definito come un lato del grafo. Ad ogni punto associo una B o una C a seconda che la batteria sia buona o cattiva. Il contro-esempio dovrà avere 4B e 4C e fare in modo che non vi siano mai due B adiacenti… Divido in sotto-casi:

1) esiste almeno un sotto-grafo di 4 vertici completo. In tal caso i 6 lati sono già definiti e basta che le batterie tarocche siano quelle 4, mentre tutte le altre sono buone;

2) esiste almeno un sottografo di 3 vertici completo (ovverosia un triangolo). Questo è il caso più complesso. Supponiamo che il triangolo sia di vertici 1,2,3 e distinguiamo 4 sottocasi:
2a) i rimanenti 3 lati sono tutti nei rimanenti 5 vertici; in questo caso considerando quanti punti isolati possono rimanere (0,1,2), si tirano fuori 4 disegni che finiscono il caso 2a;
2b) esiste un solo lato di collegamento tra quel triangolo ed i rimanenti vertici, dove avremo gli altri 2 lati; in questo caso si riesce ad avere 2 batterie buone tra triangolo e vertice collegato al triangolo ed almeno altre 2 nei rimanenti vertici (2 disegni);
2c) esistono 2 lati di collegamento tra il triangolo e gli altri vertici; i disegni da fare sono nei casi in cui i lati di collegamento partono da vertici diversi e giungono a punti diversi; partono da vertici diversi e giungono a punti diversi, partono dal medesimo vertice e giungono a punti diversi; ognuno di questi casi richiede 2 disegni (in totale questo sottocaso richiede altri 6 disegni);
2d) esistono 3 lati di collegamento tra il triangolo e gli altri vertici; in tal caso il triangolo è di batterie buone ed un’altra buona si trova in un vertice libero (1 disegno):

3) i questo caso non esiste nessun triangolo, ma
3a) da un vertice escono almeno 4 lati; questo vertice è cattivo, mentre gli altri estremi dei 4 lati sono buoni;
3b) da un vertice escono almeno 3 lati; questo vertice è cattivo, mentre gli altri estremi dei 3 lati sono buoni; si verifica che almeno un altro buono si può aggiungere;
3c) nei rimanenti casi si possono tracciare percorsi indipendenti tra loro senza staccare la penna dal foglio; si fanno 2 disegni con un percorso di 4 lati chiuso o aperto; similmente per un percorso di 3 lati; non possono esistere solo percorsi di 2 lati;

----------------mmm… pare troppo elaborata e con facilità di perdere casi "per strada", anche se con i disegnini è + veloce… come veniva altrimenti? E cosa è il teorema di Turan?

ciao!

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 30 giu 2005, 13:40

Ciao. Sì. Mancano i dettagli, ma mi sembra che funzioni (anche se ci sono un po' di si vede....). Ecco la mia.

Riformuliamo il problema con il linguaggio dei grafi, come ha fatto Pataki. Abbiamo un grafo con 8 vertici (=8 batterie) e sappiamo che, comunque scelta una quaterna (=le quattro batterie buone) di vertici, esiste un arco (=una prova fatta con le due batterie agli estremi) che appartiene al grafo.

La tesi è che il grafo ha almeno 7 archi (=occorrono almeno 7 prove). Ovverossia, che per ogni grafo con <=6 vertici, esiste una quaterna di vertici che non hanno archi che li congiungono.

Sketch:

Concentriamoci sul numero di componenti connesse (e chi era a Cesenatico e non sa che cosa sono le componenti di un grafo, si è perso la meglio conferenza: vergogna!!!)

Se il grafo ha 4 o più componenti connesse trovo una quaterna di estranei (come?)

Quindi il grafo ha 3 o meno componenti. Se ha 8 vertici e <=6 archi, deve avere almeno 2 cp.ti (perché? mosse di saturazione, congiunzione... remember?...)

Se ha tre componenti, devono essere tre grafi completi (perché?) e quindi hanno almeno 7 archi (perché?), che sono troppi.

Se ha due componenti, non ha cicli (perché?). Allora trovo in ogni componente che ha almeno 3 vertici, due vertici che non si conoscono (perché?) e in ogni componente che ha almeno 5 (basterebbe 6) vertici, tre vertici che non si conoscono a due a due (perché?).

Dato che il grafo ha almeno una componente di almeno 5 vertici oppure due componenti di almeno 3 vertici (perché?), allora trovo una quaterna di estranei (come?).

-------------------------------------------------------------

A margine faccio notare che questo problema è un caso molto simile ad un problema di un giornalino di quest'inverno (quello delle n coppie di numeri da 1 a 3N). La soluzione di quell'esercizio suggerisce che il caso più "impaccato" per coprire tutte le quaterne è tre grafi completi con i vertici distribuiti in modo il più possibile omogeneo.

-------------------------------------------------------------

Puoi trovare l'enunciato e una traccia di dimostrazione del Teorema di Turan clickando qui.

Nel nostro caso lo applichi al grafo complementare (un arco è tracciato sse quella prova non è fatta) con n=8 e p=4. Risulta che deve avere al massimo

$ $ \frac{n^2}{2} \left( 1- \frac{1}{p-1} \right) = \frac{64}{3} < 22 $.

Dato che il grafo completo di tutte le prove ha 28 archi, il complemetare ne deve avere almeno 7. []

Ciao. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 30 giu 2005, 16:01

Ora o dopo andrò a vedere quel teorema... per ora ho letto la tua sol ed è scioccante come ragionare per "componenti connesse" (che se ho ben capito sono "parti di grafo indipendenti tra loro tali che per ogni parte da un punto si riesca a raggiungere tutti gli altri, ed i punti isolati sono considerati componenti connesse: se è sbagliato dillo, altrimenti... non dire nulla :wink: ) semplifichi il tutto... grazie mille!

Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 » 30 giu 2005, 18:01

non posso distrarmi mezzo secondo che dopo averci dedicato due ore mi trovo già due soluzioni prima della mia pseudo..cmq è piuttosto brutale e mi sono accorto ora che maca un caso(7,1 non è stato analizzato a dovere ma vi assicuro che non costituisce il minimo)..

Intanto noto che analizzando le coppie a gruppi di 8 devo effettuare un numero alto di tentativi:
$ {8 \choose 2}-{4 \choose 2}+1=23 $

Per cui considerando gruppi più piccoli diminuisco il numero di coppie per gruppo e quindi i tentativi totali(anche il numero di coppie sicuramente favorevoli cala però..) analizziamo ora tutti i casi possibili: noto che il numero di gruppi deve essere o due o tre perché il caso in cui sia uno è già stato analizzato e se è quattro non sono sicuro che ci siano coppie (potrebbe esserci una pila carica per gruppo..) e i gruppi devono contenere almeno 2 pile(perché se no non ci sarebbero coppie..)
1) due gruppi da 4 e 4: se ci va male non ci sono coppie nel primo gruppo (che ci conviene analizzare completamente..) e avremo usato $ {4 \choose 2}= 6 $ tentativi; sapremo però che nel secondo ci sono almeno 3 pile cariche da cui $ {4 \choose 2}-{3 \choose 2}+1 $ altri tentativi..totale 10 tentetivi.
2) Due gruppi da 5 e 3: entrambi potrebbero non avere coppie da cui 2 casi: prima analizzando il gruppo da5 e poi quello da 3 e l’opposto. Nel primo caso $ {5 \choose 2}=10 $ e sono già sopra i risultati precedenti..quindi è inutile continuare.. nel secondo caso $ {3 \choose 2} $ tentativi nel primo che potrebbero aime non andare a frutto ma ci assicurano 3 pile nel secondo..totale tentativi: $ {3 \choose 2}+{5 \choose 2}-{3 \choose 2}+1=11 $ ancora troppo.
3) Due gruppi da6 e 2: ancora due casi:o $ {6 \choose 2}-{2 \choose 2}+1=15 $ oppure$ {2 \choose 2}+{6 \choose 2}-{3 \choose 2}+1=14 $
4) Ora iniziamo con i tre guppi che sono più promettenti..3,3,2: sicuramente uno di questi contiene una coppia(principio dei cassetti)purtroppo potrebbe essercene solo una..e potremmo trovarla all’ultimo tentativo..da cui numero di tentativi: $ 2{3 \choose 2}+{2 \choose 2}=7 $ che fino ad adesso è il minimo (e secondo Marco lo rimarrà..)
5) Evitando gli addendi 0 e 1 rimane solo un’altra possibilità:4,2,2 ancora possiamo trovarci una sola coppia e come ultima per cui i tentativi sarebbero: $ 2{2 \choose 2}+{4 \choose 2}=8 $che non è il massimo.
Un’ultima considerazione: all’inizio ho scritto che conviene analizzare tutte le coppie possibili dei gruppi in analisi perché non analizzare delle coppie equivalrebbe a creare un nuovo gruppo (quello delle coppie non analizzate che potrebbero essere coppie di pile cariche..) inoltre se decidessi di cambiare gruppo prima di avere finito con uno rischierei di trovarmi due(o tre dipende da quante coppie ho saltato..) pile cariche nel gruppo che non ho analizzato completamente ovvero lo stesso numero che avrebbe come massimo quello che stò per analizzare..e ciò non è conveniente nei casi in cui ho tre gruppi(mi giocherei l’unica coppia) ne nel caso 4,4 (per simmetria..) mentre nei casi 6,2 e 5,3 saltare tre tentativi nel gruppo grosso è un suicidio(potremmo trovarci con solo una pila carica nell’altro..) e con due tentativi saltati nel grosso saremmo già sopra 7..è già stato analizzato il caso in cui si è saltato il gruppo piccolo di 6,2..saltando due tentativi in 3,5: avrei$ {3 \choose 2}-2+{5 \choose 2}-{2 \choose 2}=10 $ che è sopra..
Ho saltato i casi in cui c’è un gruppo da 1 (7,1;6,1,1:5,2,1;4,3,1) poiché ho considerato l’uno come casi persi da un’insieme più grosso..(si diminuisce di uno il numero degli insiemi e ci si ricollega attraverso l’analisi precedente).
Ps ora leggerò le sol di info e marco che suppongo molto più geniali della mia (nella quale sicuramente ci sarà anche qualche errore logico..) @ marco: non smontarmi troppo se è sbagliata grazie..
Pps(OT)dov'è che posso trovare una bella dispensa sui grafi??tutto quello che conosco è ciò(pochissimo,mezza pagina..) che c'è nelle appendici del libro"Olimpiadi della matematica..Bersanti Conti"

matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da matthewtrager » 01 lug 2005, 20:28

aggiungo una variante (che nasce dal fatto che non so leggere...):
quante prove sono necessarie per trovare tutte e quattro le batterie funzionanti?

Avatar utente
enomis_costa88
Messaggi: 537
Iscritto il: 01 gen 1970, 01:00
Località: Brescia

Messaggio da enomis_costa88 » 02 lug 2005, 18:00

@matthewtrager (non serio..) visto che oggi non ho tanta voglia di pensare..sono sicuro che con $ {8 \choose 2} $ce la fai.. :lol: :lol:
Ps ma dici trovare anche per esclusione o mettere nella radio???

Avatar utente
Melkon
Messaggi: 259
Iscritto il: 01 gen 1970, 01:00
Località: Ferrara

Messaggio da Melkon » 02 lug 2005, 18:59

matthewtrager ha scritto:aggiungo una variante (che nasce dal fatto che non so leggere...):
quante prove sono necessarie per trovare tutte e quattro le batterie funzionanti?
11?
Numero le batterie.
Usiamo la 1 con le successive 4 e scopriamo, male che vada, che non funziona (bastano 4 prove per il pigeonhole). Poi proviamo la 2 con le 3 dopo e male che vada ancora non va. Poi la 3 con le due dopo e siamo ancora sfigati. Poi la 4 con la successiva e dopo serve un ultima prova in ogni caso. Dunque se non ho sbagliato direi 11. Infatti se una volta becchiamo la batteria giusta il numero di tentativi dovrebbe calare. Ho idea che partendo da casi piccoli si possa trovare la formula (qualcosa tipo somm da n a N +1) con l'induzione... appena ho un po' di tempo provo.

edit: ho fallato brutalmente...
Ultima modifica di Melkon il 02 lug 2005, 23:43, modificato 1 volta in totale.
"Bisogna vivere come si pensa, se no, prima o poi, ci si troverà a pensare come si è vissuto"
Paul Borget

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 02 lug 2005, 22:01

Il tuo metodo Melkon non mi pare vada bene... Immagina

1B 2C 3C 4C 5C 6B 7B 8B

prendi la prima e provala con le batterie 2,3,4,5 (entrambe cattive)... non puoi capire nè che non funziona (infatti funziona! è B, cioè buona!) nè che funzioa, infatti avresti avuto i medesimi risultati con questa disposizione:

1C 2B 3B 4B 5B 6C 7C 8C

sbaglio o ci vuole qualche altra tecnica? o perlomeno quella sopra và modificata?

Osservo cmq che questo problema mi pare sia fondamentalmente diverso da quello di Simo... Nel primo la scelta della prova da fare era alquanto arbitraria, mentre in questo caso credo sia utile trattare le batterie diversamente a seconda degli effetti ottenuti (nel senso: una volta scoperte due batterie buone, è fondamentale sapere che quelle sono buone!)... ma lascio il rischio di dire una sol errata a qualcun altro, anche perchè non è che ci abbia ragionato molto :evil: :D :twisted: :wink:

Avatar utente
HumanTorch
Messaggi: 281
Iscritto il: 01 gen 1970, 01:00
Località: Tricase

Messaggio da HumanTorch » 02 lug 2005, 23:44

Comunque devono essere meno di $ 7\cdot 2=14 $. Io proporrei $ 10 $; ottenibile dividendo le otto lampadine in gruppi da $ 2 $: in tal modo con le prime $ 7 $ mosse conosciamo le prime due buone, le restanti tre ci permettono di stabilire le altre due: difatti supponiamo le lambade numerate:
1 2 3 4 5 6 7 8

Colleghiamo le lampade $ n $ e $ n+1 $, con $ n $ dispari: se non si sente mai il suono (caso peggiore), abbiamo preso delle coppie contenenti una lampada buona e una flippata; a questo punto dividiamo in gruppi da quattro le lampade: è chiaro che in ogni gruppo due lampade sono ok e le altre due no; ci basta provare quindi (prendendo la prima quartina) 1-3 (1-2 e 3-4 sappiamo che non funzionano), 1-4, 2-3: se non si produce alcun rumore, sappiamo che 1 e 3 non vanno, quindi le giuste sono 2-4 (un'ulteriore prova sarebbe superflua); stesso ragionamento per la seconda quartina..sto prendendo un abbaglio?

Avatar utente
Melkon
Messaggi: 259
Iscritto il: 01 gen 1970, 01:00
Località: Ferrara

Messaggio da Melkon » 02 lug 2005, 23:50

credevo che si potesse aggiustare il tutto contando che ci vogliono 5 (non 4, cavolo) tentativi per trovare la prima, solo che poi andando avanti le cose si complicano, e adesso sono troppo stanco per tentare un altro approccio... ci riprovo domani mattina...
"Bisogna vivere come si pensa, se no, prima o poi, ci si troverà a pensare come si è vissuto"
Paul Borget

matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da matthewtrager » 03 lug 2005, 11:37

@human torch: si puo' fare con 9! il metodo e' quello che hai usato tu ma poi per l'altra quartina basta provare 2 volte, provando una di quelle buone con una per ognuna delle due coppie rimaste: poi fai per esclusione (se la trovi ok, senno' e' quell'altra della coppia).. credo proprio sia il minimo ma non sono ancora riuscito a dimostrarlo!

Rispondi