“Se dă \(N\), în câte moduri putem plasa \(2\) cai pe o tablă de șah de \(N\) pe \(N\) astfel încât să nu se atace?” (cai3859)
Problema la prima vedere pare grea, putem deduce că este nevoie de o formulă după tag-ul “FORMULA”, dar care este formula aceasta?
Conform indicațiilor, formula este :
\(\frac{{(n−4)}^{2}({n}^{2}-9)+4(n−4)({n}^{2}-7) +4(n-3)({n}^{2}-5)+8({n}^{2}-4)+4({n}^{2}-3)}{2}\)
Pare grea, așa-i? Putem cumva să o facem mai ușoară de atât?
Răspunsul la a 2-a întrebare este, da, putem să o facem mult mai ușoară de atât, și nu cu simplificări matematice, ci cu deduceri care sunt logice odată ce le înțelegi!
În primul rand, putem observa ceva, în momentul în care 2 cai se atacă se formează un dreptunghi de \(2\times3\) sau de \(3\times2\) (vezi poza 1). Sunt exact 2 feluri de a plasa cele 2 piese întrucât să se atace unul pe celălalt. Întrebarea acum devine, cum aflam cate astfel de dreptunghiuri pot să aibă loc pe tabla noastră de șah cu mărimea \(N\times N\)?
Răspunsul este formula : \((n-1)(n-2) + (n-2)(n-1)=2(n-1)(n-2)\)
În al doilea rand, deoarece avem mereu doua feluri de a pune caii, înmulțim cu \(2\) formula, din care avem : \(4(n-1)(n-2)\) din care poate rezulta numărul de poziții în care se pot ataca cei doi cai.
Întrebarea se modifică încă odată, acum devenind, cum aflam răspunsul problemei?
Răspunsul problemei devine ușor odată ce ai realizat formula \(4(n-1)(n-2)\)!
Pentru început, avem \(\frac{{n}^{2}({n}^{2}- 1) }{2}\) total combinații în care putem să punem cei doi cai, tot ce facem este să scădem numărul de poziții din care cei doi se ataca din numărul total de combinații.
Așadar, lo and behold, formula din \(\frac{{(n−4)}^{2}({n}^{2}-9)+4(n−4)({n}^{2}-7) +4(n-3)({n}^{2}-5)+8({n}^{2}-4)+4({n}^{2}-3)}{2}\) devine \(\frac{{n}^{2}({n}^{2}- 1) }{2}-4(n-1)(n-2)\)!
Acum o implementare în c++ devine ușoară, dar trebuie să avem multa grija deoarece sunt cazuri care trec peste limita \(int\), așa că vom pune înainte de ambele elemente (long long). O cale de a face este în modul acesta: cout << (long long)(N*N*((N*N)-1))/2 – (long long)4*(N-1)*(N-2) << ‘\n’!
———————————————————————————————————————————————————————————————————————————-
Pop Iuliu-Daniel,
Liceul Teoretic “Eftimie Murgu”, Bozovici, 9A
Pop Iuliu-Daniel (tiwerlol)
Pop Iuliu-Daniel (tiwerlol)