Dificultăți digitale | R-BLOGGERS

(Acest articol a fost publicat pentru prima dată pe R funcționeazăși a contribuit cu drag la R-Bloggers). (Puteți raporta problema despre conținutul de pe această pagină aici)

Doriți să vă împărtășiți conținutul pe R-Bloggers? Faceți clic aici dacă aveți un blog sau aici dacă nu.

Iată un alt puzzle, de la Henry Dudeney Perplexități coloană în Revista StrandIanuarie 1924.

Aranjați cele zece cifre, 1 2 3 4 5 6 7 8 9 0, astfel încât acestea să formeze un număr care poate fi împărțit la fiecare număr de la 2 la 18, fără în orice caz, un rest. Ca exemplu, dacă le aranjez astfel: 1 2 7 4 9 5 3 6 8 0, acest număr poate fi împărțit la 2,3,4,5, etc.

Una dintre provocările suplimentare în luarea de puzzle-uri din aceste surse mai vechi este să încerci să le rezolv așa cum ar fi avut un solver de puzzle, în 1924. În acest caz, nu am reușit să găsesc o soluție pură de hârtie și creion, dar am găsit o soluție modernă elegantă, care ar fi fost posibilă cu mașinile de calcul ale ERA.

Dar înainte să vă arăt soluția mea, încercați -o singur, mai întâi! Soluția mea după Matematicienii.

Matematicienii, Chirico (1917) Sursa: Wikiart — Matematicienii, Chirico (1917)

Soluţie

Să ne uităm mai întâi la o soluție de forță super brută și apoi la una mai elegantă, dar încă nu este destul de hârtie și creion.

Soluția de forță brută

Cu un computer modern, s -ar putea genera pur și simplu toate 3.628.800 de permutări posibile ale celor zece cifre. Apoi, pentru fiecare permutare, verificați dacă este divizibil de toate numerele întregi de la 2 la 18. Acest lucru este brutal, dar funcționează.

De asemenea, putem reduce numărul de permutări, profitând de unele fapte despre divizibilitate.

Un număr este:

divizibil cu 10 (și 5) dacă ultima cifră este 0
Divisibil cu 4 (și 2) dacă ultimele două cifre sunt un număr divizibil cu 4 (a se vedea apendicele pentru o explicație rapidă a de ce).

Combinând aceste fapte, putem deduce că ultimele două cifre ale numărului nostru țintă trebuie să fie 20, 40, 60 sau 80. Aceasta pleacă (pentru fiecare caz), 40.320 de permutări, oferindu -ne în total 40320 = 161.280 candidați pentru a examina. Acesta este un număr mult mai mic!

O soluție modernă elegantă

Iată o soluție care reduce și mai mult numărul de candidați. De data aceasta, vom începe prin găsirea celui mai mic număr, acest lucru este divizibil de către toți numerele întregi de la 2 la 18. Știm că numărul nostru țintă trebuie să fie un multiplu din . În continuare, găsim toți multiplii în intervalul corespunzător și verificați care dintre ele au zece cifre unice. Acestea vor fi soluțiile.

Să codificăm această soluție, în R.

Găsiți cel mai puțin comun multiplu (LCM) de numere întregi de la 2 la 18

Vom începe prin a înmulți toate primele din gama noastră:

m = 2 * 3 * 5 * 7 * 11 * 13 * 17
m

Rețineți că acest număr este divizibil și de 6=2*3, 10=2*5, 14=2*7și 15=3*5. Ce factori au mai rămas? Pentru a salva problemele de a urmări acest lucru de mână, vom scrie o funcție pentru a returna care numere întregi în intervalul 2:18 un număr m este nu divizibil de.

not_divisible_by = function(m) {
  candidates = 2:18
  
  remainders = m %% candidates
  candidates(remainders != 0)
}

not_divisible_by(m)

Dacă ne înmulțim în continuare cu alți 3, va fi apoi divizibil cu 9 și 18. Dacă atunci vom înmulți și Până la 4, va fi divizibil cu 4, 8 și 12. Aceasta lasă 16, ceea ce înseamnă că avem nevoie de încă 2.

# 3 and 4, first
m = m * 3 * 4
not_divisible_by(m)

# now an extra 2
m = m * 2
not_divisible_by(m)

Acest lucru ne oferă m = 12252240, care ar trebui să fie cel mai mic număr divizibil de toți întregi de la 2 la 18. Numărul pe care îl dorim trebuie, prin urmare, să fie un multiplu din m.

Filtrează toți multipii de

Acum trebuie să

Găsiți toți multipii în intervalul corespunzător
Găsiți toate numerele rezultate care au zece cifre unice

În primul rând, vom găsi gama de candidați.

# the smallest possible candidate
minC = 1234567890

# the largest possible candidate
maxC = 9876543210

