геометрия - Сколько вершин останутся незакрашенными?

Question

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

DocentI 10.0k●4●21●52 · Accepted Answer

2

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

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

ссылка

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

DocentI
10.0k●4●21●52

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

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

Да, конечно.

(15 Ноя '12 17:52) DocentI

umv 16●2 · Answer 2

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

umv
16●2

изменен 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

геометрия - Сколько вершин останутся незакрашенными?

2 ответа

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

Связанные исследования

Связанные вопросы

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