Santannaland 1

Lo stato di Santannaland utilizza come moneta nazionale il Piso e la Banca Centrale ha deciso di stampare banconote di soltanto due tagli. Si tenga conto che:
a) tutti i beni hanno un prezzo intero, compreso tra $1$ e $100$ (estremi compresi);
b) i beni hanno prezzi uniformemente ripartiti e la stessa probabilità di essere acquistati;
c) i pagamenti vengono fatti in contanti per la cifra esatta e senza ricevere resto;
d) ogni cittadino possiede banconote dei due tagli in gran quantità, sicuramente sufficienti a fare gli acquisti.

1.Determinare la scelta dei due tagli di banconote che rende minimo in media il numero di banconote necessario per gli acquisti.
2.Discutere la questione precedente nel caso generale in cui i prezzi dei beni siano compresi tra $1$ ed $N$, con $N$ intero qualsiasi, lasciando uguale a due il numero di tagli di banconote da stampare.


Sembra facile, ma lo è meno di quel che appare

Testo nascosto, fai click qui per vederlo

$10$ o $11$

Devi minimizzare questa funzione: $\lfloor p/t \rfloor + p - \lfloor p/t \rfloor * t$ dove fissato ogni volta $t$ (il taglio della seconda banconota dato che la prima deve essere per forza di taglio unitario) fai variare il prezzo $p$ da $1$ a $P_(max)$

IMHO

Cordialmente, Alex

E in generale …

Testo nascosto, fai click qui per vederlo

… il minimo si dovrebbe ottenere quando il secondo taglio di banconote è $sqrt(N)$ perché in tal modo si equilibra il massimo numero di banconote tra i due tagli

Come è già stato detto, una delle due monete deve essere per forza 1.
Sia $p$ il prezzo di un bene, tale che $1$ $<=$ $p$ $<=$ $N$, sia $x$ il valore della seconda moneta,
allora detti $m$ e $n$ il numero di monete del primo e del secondo tipo che ci vogliono per comprare un bene, si ha che:
$m*1+n*x = p $
Definendo
$f(m,n)-= m+n = p -nx +n = (1-x)n+p$
Il problema mi chiede di minimizzare il numero medio di banconote, quindi:
$bar(f)= bar(m+n)=bar((1-x)n+p)= bar((1-x)n)+ bar(p)= (1-x)bar(n)+bar(p)$
Dove si è fatto uso delle proprietà della media.
inoltre si ha che, dall'equazione di partenza:
$bar(n)= (bar(p)-bar(m))/x$
analizziamo $bar(p)$: esso rappresenta il prezzo medio di un bene, che varia da 1 a N. la media sarà quindi:
$bar(p)= (sum_(i=1)^(N) i)/N= (N+1)/2$
analizziamo $bar(m)$: esso rappresenta il numero medio di monete che valgono 1. Quando acquisto un bene , userò un numero di monete che valgono 1 che varia tra 0 e $x-1$ ( se usassi x monete da 1 farei prima a usarne una che vale x).
quindi $bar(m)=(sum_(i=0) ^(x-1) i) / (x)= (x-1)/2$
in definitiva devo minimizzare la funzione
$bar(f(x))=(1-x)bar(n)+bar(p)=(1-x)(bar(p)-bar(m))/x+bar(p)=
=(1-x)/(x) (bar(p)-(x-1)/2) +bar(p)$
la derivata prima di questa funzione è
$(dbar(f(x)))/dx = (x^2-2bar(p)-1)/x^2 $
perciò studiandone il segno si vede che la funzione di partenza ha un minimo per
$x= sqrt(2bar(p)+1) = sqrt(N+2) $.
Nel caso $N=100$ i valori interi più vicini a $sqrt(102)$ sono 10 e 11.

Una soluzione con due sorprese.

Testo nascosto, fai click qui per vederlo

La banconota di minor valore deve valere necessariamente $ 1 $; indichiamo con $ t $ il taglio della seconda. Confrontando, al variare del numero $ n $ di oggetti, la convenienza nell'utilizzare il taglio $ t+1 $ al posto di $ t $, si trova agevolmente (senza derivate) che:
per ogni $ n>= t(t+1) $ risulta conveniente usare il taglio $ t+1 $;
per $ n<t(t+1) $ è più conveniente usare il taglio $ t $ tranne nei casi in cui la scelta non comporta alcuna differenza.
Il numero di questi valori, indifferenti per la scelta, risulta sorprendentemente elevato:
$ n<t vv n=kt-1 " "(con " " 1<k<t) vv t^2 <=n<t(t+1)-1 $.
Confrontando questi risultati al variare di $ t $ mi sono sorpreso per la seconda volta: per $ n=i(i-1)-1 (con " " i>2) $ esistono $ 3 $ valori $ t=i-1; t=i; t=i+1 $ che comportano la necessità di utilizzare il medesimo numero complessivo di monete per acquistare tutti gli $ n $ oggetti.

Assegnato $ N >1 $ per determinare il/i miglior valore di $ t $ si può calcolare $ r=sqrt(N+1) $ arrotondato per difetto e:
se $ r^2<=N+1<r(r+1) $ allora $ t=r vv t=r+1 $ indifferentemente;
se $ N=r(r+1)-1 $ allora $ t=r vv t=r+1 vv t=r+2 $ indifferentemente;
se $ r(r+1)<=N<r(r+2) $ allora $ t=r+1 $.

Ciao