# the range of multipliers to consider
crange = round(c(minC, maxC) / m)
crange

Acest lucru lasă 706 candidați să verifice, ceea ce este mult mai puțin de 161.280. Știm deja că toți acești candidați sunt divizibili de către toți numerele întregi de la 2 la 18; Trebuie doar să verificăm care sunt un număr format din zece cifre unice.

Deci, să scriem filtrul și să facem calculul:

ten_unique_digits = function(nint) {
  nstring = as.character(nint)
  if (nchar(nstring) != 10)
    return(FALSE)
  
  # create a vector of digits
  digits = unlist(strsplit(nstring, split = ""))
  
  length(unique(digits)) == length(digits)
}


candidates = m * crange(1):crange(2)
cfilter = vapply(candidates, ten_unique_digits, logical(1))

solns = candidates(cfilter)
solns

(1) 2438195760 3785942160 4753869120 4876391520

Există 4 soluții! Să verificăm manual că toate soluțiile sunt valabile.

for(s in solns) {
  print(paste("Checking solution", s))
  for (i in 2:18) {
    stopifnot(s %% i == 0)
  }
  print("--- Checks out")
}

(1) "Checking solution 2438195760"
(1) "--- Checks out"
(1) "Checking solution 3785942160"
(1) "--- Checks out"
(1) "Checking solution 4753869120"
(1) "--- Checks out"
(1) "Checking solution 4876391520"
(1) "--- Checks out"

# let's also find the multipliers
solns / m

Și am terminat! ✅

Dar cum ar rezolva Dudeney asta?

Este ușor de găsit LCM a numerelor întregi de la 2 la 18, cu creion și hârtie. Dar mi-e greu să-mi imaginez că un solver de puzzle în 1924 ar fi dispus să calculeze multiplii candidați de De mână pentru a găsi una cu zece cifre unice. Chiar dacă au început la 101m Și și -au lucrat drumul, ar trebui să verifice 199 – 101 + 1 = 99 de candidați înainte de a găsi o soluție. Nu mai sună distractiv.

Din fericire, chiar și în 1924, s-ar putea ca un-solver sofisticat de puzzle (precum Dudeney) să nu fie nevoie să facă calculul pur și simplu prin creion și hârtie. Aceștia ar fi putut folosi un calculator mecanic al epocii, cum ar fi aritmometrul de mai jos:

Odhner Arithmos, tip 5, circa 1912-1928. Sursa: Wikipedia

Cu un astfel de dispozitiv, un solver de puzzle ar putea literalmente multipli de scanând fiecare în timp ce merg, respingând valorile cu cifre repetate, până când descoperă o soluție la puzzle. Îmi imaginez că s -ar putea face în mai puțin de zece minute – ceea ce nu ar fi considerat mult timp pentru cineva obișnuit cu mai multe calcule manuale.

Puteți citi mai multe despre tehnologiile de calcul mai vechi în articolul lui John Mount, Calcularea la scara creionului și hârtiei.

Unul dintre descendenții aritmometrului este calculatorul Curta, iar noi la Win Vector se întâmplă să avem unul! Rezolvarea acestei probleme cu o Curta ar fi mult ca rezolvarea acesteia cu un aritmometru. Iată un videoclip cu John Mount „Găsirea” cea mai mică soluție a puzzle -ului:

https://www.youtube.com/watch?v=khis7nirdqi

Soluția descoperită este în zona neagră și multiplu asociat al este în zona albă. Rețineți că John știa deja câți manivele trebuie să facă înainte de a apărea o soluție, iar după primele două sau trei manivele, a încetat să verifice cifrele duplicate. Deci, probabil că este puțin mai rapid decât ar fi nevoie de cineva care nu știa cu adevărat care a fost răspunsul.

Acum că știu despre aritmometru și dispozitivele conexe, nu sunt prea îngrijorat dacă Dudeney mi -ar fi putut executa soluția. Dar îmi pare rău pentru orice sărac Revista Strand Cititorii care nu aveau cea mai recentă tehnologie de calcul. Și tot mă întreb dacă îmi lipsește un truc și mai inteligent, ceea ce ar fi făcut acest solvabil doar cu creion și hârtie. Dacă voi găsi vreodată o astfel de soluție, o voi posta aici la Puzzle Corner. Și dacă găsiți vreodată unul, vă rugăm să scrieți și să ne anunțați!

Apendicele: divizibilitate cu 4

Un număr este divizibil cu 4 dacă ultimele două cifre sunt divizibile cu 4.

Lasă să fie numărul inițial și să fie numărul format din ultimele două cifre. Apoi este un număr care este divizibil cu 100. Deoarece 100 este divizibil cu 4, la fel și este . Prin urmare, este divizibil cu 4 dacă este.