martedì 13 ottobre 2009

Indovinello

Stimolato da un'intervista a Paolo Gargini segnalatami da Francesco vorrei cominciare a parlare di qualcosina che ha a che fare con la mia ricerca. E comincio da un indovinello semplice semplice.

Mario è un esperto di barbecue e adora cucinare le bistecche sulla graticola per sua moglie e suo figlio. Il suo fornellino è piccolo, e ci sta su una sola bistecca. Per cuocere un lato di una bistecca ci mette circa 3 minuti. Quindi, per cuocere 3 bistecche ci mette 18 minuti (3 minuti per ogni lato di ogni bistecca). Per ridurre l'attesa decide di comprare un altro fornellino identico, cosicché egli possa cuocere due bistecche in parallelo.

1) Qual'è il tempo minimo necessario per cuocere tutte e 3 le bistecche sui due fornellini?

2) Supponiamo di avere N bistecche e K fornellini, con N > K (ad esempio 5 bistecche su 3 fornelli). Riuscite a ricavare una formula per calcolare il tempo minimo necessario?

Le soluzioni e un po' di discussione nei prossimi post.

16 commenti:

  1. Identificando le bistecche come 1,2,3 e i lati come a,b:
    I turno: 1a, 2a
    II turno: 1b 3a
    III turno: 2b, 3b

    Totale: 9 minuti.

    La formula generale non la so: son filosofo, io!

    RispondiElimina
  2. N bistecche hanno 2N lati;
    Con K fornellini sono quindi richiesti 2N/K cotture, se 2N è multiplo di K, altrimenti un giro in più con alcuni fornellini spenti;
    Ogni cottura richiede 3 min (dai a questo punto dimentico SI);
    Quindi arrotondare all'intero superiore 2N/K e moltiplicare per 3.

    RispondiElimina
  3. ok! La soluzione al problema 2) ha un'ulteriore piccolo risvolto da discutere (a domani...)

    RispondiElimina
  4. Quando il gioco si fa duro, o meglio interessante...
    La soluzione matematica non tiene conto dei tempi di preparazione, giratura (?) e sostituzione delle bistecche, alimentazione dei fornellini, interruzioni per rispondere al cellulare, ...
    Se il problema è questo sono stato tratto in inganno dal nome: Mario è esperto e in letteratura è spesso indicato come Super Mario. Super come Superman, non come ancestore.
    Altrimenti aspetto con impazienza che arrivi domani.

    RispondiElimina
  5. Avere una bistecca e 2 fornellini vuol dire dimezzare il tempo di cottura di entrambi i lati? Magari in parallelo

    RispondiElimina
  6. @totonno: scusa ma come fai a cuocere una sola bistecca su due fornellini in parallelo? se ci riesci fammelo sapere, rivoluzioneresti il mondo del barbecue!

    RispondiElimina
  7. @juhan: beh, assumiamo tempi di giratura trascurabili.

    Aiutino: assumiamo anche che se una bistecca viene tolta dal fuoco dopo x minuti (x < 3), quando si rimette sul fuoco basta tenercela per 3-x minuti.

    (Nella realtà, se dopo 1 minuto togliamo una bistecca dal fuoco, il lato si comincia a raffreddare, e quando si rimette sul fuoco ci mette un po' di più di 2 minuti per completare la cottura perché il lato deve essere prima riportato a temperatura...)

    RispondiElimina
  8. ragionavo per assurdo e la febbre ha fatto il resto :-)

    RispondiElimina
  9. Sono troppo stanco per provarlo ma "a sentimento" mi verrebbe da dire che ci si avvicina alla soluzione con divisione tra reali, cioè T = 3*2N/K, ma ci dormo sopra.
    Caso mai torno al prossimo appello ;-)

    RispondiElimina
  10. Esempio: N=100 e K=99. Secondo la formula di juhan, ci vorrebbero 3min*2*100/99 ~ 3min*2*1.01.
    Anche volendo prendere la parte intera del rapporto 2N/K, ovvero floor(2N/K)+1, che in questo caso sarebbe 3, avremmo 3min*3=9minuti.
    Senza formule, però, la soluzione a questo problema sarebbe: metto le prime 99 bistecche sulle 99 piastre (3min), poi le giro (6min) e poi faccio l'ultima bistecca (9min) su entrambi i lati (12min). Ha ragione la formula (e cioè c'è un modo più intelligente di fare le 100 bistecche su 99 piastre in meno di 12min) oppure la formula è sbagliata? Oppure dovrei prendere il floor di N/K? Cioè 2*(floor(N/K)+1), che in questo caso saerbbe 4 e i minuti diventerebbero effettivamente 12...

    Allora, io ri-cercherei una formula come segue: anche con infinite piastre e una sola bistecca, non potrei metterci meno di 6min, perchè devo cuocere un lato alla volta. Con K piastre e N<K bistecche, posso non accendere K-N piastre, ma ci metterò sempre 6min. Se N>K dovrò per forza metterci almeno 12min: i primi 6min per cuocere le prime K bistecche e i secondi 6min per cuocere le restanti N-K. Se poi N-K>K, devo aggiungere altri 6min. E se N-K-K>K, altri 6min.
    La formula, in definitiva, mi sembra che debba essere: 6min*[(N div K)+1], dove "div" indica il quoto (cioè il risultato della divisione senza resto). Oppure, usando l'operatore "floor", la formula sarebbe: 6min*(floor(N/K)+1).

    Ehi, Knulp, c'ho preso? :)

    RispondiElimina
  11. hrorir, nel caso di 3 bistecche e 2 fornelli con la tua formula il risultato sarebbe 12 min.
    Mentre il risultato corretto mi sembra 9, come indica ivo sopra.
    Credo che questi 3 min aggiuntivi siano dovuti al fatto che non vengano fatte in parallelo le operazioni quando possono essere fatte.
    Nello specifico con la tua formula avremmo la cottura di due bistecche ( 6 min ) e dopo la cottura totale della terza su un fornello lasciandone uno vuoto. La cottura di entrambi i lati avviene in modo sequanziale e quindi impiega (3 + 3). Mentre parallelizzando le operazioni, dove si puo', riduce a 9 min il tempo necessario, come nell'esempio di ivo.

    RispondiElimina
  12. io sono per la formula:

    3min*arrotondamento all'intero superiore di 2N/K

    come diceva prima juhan

    in sostanza 3*d(N,K)

    dove d(N,K) effettua divisione 2N/K e arrotondamento all'intero successivo. d(100,90)=3
    d(1,1)=1
    d(3,2)=3

    Notte a tutti!

    RispondiElimina
  13. Stiamo trascurando il fatto della cottura parziale interrotta e poi ripresa per aumentare il parallelismo.
    Se ci fosse più tempo...
    In ogni caso bel post!
    Ben fatto Knulp :-)

    RispondiElimina
  14. Eh, sì, totonno, c'era lì l'esempio di Ivo e me lo sono completamente ignorato! :(

    RispondiElimina
  15. Non ho una mente matematica, non riesco arisolvere il problema, ma le bistecche alla griglia mi piacciono. HO DECISO: vado a comperare un altro fornellino. Dopo sei minuti mangia tutta la famiglia.
    Un allegro ciao
    Angelo

    RispondiElimina
  16. Ciao autobiogrquanto, benvenuto!
    Nel caso (improbabile!) che non te ne sia accorto, la soluzione è al post successivo:

    http://scacciamennule.blogspot.com/2009/10/di-bistecche-fornelli-e-multicore.html

    Ciao!

    RispondiElimina

Attenzione: I commenti a vecchi post potrebbero essere moderati