Algoritmul lui Dyson pentru problema celor douăsprezece monede

Algoritmul lui Dyson

Algoritmul lui Dyson rezolvă de fapt o versiune mai generală a problemei monedelor:

Aveți monede, la apariția exact identice; dar, eventual, unul este contrafăcut (o să-l numim un „dud”). Nu știi dacă un dud este prezent și nici dacă este mai greu sau mai ușor decât monedele bune. Poti determina in cântăriri pe o cântar: (1) dacă există un dud, (2) dacă da, care monedă și (3) greutatea ei relativă (mai ușoară sau mai grea decât monedele bune)?

Dyson arată că cel mai mare număr de monede care se poate rezolva în cântăririle este . Adică 3 monede în 2 cântăriri, 12 monede în 3 cântăriri, 39 de monede în 4 cântăriri și așa mai departe. Algoritmul pe care îl voi arăta în această postare rezolvă cazul în care aveți exact monede. Voi discuta cazul general în care într-un articol următor.

Ideea de bază a algoritmului lui Dyson este să eticheteze fiecare monedă după reprezentarea sa trinară și apoi să programeze cântăririle în așa fel încât, cu reprezentarea adecvată a rezultatelor măsurătorilor, cântăririle „scriu” eticheta monedei dud, dacă există. Există o etichetă cunoscută pentru cazul în care nu există greșeală.

Algoritmul original al lui Dyson a folosit reprezentări standard de bază 3, unde cifrele sunt (0, 1, 2). Am decis să implementez versiunea mea folosind trinar semnat, unde cifrele sunt (-1, 0, 1). Aceasta este reprezentarea pe care am folosit-o pentru puzzle-ul cu patru greutăți și mi se pare mai naturală pentru problemele cântarelor. Ca bonus, face și algoritmul lui Dyson mai ușor de descris.

Algoritmul

Voi descrie procedura cu exemplul (3 monede, 2 cântăriri), deoarece este ușor de rezolvat manual. Apoi vă voi indica un cod pentru cazuri mai mari.

1: Etichetați monedele cu numerele de la 1 la și convertiți-le în trinar semnat folosind cifre. Am descris mai înainte procedura de conversie în trinar semnat, aici. Pentru arata cam asa:

1 = (0 1)
2 = (1 -1)
3 = (1 0)

2: Setați reprezentările trinare să se rotească „înainte”.

Spunem că un număr în baza 3 se rotește „înainte” (Dyson l-a numit „în sensul acelor de ceasornic”) dacă prima schimbare de cifre crește cu 1, modulo 3. Deci succesiunea înainte este (Rețineți că și ). În R, arată cam așa, presupunând că ați implementat numărul de bază 3 ca vector:

is_forward = function (ptrinary) {
  delta = diff(ptrinary)
  # get only the nonzero diffs
  delta = delta(!(delta==0))

  if(length(delta)==0)
    stop("constant vector")

  # check if we are rotating forward, and return
  delta(1) %% 3 == 1
}

Dacă un număr trinar semnat se rotește înainte, apoi negație se rotește înapoi și invers. Deci înlocuiți oricare dintre etichetele monedelor care se rotesc înapoi cu negarea sa:

1 = (0 1) : rotates forward
2 = (1 -1): rotates forward
3 = (1 0): rotates backward, so replace with (-1 0) (-3)

Reprezentarea tuturor monedelor cu numere care se rotesc înainte elimină ambiguitatea care apare din faptul că nu se știe dacă moneda dud este mai grea sau mai ușoară decât monedele bune: dacă balanța înclină panoul din stânga în jos, asta ar putea fi din cauză că un dud greu este în stânga. tigaie, sau pentru că în tigaia din dreapta se află un dud mai ușor. După cum vom vedea, setarea tuturor etichetelor monedelor să se rotească înainte înseamnă că o greșeală grea va produce un model de comportamente care „exclude” locația etichetei, în timp ce o greșeală ușoară va explica negația etichetei.

3: Planificați programul de cântărire.

Acum haideți să etichetăm pozițiile posibile pe (sau în afara) cântarului. înseamnă tigaia din stânga, înseamnă tigaia potrivită și înseamnă masa. Programul de cântărire este astfel încât pentru Cântărirea, o monedă dată se află în locația descrisă de eticheta ei a-a cifră (numărând de la stânga, deci cifra celor este ultima). Pentru exemplul nostru, acesta oferă programul:

1 = (0 1): table, then right pan
2 = (1 -1): right pan, then left pan
3 = (-1 0): left pan, then table

Folosind notația pe scară pe care am folosit-o pentru problemele de echilibru, arată astfel:

First weighing:

(coin 3 | coin 2)
------------------
coin 1

Second weighing:

(coin 2 | coin 1)
-----------------
coin 3

