Escrit per: Ramon dissabte, 26 d’octubre de 2013

Al món som, actualment i segons Google, aproximadament, 7,0464 mil milions de persones (7.046.400.000). Certament, una xifra elevadíssima, que duplica la població d'ara fa 50 anys. 

Ara bé, imagina't per un moment que cada persona del planeta té un número d'identificació personal o un "DNI mundial", començant per la persona més vella de la Terra, que té el número 0.000.000.001 i acabant pel nadó que acaba de néixer, que s'identifica amb el 7.046.400.000.

Entre el total de les persones volem trobar-ne una d'especial que, com a habitant de la Terra, tindrà el seu propi número d'identificació. Per fer-ho, anem fent preguntes successives de doble resposta (Sí o No) sobre el seu número.

Exemple: El seu número és més gran que 5.000.000.000?

Quantes preguntes creus que hem de fer, per trobar-la? 
Quin és el mètode més eficient?


Solució:
Potser hauràs pensat en 1000, 2000 o 3000 preguntes. Tanmateix, en tenim prou amb 33 preguntes per trobar una persona entre tota la població mundial.

La manera més eficient de fer-ho és coneguda com el mètode dicotòmic, i consisteix en prendre el valor mig del total ($N$) i anar fent mitjanes successives fins a trobar el número que busquem. D'aquesta manera, la primera pregunta que caldria fer és:
1. El seu número és més gran o igual que 3.523.800.000? 
$$\frac{N}{2}$$

Si la resposta és "Sí", aleshores preguntaríem:
2. El seu número és més gran o igual que 5.285.200.000? 
$$\frac{N+\frac{N}{2}}{2}=\frac{N}{2}+\frac{N}{4}$$

Si la resposta és "No", preguntarem:
3. El seu número és més gran o igual que 4.404.500.000?
$$\frac{\frac{N+\frac{N}{2}}{2}+\frac{N}{2}}{2}=\frac{N}{2}+\frac{N}{8}$$

I així successivament, fins a arribar al número que busquem. Per tant, com que en cada pas que fem reduïm el ventall de possibilitats a la meitat, el número de preguntes que haurem de fer serà:
$$2^{n}\ge7,0464·10^{9}$$
$$n\ge\frac{\log{7,0464·10^{9}}}{\log{2}}$$
$$n\ge32,71$$

Com a conclusió, tan sols caldran 33 preguntes per trobar qualsevol persona de la Terra. És més, gràcies a la potència dels ordinadors actuals, això es pot arribar a fer en poques mil·lèssimes de segons.

Mentre estava escrivint l'entrada, m'he adonat d'un detall curiós. Fixem-nos que, a  les preguntes successives "El número és més gran o igual que $x$?", podem assignar el valor 1 a la resposta "Sí" i el valor 0 a la resposta "No". D'aquesta manera, un cop hàgim acabat les preguntes obtindrem una seqüència de zeros i uns (un codi binari) que, passant-lo a decimal, ens proporcionaria el número que busquem.

Per exemple, establim $N=8=2^{3}$ (3 preguntes necessàries), i el número que busquem és el 5. Preguntarem:
- El número és més gran o igual que 4? Resposta: Sí.
1
- El número és més gran o igual que 6? Resposta: No.
10
- El número és més gran o igual que 5? Resposta: Sí
101

El número que busquem és el 5 o, el que és el mateix, l'101 en binari. Per tant, un mètode alternatiu d'identificar qualsevol persona del món és combinar 33 vegades el "Sí" i el "No" o l'1 i el 0.


Deixa un comentari

Entrada a l'atzar

El més vist

Què diuen al Twitter?

Cocociència al teu mail!

Traductor

- Copyright © CocoCiència - Powered by Blogger and Metrominimalist -