Дружелюбный город

mansur · Сообщение **mansur** » 04 окт 2011, 11:11

Жителями города натуральных чисел являются натуральные числа.
Каждый житель может быть другом или недругом для каждого другого жителя этого города.
Назовем город дружелюбным, если у двух натуральных чисел этого города найдется общий друг тогда и только тогда, когда одно натуральное число делится на другое.

Может ли город, жителями которого являются только числа 1, 2, . . . , 2011, быть дружелюбным?

vicvolf · Сообщение **vicvolf** » 04 окт 2011, 12:00

mansur писал(а):Source of the post
Назовем город дружелюбным, если у двух натуральных чисел этого города

Только у двух или любых двух?

MrDindows · Сообщение **MrDindows** » 04 окт 2011, 12:17

vicvolf писал(а):Source of the post
mansur писал(а):Source of the post
Назовем город дружелюбным, если у двух натуральных чисел этого города

Только у двух или любых двух?

у любых

mansur · Сообщение **mansur** » 04 окт 2011, 12:46

Клянусь, что это легкая задача. В одну строчку решается.

MrDindows · Сообщение **MrDindows** » 04 окт 2011, 13:42

mansur писал(а):Source of the post
Клянусь, что это легкая задача. В одну строчку решается.

Ну у меня не в одну, но решение простое:
Очевидно, что из любых двух чисел, которые дружат с единицей, одно делится на другое. Назовём все эти числа множеством А. Наибольшее такое множество: 2, 4, 8... 1024. (итого 10 чисел).
Так как все натуральные числа делятся на единицу, а значит имеют с ней общего друга, то каждое нат. число дружит с неким числом из множества А.
Ясно, что два простых числа не могут иметь общих друзей, а значит каждое число из множества А дружит не более чем с один простым числом.
А так как простых чисел до 2011 намного больше чем 8, то это не возможно.

mansur · Сообщение **mansur** » 04 окт 2011, 14:05

MrDindows писал(а):Source of the post
mansur писал(а):Source of the post
Клянусь, что это легкая задача. В одну строчку решается.

Ну у меня не в одну, но решение простое:
Очевидно, что из любых двух чисел, которые дружат с единицей, одно делится на другое. Назовём все эти числа множеством А. Наибольшее такое множество: 2, 4, 8... 1024. (итого 8 чисел).
Так как все натуральные числа делятся на единицу, а значит имеют с ней общего друга, то каждое нат. число дружит с неким числом из множества А.
Ясно, что два по у ростых числа не могут иметь общих друзей, а значит каждое число из множества А дружит не более чем с один простым числом.
А так как простых чисел до 2011 намного больше чем 8, то это не возможно.

У меня немного иначе.
Назовем двоюродным другом того, кто является другом друга.
Ни у кого не может быть более 11 друзей, в значит и более 121 двоюродных друзей.
Но у числа 1 должно быть ровно 2010 двоюродных друзей - противоречие.

MrDindows · Сообщение **MrDindows** » 04 окт 2011, 14:54

mansur · Сообщение **mansur** » 04 окт 2011, 15:06

MrDindows писал(а):Source of the post
DEL

У меня правильное решение?
Если да, то ставлю другой вопрос - при каком максимальном n город с жителями 1, 2, ... n может быть дружелюбным?

MrDindows · Сообщение **MrDindows** » 04 окт 2011, 17:25

mansur писал(а):Source of the post
MrDindows писал(а):Source of the post
DEL

У меня правильное решение?
Если да, то ставлю другой вопрос - при каком максимальном n город с жителями 1, 2, ... n может быть дружелюбным?

При

mansur · Сообщение **mansur** » 04 окт 2011, 17:29

MrDindows писал(а):Source of the post
mansur писал(а):Source of the post
MrDindows писал(а):Source of the post
DEL

У меня правильное решение?
Если да, то ставлю другой вопрос - при каком максимальном n город с жителями 1, 2, ... n может быть дружелюбным?

При

Почему?

yourdomain.com