Brescia, gennaio 2006

Logica, probabilità e combinatoria:
Soluzione del problema 8

Sia $a_1,a_2,\ldots,a_n$ una successione arbitraria di interi positivi. Si prenda a caso un elemento della successione e sia $a$ il suo valore. Si prenda a caso un altro elemento, indipendentemente dal primo e sia $b$ il suo valore. Poi un terzo, di valore $c$. Dimostrare che la probabilità che $a+b+c$ sia divisibile per $3$ è almeno $\frac{1}{4}$.

Dimostrazione

Data la sequenza $a_1,a_2,\ldots,a_n$ con $a_i \in \mathbb{N}$, scegliamo in modo casuale tre elementi di valore $a,b,c$. Vogliamo calcolare la probabilità che

$$a+b+c \equiv 0 \pmod 3.$$

Siano:
$p$ la probabilità di un intero positivo di essere congruo a $0$ modulo $3$;
$q$ la probabilità di un intero positivo di essere congruo a $1$ modulo $3$;
$r$ la probabilità di un intero positivo di essere congruo a $2$ modulo $3$.
Perché sia $a+b+c \equiv 0 \pmod 3$, deve verificarsi uno dei due casi:

1. $a \equiv b \equiv c \pmod3 \textrm{ oppure }$
2. $a \not\equiv b \not\equiv c \not\equiv a \pmod3$

1. La probabilità che $(a \equiv b \equiv c \equiv 0 \pmod3)$ è $p^3$,
   la probabilità che $(a \equiv b \equiv c \equiv 1 \pmod3)$ è $q^3$,
   la probabilità che $(a \equiv b \equiv c \equiv 2 \pmod3)$ è $r^3$.
   Quindi la probabilità che $( a \equiv b \equiv c \pmod3)$ è $p^3+q^3+r^3$.
   
2. I casi favorevoli sono $6$:

   -

   $a \equiv 0$, $b \equiv 1$, $c \equiv 2$;

   -

   $a \equiv 0$, $b \equiv 2$, $c \equiv 1$;

   -

   $a \equiv 1$, $b \equiv 0$, $c \equiv 2$;

   -

   $a \equiv 1$, $b \equiv 2$, $c \equiv 0$;

   -

   $a \equiv 2$, $b \equiv 1$, $c \equiv 0$;

   -

   $a \equiv 2$, $b \equiv 0$, $c \equiv 1$;

   Ognuno di essi ha probabilità $p \cdot q \cdot r$. In totale allora: $6 \cdot p \cdot q \cdot r$

Resta da vedere che $p^3+q^3+r^3+6pqr \geq \frac{1}{4}$.
Poiché $p+q+r=1$, si ha:

$$1=(p+q+r)^3=p^3+q^3+r^3+6pqr+3(p^2q+pq^2+p^2r+pr^2+q^2r+qr^2).$$

Quindi bisogna dimostrare la seguente disuguaglianza:

$$p^2q+pq^2+p^2r+pr^2+q^2r+qr^2 \leq \frac{1}{4},$$

che equivale a:

$$p^2(q+r)+p(q^2+r^2)+qr(q+r) \leq \frac{1}{4}.$$

Equivalentemente, ricordando che $p+q+r=1$:

$$p^2(1-p)+p(q+r)^2+qr(q+r-2p) \leq \frac{1}{4},$$

$$p^2(1-p)+p(1-p)^2+qr(1-3p) \leq \frac{1}{4},$$

$$p(1-p)+qr(1-3p) \leq \frac{1}{4}.$$

Se $p \geq \frac{1}{3}$, allora

$$p(1-p)+qr(1-3p)$$

è massimo per $qr=0$ e $p=\frac{1}{2}$. In questo modo si ha

$$p(1-p)+qr(1-3p)=\frac{1}{4}, \textrm{con }$$

$p=\frac{1}{2}$, $q=\frac{1}{2}$ e $r=0$, oppure

$p=\frac{1}{2}$, $q=0$ e $r=\frac{1}{2}.$

Per simmetria, non si perde di generalità se si suppone $p \geq q \geq r$, per cui dev'essere $p \geq \frac{1}{3}$. Allora il valore minimo di $p^3+q^3+r^3+6pqr$ è $\frac{1}{4}$.

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002 (1.62)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 -no_antialias_text Pb8.tex

The translation was initiated by DMF Web on 2006-01-10