 |
|
 |
 |
 | Карта сайта |
 | Недавние изменения |
 | Поиск |
 | Вы посетили |
 | История страницы |
 | Вход |
Различия
Здесь показаны различия между двумя версиями данной страницы.
|
marathon:problem_160 [2012/04/05 20:27] 127.0.0.1 внешнее изменение |
marathon:problem_160 [2026/10/25 18:53] (текущий) letsko |
||
|---|---|---|---|
| Строка 4: | Строка 4: | ||
| На множестве натуральных чисел от 1 до 10460353203 структура графа G задается так: | На множестве натуральных чисел от 1 до 10460353203 структура графа G задается так: | ||
| - | вершины a и b смежны тогда и только тогда, когда множества цифр в g-ичной записи чисел a и b различны при любом натуральном g \ge 2. | + | вершины a и b смежны тогда и только тогда, когда множества цифр в g-ичной записи чисел a и b различны при любом натуральном g ≥ 2. |
| Является ли G:\\ | Является ли G:\\ | ||
| a) двудольным;\\ | a) двудольным;\\ | ||
| Строка 16: | Строка 16: | ||
| Положим n = 10460353203=3<sup>21</sup>. | Положим n = 10460353203=3<sup>21</sup>. | ||
| - | Обозначим U<sub>1</sub>={2<sup>k</sup>-1|k ∈ {1,2, ..., 33}}, \ U<sub>2</sub>=V \ U<sub>1</sub>. Очевидно, что числа из U<sub>1</sub> и только они записываются в двоичной системе с помощью одних единиц. Поэтому эти 33 вершины попарно не смежны. | + | Обозначим U<sub>1</sub>={2<sup>k</sup>-1|k ∈ {1,2, ..., 33}}, \ U<sub>2</sub>=V без U<sub>1</sub>. Очевидно, что числа из U<sub>1</sub> и только они записываются в двоичной системе с помощью одних единиц. Поэтому эти 33 вершины попарно не смежны. |
| Вершины из U<sub>2</sub> в двоичной записи имеют нули и единицы. Соответственно и эти вершины попарно не смежны. Таким образом, граф двудольный. | Вершины из U<sub>2</sub> в двоичной записи имеют нули и единицы. Соответственно и эти вершины попарно не смежны. Таким образом, граф двудольный. | ||
| Строка 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) учтена в предыдущем пункте. | ||