 |
|
 |
 |
 | Карта сайта |
 | Недавние изменения |
 | Поиск |
 | Вы посетили |
 | История страницы |
 | Вход |
Различия
Здесь показаны различия между двумя версиями данной страницы.
|
marathon:problem_160 [2026/10/25 18:46] letsko |
marathon:problem_160 [2026/10/25 18:53] (текущий) letsko |
||
|---|---|---|---|
| Строка 32: | Строка 32: | ||
| Среди чисел, не кратных 3, отсутствие смежности вершины a вершине 3 может быть обусловлено одной из двух причин: | Среди чисел, не кратных 3, отсутствие смежности вершины a вершине 3 может быть обусловлено одной из двух причин: | ||
| 1) множество цифр в троичной записи a равно {0,1};\\ | 1) множество цифр в троичной записи a равно {0,1};\\ | ||
| - | 2) a \in U<sub>1</sub>.\\ | + | 2) a ∈ U<sub>1</sub>.\\ |
| Легко видеть, что число вершин, удовлетворяющих условию (1) равно 2<sup>20</sup>-21. В самом деле, числа, не превосходящие n будем записывать упорядоченный набор из 21-й троичной цифры, возможно, с нулями старших разрядах (набор из одних нулей сопоставим числу 3<sup>21</sup>). Тогда в каждой позиции можно поставить либо 0, либо 1. Но в младшем разряде должна быть 1, что обеспечит отсутствие кратности 3. Это дает 2<sup>20</sup>. Остается заметить, что ровно 21 из этих чисел записывается с помощью одних единиц. | Легко видеть, что число вершин, удовлетворяющих условию (1) равно 2<sup>20</sup>-21. В самом деле, числа, не превосходящие n будем записывать упорядоченный набор из 21-й троичной цифры, возможно, с нулями старших разрядах (набор из одних нулей сопоставим числу 3<sup>21</sup>). Тогда в каждой позиции можно поставить либо 0, либо 1. Но в младшем разряде должна быть 1, что обеспечит отсутствие кратности 3. Это дает 2<sup>20</sup>. Остается заметить, что ровно 21 из этих чисел записывается с помощью одних единиц. | ||
| Вершина 2<sup>i</sup>-1 из U<sub>1</sub> кратна 3 тогда и только тогда, когда i четно. Поэтому ровно 17 вершин из U<sub>1</sub> не кратны 3. Но одна из них (31) учтена в предыдущем пункте. | Вершина 2<sup>i</sup>-1 из U<sub>1</sub> кратна 3 тогда и только тогда, когда i четно. Поэтому ровно 17 вершин из U<sub>1</sub> не кратны 3. Но одна из них (31) учтена в предыдущем пункте. | ||