(Acest articol a fost publicat pentru prima dată pe R Funcționeazăși cu amabilitate a contribuit la R-bloggeri). (Puteți raporta problema legată de conținutul acestei pagini aici)
Doriți să vă distribuiți conținutul pe R-bloggeri? dați clic aici dacă aveți un blog, sau aici dacă nu aveți.
Din articolul „Perplexities” al lui Henry Dudeney din numărul din martie 1925 al Revista Strand:
Un bărbat a intrat într-o bancă cu 1.000 de dolari de argint și 10 pungi. El a spus: „Puneți acești bani, vă rog, în pungi astfel încât, dacă sun și cer un anumit număr de dolari, să-mi puteți preda unul sau mai multe genți, oferindu-mi exact suma cerută fără a deschide niciunul dintre sacii.” Cum era de făcut? Desigur, ne preocupă doar o singură cerere, dar el poate cere orice număr exact de dolari de la 1 la 1000.
(În articolul original erau „suverani” și „lire sterline” – dar sunt în SUA, deci…)
Acest lucru este similar în spirit cu problema celor patru greutăți a lui Bachet, așa că dacă ați rezolvat-o pe aceea, cu siguranță ar trebui să o puteți rezolva pe aceasta.
Soluția este sub cea a lui Chirico Matematicienii.
Soluția
Spre deosebire de problema greutăților, combinația de pungi de aici este strict aditivă:
unde 
este numărul de monede din pungă 
și 
.
Deci, în loc de un sistem trinar, avem un vechi sistem binar bun. Asta înseamnă dacă avem 
pungi și punem 1 monedă în primul sac, 2 monede în al doilea sac, 4 monede în al doilea sac… Adică punem 
monede în ipunga, putem reprezenta orice valoare între 0 și 
.
Să arătăm asta cu 3 pungi, care ar trebui să ne dea numerele 0:7.
# fill the bags
bags = vapply(1:3, function(i) {2^(i-1)}, numeric(1))
bags
# get all the possible combinations of bags
signs = c(0,1)
S = expand.grid (s1 = signs,
s2 = signs,
s3 = signs) |>
as.matrix()
S
s1 s2 s3 (1,) 0 0 0 (2,) 1 0 0 (3,) 0 1 0 (4,) 1 1 0 (5,) 0 0 1 (6,) 1 0 1 (7,) 0 1 1 (8,) 1 1 1
# get the total number of coins for each combination as.numeric(S %*% bags)
Avem 10 pungi, deci putem reprezenta orice valoare de la 0 la 
care sunt mai multe monede decât avem noi. A zecea geantă ar trebui să țină 
monede, dar din moment ce avem 23 de monede mai puțin, va ține doar 
monede.
Deci solutia este: Primele 9 pungi țin monede pentru de la 1 la 9; iar ultima geantă are 489 de monede.
Să verificăm asta.
# fill the bags
bags = vapply(1:10, function(i) {2^(i-1)}, numeric(1))
bags(10) = 489 # the last bag is a little short.
# get all the possible combinations of bags
slist = lapply(1:10, function(i) signs)
names(slist) = paste0("bag", 1:10)
S = expand.grid (slist) |> as.matrix()
dim(S)
Rețineți că există încă 1024 de combinații de genți; știm că putem reprezenta doar numerele 0:1000, așa că unele dintre totaluri vor fi duplicate. Cu alte cuvinte, pentru unele numere, există mai multe combinații de pungi care dau aceeași sumă.
# get the total number of coins for each combination x = as.numeric(S %*% bags) # find all the unique values we can achieve x_unique = sort(unique(x)) # confirm that this gives us every value from 0 to 1000 stopifnot(x_unique==0:1000)
Așa că am îndeplinit cererea clientului, iar bancherul nu mai este perplex!
Putem merge puțin mai departe. Ce sume pot fi obținute în mai multe moduri?
x(duplicated(x))
(1) 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 (20) 508 509 510 511
Rețineți că 489 este numărul de monede din bag10, iar 511 este 
care, într-o reprezentare binară corectă, este ultimul număr care nu ar necesita bag10 pentru a îndeplini suma.
Pentru distracție, să vedem diferitele moduri de a obține x = 500:
ix = which(x==500) S(ix, )
bag1 bag2 bag3 bag4 bag5 bag6 bag7 bag8 bag9 bag10 (1,) 0 0 1 0 1 1 1 1 1 0 (2,) 1 1 0 1 0 0 0 0 0 1
Prima soluție este soluția „standard”, adică 500 codificat în binar (înapoi). A doua soluție este că ultima noastră geantă nu are numărul corect de monede în ea și, de fapt, conține mai puțin de 500 de monede. Vă puteți da seama că nu este răspunsul standard, deoarece folosim punga 1, ceea ce înseamnă că răspunsul pare a fi ciudat. Dar acest lucru se uniformizează, deoarece bag10 are un număr impar de monede în ea.
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.
