Вершины 2500-угольника занумерованы от 1 до 2500. Начиная с первой, закрашивается каждая 35-тая вершина (1, 36, 71 и т.д.). Вершины закрашиваются до тех пор, пока не окажется, что все вершины, которые требуется закрасить уже найдены. Сколько вершин останутся незакрашенными?

задан 14 Ноя '12 21:47

изменен 16 Ноя '12 20:41

Deleted's gravatar image


126

Что значит "которые требуется закрасить"? В чем состоит это "требование"?

(14 Ноя '12 23:22) DocentI

а если та же самая задача, но 2000-угольник и закрашивается каждая 12 вершина, то сколько вершин останутся не закрашенными?

(16 Ноя '12 15:46) Art_2610

@danny_leonov, не нужно удалять вопросы. Если Вы получили исчерпывающий ответ и не желаете узнать новых вариантов, то следует их закрывать.

(16 Ноя '12 20:44) Deleted

@Art_2610, замените 5 на НОД(2000, 12) = 4.

(16 Ноя '12 23:55) DocentI
10|600 символов нужно символов осталось
2

Не очень понятны слова "вершины, которые требуется закрасить". Никакого "требования" не высказано. Может, надо понимать это так: процесс останавливается тогда, когда перестают появляться новые закрашенные вершины? Если так, задача относится к теории чисел.

Пусть вершина с номером k закрашена на круге с номером n + 1, n > 0. Тогда ее номер, отсчитанный по кругу, есть $%2500n + k$%. Он должен иметь вид $%35m + 1$%. Получаем равенство $%k-1=35m - 2500n$%. Из теории диофантовых уравнений известно, что уравнения такого вида разрешимы для всех $%k-1$%, делящихся на НОД(35, 2500) = 5. Итак, закрашена будет каждая пятая вершина, т.е. всего 500 штук.

ссылка

отвечен 15 Ноя '12 15:03

Т.е. останутся незакрашенными 2000 вершин?

(15 Ноя '12 16:58) danny_leonov

Да, конечно.

(15 Ноя '12 17:52) DocentI
10|600 символов нужно символов осталось
0
var 
i,j,k: integer;
a:array[1..2500] of integer;
begin
j:=1;
k:=0;
for i:=1 to 2500 do a[i]:=0;-все незакрашены
while a[j]=0 do - только для незакрашенных
  begin
  a[j]:=1;-закрашиваем
  j:=j+35;
  if j>2500 then j:=j-2500;
  end;
for i:=1 to 2500 do
if a[i]<>0 then k:=k+1
writeln("Количество не закрашенных вершин", 2500-k);
end.
ссылка

отвечен 15 Ноя '12 11:48

изменен 16 Ноя '12 20:47

Во-первых, почему 3500, а не 2500? Во-вторых, Вы считаете один цикл. Но для этого не нужно писать программу, достаточно разделить 2500 на 35 и округлить в большую сторону. Если уж пишете программу, то нужно организовать массив вершин, помечать окрашенные (например, присваивать 1), остановить цикл при попадании на уже окрашенную вершину и после этого подсчитать количество нулей и единиц в массиве.

(15 Ноя '12 15:05) Андрей Юрьевич

В условии ничего не говориться про закрашивание по второму кругу

(15 Ноя '12 20:57) umv

Оно вообще сформулировано плохо. Но можно догадаться. Если бы не надо было идти по второму кругу, зачем вообще располагать вершину по кругу? Можно на прямой. И в этом случае не будет никакой задачи: надо будет просто найти частное.

(15 Ноя '12 21:21) DocentI

И что получилось в результате? Что сказал компьютер?

(16 Ноя '12 15:52) Андрей Юрьевич

2000 Но математически получилось красиво. Я бы не додумался.

(16 Ноя '12 20:56) umv

@umv, эта задача легкая только для тех, что специально занимается олимпиадами. У меня, например, стаж почти 40 лет...

(16 Ноя '12 23:57) DocentI
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,331
×791

задан
14 Ноя '12 21:47

показан
1525 раз

обновлен
16 Ноя '12 23:57

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru