Питання-Відповідь Число трикутників
| Питання-Відповідь → Розділ «Математика, фізика, інформатика, економіка» → Тема «Кількість трикутників» |
| 1. | ArakelyanLA2 |
| 2. | SorokinaYaV2 |
| 3. | LimUI |
| 4. | SolinMV |
| 5. | StudenikinSB |
| 6. | KravishviliED |
| 7. | ShadrovaEV |
| 8. | GoryuchkinaKV |
| 9. | FridlenderMO |
| 10. | Конюхова |
| 11. | PrudnikovaAS |
| 12. | GorinaSV |
| 13. | LavrovAV8 |
| 14. | LukovskayaTS |
| 15. | AbashkinaOA |
| 16. | RudenkoUV4 |
| 17. | ShirinyanMA |
| 18. | SuvorovaEN3 |
| 19. | RuhlyadevaOL |
| 20. | IbragimovMA3 |
| 21. | GenevieveEA |
| 22. | GeginaVV |
| 23. | DorohovDV |
| 24. | KostinGV |
| 25. | BenensonEP |
| 26. | LeonovaTV |
| 27. | DavydovaKS3 |
| 28. | КузнецоваKS7 |
| 29. | MinasyanKV |
| 30. | DuvanovaVS |
| 31. | MescheryakovDV2 |
| 32. | ZalenskayaNS |
| 33. | PopovRA3 |
| 34. | AkinshinaGV |
| 35. | БуринскаяUV |
| 36. | BufetovEN |
| 37. | UglinskiiPU |
| 38. | SolovevaLM2 |
| 39. | LobanovaOA2 |
| 40. | KoshoridzeSI |
| 41. | PolkovnikovDA |
| 42. | KurdyumovAS |
| 43. | SergeiRI |
| 44. | StepanovVN |
| 45. | СовцоваНА |
| 46. | IvankovaLI |
| 47. | HamzinTM |
| 48. | ТкаченкоВН |
| 49. | TurkinaNA |
| 50. | КрасновскаяВМ |
| 51. | RomashkaMU |
| 52. | LobanovaEV2 |
| 53. | ElesinaEE |
| 54. | SolntsevaMO |
| 55. | HruschevVP |
| 56. | LyashenkoOV2 |
| 57. | PyatigorskayaEI |
| 58. | MitrofanovOD |
| 59. | MamchurVV |
| 60. | GolovinskayaTP |
| 61. | BondarenkoUM5 |
| 62. | treda_5989 |
Насправді в наведеному нижче міркуванні допущена груба помилка, яку, однак, не легко помітити (під кінець ми вкажемо на помилку).
Легко зрозуміти, що ми маємо справу з (k,n-k-1)-регулярним двоколірним графом на n вершинах (далі ми позначатимемо будь-який такий граф як G_) і нас запитують про максимальну кількість одноколірних циклів у ньому. Дивно, але незважаючи на те, що таких графів як бруду число одноколірних циклів є інваріант (тобто це число залежить лише від n і k і не залежить від конкретного (k,n-k-1)-регулярного двоколірного графа).
Легко зрозуміти, що в G_ bin(n,3) трикутних циклів (тут bin(n,3) є число поєднань з n елементів по k; я б використовував стандартне позначення, але TeX не працює). Ми порахуємо кількість одноколірних трикутних циклів.
Зауважимо, що кожному не одноколірному трикутному циклу в G_ можна єдиним чином зіставити дві пари суміжниходноколірних ребер. Припустимо, що ми знаємо кількість пар суміжних не одноколірних ребер у нашому графі, тепер треба помітити, що число різнокольорових трикутників вдвічі менше від цього числа (у кожному трикутнику рівно дві такі пари!). Знайдемо кількість цікавих для нас пар ребер. З кожної вершини виходить k ребер одного кольору і n-k-1 ребер іншого, отже кожна вершина бере участь у k(n-k-1) різнокольорових парах. Усього вершин n, означає аналізованих нами пар k(n-k-1)n штук. Значить не одноколірних трикутників k(n-k-1)n/2 штук, а одноколірних bin(n,3)-k(n-k-1)n/2 штук (можливо, очевидні випадки n = 0,1,2 слід розібрати окремо, а може і наведена формула годиться; мені ліньки перевіряти).