118. Представьте себе граф из 1000 вершин, прону- мерованных числами от 1 до 1000 (рисовать их не нужно!). Ребро (стрелка) из вершины а в вер- шину в проводится в том случае, если а делится на в нацело. а) Сколько в этом графе петель? б) Сколько стрелок выходит из вершины 19? в) Сколько стрелок входит в вершину 1? г) Сколько стрелок входит в вершину 2? д) Сколько стрелок выходит из вершины 1000?

Рассмотрим граф из 1000 вершин, пронумерованных числами от 1 до 1000. Ребро (стрелка) из вершины $$a$$ в вершину $$b$$ проводится в том случае, если $$a$$ делится на $$b$$ нацело.

1. а) Сколько в этом графе петель?

Петля в графе - это ребро, которое ведет из вершины в саму себя. В данном случае петля из вершины $$a$$ будет, если $$a$$ делится на $$a$$. Так как любое число делится само на себя, то петля будет в каждой вершине графа. Таким образом, в графе 1000 петель.

Ответ: 1000

1. б) Сколько стрелок выходит из вершины 19?

Стрелка выходит из вершины 19 в вершину $$b$$, если 19 делится на $$b$$ нацело. Число 19 - простое число, поэтому делится только на 1 и на само себя (19). Таким образом, из вершины 19 выходит две стрелки: в вершину 1 и в вершину 19.

Ответ: 2

1. в) Сколько стрелок входит в вершину 1?

Стрелка входит в вершину 1 из вершины $$a$$, если $$a$$ делится на 1 нацело. Так как любое целое число делится на 1, то в вершину 1 входят стрелки из всех вершин графа, то есть из вершин с номерами от 1 до 1000. Таким образом, в вершину 1 входит 1000 стрелок.

Ответ: 1000

1. г) Сколько стрелок входит в вершину 2?

Стрелка входит в вершину 2 из вершины $$a$$, если $$a$$ делится на 2 нацело. Это значит, что $$a$$ - четное число. В диапазоне от 1 до 1000 находится 500 четных чисел (2, 4, 6, ..., 1000). Таким образом, в вершину 2 входит 500 стрелок.

Ответ: 500

1. д) Сколько стрелок выходит из вершины 1000?

Стрелка выходит из вершины 1000 в вершину $$b$$, если 1000 делится на $$b$$ нацело. Это значит, что $$b$$ - делитель числа 1000. Найдем все делители числа 1000.

Разложим число 1000 на простые множители: $$1000 = 2^3 \times 5^3$$.

Делители числа 1000: 1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000. Количество делителей равно (3+1)×(3+1) = 4×4 = 16.

Таким образом, из вершины 1000 выходит 16 стрелок.

Ответ: 16