I seguenti problemi sono stati proposti da Valerio I. , aspirante fisico e pugile, e da Daniele T, aspirante fisico anche lui e esperto di calamite.
-In un gioco a quiz il concorrente è messo di fronte alla scelta di tre porte. Dietro due di esse c'è una capra, dietro la terza c'è un'automobile. Il conduttore è onniscente.
Il concorrente vince se sceglie la porta che nasconde l'auto (ammettiamo che gli faccia più piacere vincere l'auto che non una delle due capre).
Egli fa una prima scelta. Il conduttore apre allora una delle porte che nasconde una capra (si noti che è sempre possibile farlo...). A questo punto gli chiede al concorrente:-Vuoi cambiare la tua scelta?-.
La domanda del problema è: gli conviene o no cambiare scelta?
-In un oasi si trovano un esploratore, una jeep e tutto il petrolio dell'Universo. L'esploratore deve andare in una città che dista L (minore di infinito:) ) dall'oasi ma tutta la benzina che riesce a imbarcare nella jeep è comunque insufficiente per raggiungere l'altra città.
Bene...come si fa?
Io conosco la soluzione del primo quesito perchè il pugile me l'ha detta. Non conosco invece la soluzione del secondo problema. Prima di scrivere la soluzione in un comment siete pregati di aspettare un po' di tempo, più o meno una settimana...poi vedete voi.
T
PS Sul fatto di non pubblicare soluzioni mi rivolgevo a Valerio e Daniele...lo scrivo perchè questa cosa ha già dato adito ad equivoci. Chiunque voglia dare soluzioni può farlo. Sorry
23 commenti:
Non è esatto che il conduttore apre una delle porte che nasconde una capra. Il conduttore apre una delle porte che nasconde una capra, scegliendo tra le due porte che il concorrente non ha scelto.
Aspirante pugile... tsk...
Ma se imbarco tutta la benzina che posso e poi proseguo a piedi??Oppure vendo il petrolio agli americani e mi autofinanzio le ricerche per il teletrasporto?
Il marinaio semplice
Ho trovato.
Imbarco più carburante che posso. Cammino fino a che non cosumo un quarto del carburante imbarcato. Svuoto due quarti del carburante imbarcato in un pozzo, torno indietro e ricomincio finche non ho trasportato carburante a sufficienza per fare il giro del mondo. Dopo ricomincio. Dovrei arrivare alla fine del deserto. Che ne dite?
si, ci sta.. ma non dovevamo aspettare a postare soluzioni?
Il primo comunque è noto come paradosso di monty hall.
ah invece il secondo mi sembra fosse un problema NP.. possibile?
(continuo nel mio stile di spararle grosse per poi dover ritrattare, ma mi sembra un atteggiamento molto più dinamico e divertente...)
no...dicevo a valerio e daniele di non non pubblicare la soluzione prima di una settimana...mi dispiace per l'equivoco:)...
vedeverde puoi vedere l'ultimo commento al post sulle bolle di sapone?
grazie; ciao
Vedeverde si arrabbia per non aver trovato la soluzione e poi le spara grosse per rifarsi !!!!:)
Comunque cosa significa che il secondo è un problema di tipo NP? forse che i passi per ottenere la soluzione non sono "polinomiali"? facci sapere presto, aspettiamo una tua risposta in qualità di matematico di fiducia!!
:-) al limite mi arrabbio perchè li conoscevo tutti e due i problemi!!
Avevo dei fogli che parlavano di questo problema e della ottimizzazione dei carichi e viaggi, e mi sembra dicesse che non c'era verso nel caso generale di dimostrare l'ottimità della soluzione (per esempio quella del marinaio semplice non è detto sia ottima).O meglio,ovviamente un modo c'è, vederle tutte e confrontarle, e questo ci riconduce al problema NP, perchè il costo per fare sta cosa è esponenziale.
Poi se si sia dimostrato "l'indimostrabilità polinomiale" del problema oppure semplicemente non si sia trovato algoritmo non lo so. E mi sembra che se siamo nel secondo caso il porblema si dice NP completo.
Non sono affatto sicuro di tutto questo, ho cercato un po' in rete e non ho trovato nulla.. quando avrò tempo rovisterò tra i miei fogli in cerca di quelli.. nel frattempo un link con diverse varianti del sistema e le diverse ottimizzazioni.. http://utenti.quipo.it/base5/misure/probjeep.htm
Che significa problema polinomiale?
Non ho capito se quella del marinaio semplice non è una soluzione o non è una soluzione ottimale...e poi non ho capito perchè vederle e confrontarle tutte non è un buon metodo per trovare quella ottimale:)...vedeverde parla in modo semplice!
la soluzione del marinaio semplice è una soluzione.
una soluzione è ottima se non ce n'è una migliore (rispetto al parametro che vuoi ottimizzare, per esempio la benzina spesa o i kilometri di viaggio(che dovrebbe essere uguale)).
In alcuni problemi esiste un modo per trovare la soluzione ottima senza dover controllare ogni soluzione:per esempio,se so che la soluzione ottima risolve un sistema lineare non vado ad assegnare ogni enupla possibile di soluzioni al sistema (che comutazionalmente è un costo esponenziale al variare di n, ovvero le operazioni da farsi sarebbero proporzionali al numero di valori possibili per una soluzione (che in un computer sono finite) elevato alla n).
Risolvere il sistema con uno dei tanti metodi ha un costo polinomiale invece, ovvero che le operazioni da farsi sono proporzionali a un polinomio in n (numero incognite).
Altro esempio: il problema dell'ordinamento.
Se io ho un insieme con una relazione d'ordine e voglio ordinarlo posso farlo in molti modi. Uno di certo è quello di fare tutte le n-ple possibile e trovare quelle ordinate. Il costo in questo caso è proporzionale ad n!, quindi un costo(più chè)esponenziale.
Alternativamente posso predere il primo elemento e metterlo al primo posto,poi prendere il secondo, confrontarlo con il primo, e decidere dove metterlo,in generale poi prendo un elemento e lo faccio scalare finche non lo emtto prima di uno più grande o all'ultimo. Questo algoritmo (selection sort) costa, nel caso peggiore, n^2 (come ordine).
Ora per alcuni problemi non esistono algoritmi per trovare una soluzione senza dover guardare tutte le possibilità!
Per esempio il problema dello zaino intero (mi sembra si dica così):
Hai trovato un tesoro in una caverna e hai soltanto uno zaino da riempire con oggetti di grande valore. Le pareti stanno crollando e non potrai più tornare in questo luogo perciò devi decidere adesso che cosa mettere in salvo, una volta per tutte.
Inoltre non puoi portare più di M kg di peso.
e segue una lista di oggetti, il loro peso, il loro valore.
Ecco la lista degli oggetti. Quali sceglieresti, in modo da accumulare il più alto valore possibile?
Ecco questo problema, in generale, non è risolvivibile se non considerando ogni caso e poi scegliendo il migliore.
(in realtà non è neanche proprio così grazie alla prog dinamica)
ma la soluzione a sti problemi non la sa nessuno:)??
se non si fa vivo nessuno entro due giorni sleeper e a p sono invitati a dare la loro soluzione.
scusami, approfitto di questa occasione per chiederti.. perchè chi semo?
io ho detto che già li conoscevo, the sleep lo sa, a.p. lo sa..
tu t. mi sembrava di capire lo sapessi e marinaio semplice ha proposto la sua..
chi ci manca?
Non sai...milioni di utenti affollano ogni giorno questo blog:)
in ogni modo tu li sai e vabbè, ma vuoi dare una tua soluzione o vuoi tenertela per te?
poi mi sembra che manchino delle combinazionio solo con quei cinque-sei che hai citato tu..
non ho afferrato la questione/battuta sulle combinazioni.. comunque
io so la soluzione perchè li conoscevo, uno studiato all'uni e l'altro su quei fogli di cui parlavo.. ora il lavoro di riscrivere la soluzione se permetti spetta a che l'ha proposti!! (mamma mia quanto so pigro.. o forse è che domani ho l'esame di meccanica)(corso orripilante)
Meccanica corso orripilante? Non conosco altre materie che siano concettualmente semplici, tutto sommato, ma che portino a porsi e risolvere problemi di una difficoltà disarmante.
Comunque, Monty Hall. Il modo più convincente per il popolo (apparte il buon vecchio metodo sperimentale, che però può richiedere un certo tempo), è considerare i vari casi possibili.
Supponiamo perciò che le scelte possibili siano capra1, capra2 e automobile. Supponiamo anche che il concorrente segua la strategia cambiare, perché giustamente ha letto queste soluzioni.
Se il concorrente ha inizialmente scelto capra1, il conduttore scopre capra2: il concorrente cambia, sceglie l'automobile e torna a casa contento.
Se inizialmente ha scelto capra2, il conduttore scopre capra1: il concorrente cambia e vince l'automobile.
Se inizialmente ha scelto l'automobile, il povero concorrente cambiando prende una capra, e quindi perde.
Morale: la strategia di cambiare paga 2 volte su 3.
Anche un idiota, a questo punto, si accorge che se la strategia fosse tenere, il concorrente vincerebbe 1 volta su 3. Tutte le giustificazioni in termini probabilistici rigorosi ve le trovate su internet.
Per inciso. Non trovo niente di ovvio in questa spiegazione. Non trovo niente di ovvio in nessuna delle giustificazioni che ho trovato. Ritengo ragionevole la soluzione qua sopra, anche e soprattutto perché "si verifica sperimentalmente", con i simulatori che si incontrano su internet. Far vedere è il modo migliore per convincere di un risultato "chi non frequenta la matematica", e vi assicuro che non è per niente facile.
qualcosina in più, anche storica sul prob
http://utenti.quipo.it/base5/probabil/montyhall.htm
ah e di solito quando dico corso parlo di corso, non materia.
Dopo giorni di scervellamenti infruttuosi ho letto la pagina con la soluzione del problema dell'esploratore e della jeep, postata da vedeverde.
La soluzione, però, secondo me non regge (ammesso che io l'abbia interpretata correttamente):
si dice di percorrere un primo sesto del deserto e tornare indietro, facendo avanzare così un po' di benzina, e continuare fino ad aver percorso tutto il deserto.
La soluzione, in questi termini, non regge perchè, per fare ciò, dovrei caricare ad ogni viaggio più benzina di quella consentita dal problema; a questo punto, partivo direttamente con 2 pieni senza complicarmi la vita.
Si, probabilmente ho interpretato male, poichè si dice di "depositare" ad ogni viaggio il carburante in eccesso.
Si arriva così alla soluzione del Marinaio, che reputo la migliore.
Tuttavia non mi convince perchè, da un punto di vista pratico, non mi viene detto se ho i mezzi per depositare il petrolio.
Bo. Che rompiballe che sono :)
il punto è che questo è principalmente un problema "informatico", e agli informatici non interessa se devi scavare serbatoi per depositare benzina ogni volta se questa cosa la fai in tempo costante.
Grazie, buon lavoro! Questa era la roba che dovevo avere.
Grazie, buon lavoro! Questa era la roba che dovevo avere..
Posta un commento