21. Ancora monete false

[cip999]

Già, mi sa tanto di sì...

[Federico II]

Le soluzioni che avete postato sono tutte sbagliate, perché c'è una strategia anche per:

Testo nascosto:

$k>3^{n-1}$ (non dico il numero preciso).
Poi devo dire che in realtà non avete trovato la soluzione nemmeno per $k=3^{n-1}$, perché se usi le prime due pesate per vedere se la moneta falsa pesa di più o di meno di quelle vere e poi trisechi sempre alla fine ti viene $k=3^{n-2}$.

Per il procedimento che è stato postato, la dimostrazione del fatto che con $2^n$ palline è possibile è giusta, ma quella del fatto che con $2^n+1$ non è possibile è sbagliata, infatti c'è una strategia anche per $k=2^n+1$ e per altri valori (non dico fino a dove). Per il momento non dico nemmeno l'errore nel procedimento, perché darei un hint abbastanza corposo e almeno per ora preferisco di no.

[Gerald Lambeau]

Veramente per [tex]k=3^{n-1}[/tex] ripercorrendo le pesate al contrario mettiamo che dopo [tex]m[/tex] pesate (cioè [tex]3^m[/tex] monete per gruppo) hai i tre gruppi da cui eri partito che li rimetti insieme con altre due pesate, perciò [tex]m+2=n[/tex], ma le monete sono [tex]3^{m+1}=3^{n-1}[/tex], o sbaglio? Cioè con le prime due pesate sia valuti se la moneta pesa di più o di meno sia trisechi.

[Federico II]

Sì se fai le prime due pesate in modo intelligente arrivi anche a risolvere il caso $k=3^{n-1}$, ma vi ripeto che c'è una soluzione migliore...

[xXStephXx]

Era un esempio buttato lì, ovviamente si trova pure in quale gruppo sta la moneta falsa, ma non saprei quale sia il metodo migliore, se domani ho tempo provo a pensarci
Comunque volendo si arriva a $3^{n-1}$ + $qualcosina$ usando quel metodo più lasciare 2-3 monete da parte, ma immagino valga la pena cercare una soluzione che aumenti pure l'ordine di grandezza

[Federico II]

Comunque vi do un piccolo aggiornamento: $n,\ k\in\mathbb{Z^+}$, senza nessun limite minimo fissato (a parte ovviamente $k\geq2$).
(Non disperatevi, capite bene che se un ragionamento era corretto prima lo è anche adesso)

[Federico II]

Ancora nessuno che riesce a risolverlo o che ha qualche idea?

[Federico II]

Dai non è poi così difficile... se volete qualche hint o la soluzione numerica fatemi sapere.
PS: Anche gli stagisti e i veterani sono autorizzati a postare la loro soluzione se ce l'hanno

[xXStephXx]

Non so dipende da quanto sia palloso o meno trovare una soluzione esplicita

Sicuramente puoi dimostrare di non poter mettere più di $\displaystyle \frac{3^n-1}{2}$ monete. Se riesci a farlo con esattamente quelle monete in modo non brutto, dimmelo subito e potrei pure... forse...... provarci.

[Federico II]

Testo nascosto:

Sì, la soluzione è quella, e trovare un modo per farlo non è poi così brutto...