Rețineți că programul de cântărire poate fi calculat în avans dacă știți (şi ), chiar înainte de a vedea un anumit set de monede. De asemenea, poate fi folosit din nou și din nou, pentru orice set de monede. Aceasta este ceea ce ne referim când numim acest algoritm „inutil”.

4: Cântăriți monedele conform programului

Vom înregistra rezultatul fiecărei cântăriri, ca tigaie a fost mai grea (daca exista): înseamnă că tigaia din stânga este mai grea, înseamnă că tigaia dreaptă este mai grea, înseamnă că cântarul este echilibrat. Aceasta înseamnă că dacă Moneda este o greșeală grea, își va scrie propria etichetă în trinar semnat, ca . O greșeală ușoară va explica negarea etichetei. Puteți recupera reprezentarea zecimală a rezultatului final, ca

Atunci locația răului este iar dud-ul este greu dacă se rotește înainte și este ușor dacă se rotește înapoi. Dacă nu există greșeală, atunci .

Rețineți că semnul de NU este dacă dud-ul este greu sau ușor; este dacă reprezentarea trinară originală a rotit înainte sau înapoi.

Și asta este! Să trecem prin câteva exemple.

• Fără greșeală
  • Scala: (echilibrat, echilibrat), deci : nu prost
• Dud-ul este moneda 1 și este ușor
  • Scala: (echilibrat, stânga), deci şi se rotește înapoi: monedă 1, lumină.
• Rasul este moneda 2 și este greu
  • Scară: (dreapta, stânga), deci şi se rotește înainte: moneda 2, grea.
• Rasul este moneda 3 și este greu
  • Scala: (stânga, echilibrată), deci şi se rotește înainte: moneda 3, grea.

Înapoi la cele 12 monede

Așa că acum putem rezolva problema la care ne pasă de fapt. S-ar putea face manual, dar codul este mai ușor. Am codul R pentru cazul special aici.

Să arătăm reprezentările înainte ale monedelor.

source("dyson_signed_specialcase.R")

nrounds = 3
ncoins = (3^nrounds - 3)/2  # 12

# Show the forward representations of the coins
get_forward_representation(nrounds)

      (,1) (,2) (,3)
 (1,)    0    0    1
 (2,)    0    1   -1
 (3,)    0    1    0
 (4,)    0    1    1
 (5,)    1   -1   -1
 (6,)    1   -1    0
 (7,)    1   -1    1
 (8,)   -1    0    1
 (9,)   -1    0    0
(10,)   -1    0   -1
(11,)    1    1   -1
(12,)   -1   -1    0

În implementarea mea, precompilez programul de cântărire din timp, astfel încât să pot cântări monede din nou și din nou. The precompile apeluri de funcții get_forward_representation intern și returnează o listă. Fiecare element al listei este programul de cântărire pentru acea cântărire, ca un cadru de date, cu coloane (left, table, right). Fiecare coloană a cadrului de date conține monedele care intră în acea poziție pentru acea cântărire.

Cset = precompile(ncoins, nrounds)

# show the schedule 
knitr::kable(Cset((1)), caption = "Weighing 1")

knitr::kable(Cset((2)), caption = "Weighing 2")

knitr::kable(Cset((3)), caption = "Weighing 3")

Acum putem găsi prostii. Nu contează cât cântăresc monedele, atâta timp cât toate monedele bune cântăresc aceeași cantitate. Funcția mea find_dud returnează o valoare D astfel încât abs(D) dă indicele dudului și sign(D) dă greutatea relativă a dud-ului; negativ înseamnă că dud-ul este ușor, iar pozitiv înseamnă că dud-ul este greu. Cu alte cuvinte, !! Dar notația este concisă și ușor de scris cecuri pentru.

# a good coin weighs 1 unit
coins = numeric(ncoins) + 1
epsilon = 0.5

# check the no dud case
find_dud(coins, Cset)

# check a specific case
idud = 7
relative_wt = -1 # make it lighter
coins(idud) = 1 + epsilon*relative_wt
find_dud(coins, Cset)

# verify this works in all possible cases
for(idud in 1:ncoins) {
  for(relative_wt in c(-1, 1)) {
    actual = idud*relative_wt # location and direction
    coins = numeric(ncoins) + 1
    coins(idud) = 1 + epsilon*relative_wt
    A = find_dud(coins, Cset)
    stopifnot(actual==A)
  }
}

Și aceasta este soluția monede în problema cântăririlor, pentru cazul special când . În următoarea postare, voi descrie cazul general, când .

Nina Zumel este un cercetător de date cu sediul în San Francisco, cu peste 20 de ani de experiență în învățarea automată, statistică și analiză. Ea este co-fondatoare a firmei de consultanță în știința datelor Win-Vector LLC și (împreună cu John Mount) co-autoarea cărții Practical Data Science cu R, aflată la a doua ediție.