Везучая теща

[fortpost]

В розыгрыше главного приза телевизионной лотереи участвовало 300 человек. Они выстроились по кругу, затем, начиная с кого-то, получившего номер 1, их стали пересчитывать. При этом каждый третий всякий раз выбывал. (Так, на первом круге выбыли все с номерами, кратными 3.) Счет продолжался до тех пор, пока не остался один человек. Этот человек и получил главный приз. (Им случайно оказалась теща телережиссера.) Какой номер в первоначальной расстановке имел победитель?

[moonlight]

Показать скрытый текст

191

?

[монЯрхъ]

Хау? Хау вы это посчитали? Решение! 

[семеныч]

решение бы

 

[☭-Изделие 20Д]

Показать скрытый текст

Ну хотя бы - 200, а надёжней - 298

[fortpost]

И у меня 191. Считал с помощью сей программы.
Показать скрытый текст

Program JosivFlaviye;
Uses CRT;
Const n: integer = 300;
Type tp = ^bt;
     bt = record
          inf: integer;
          lnk: tp;
          off: Boolean;
          End;
Var t, top: tp;
    f: tp;
    i:integer;
    k: integer;
    o: integer;

Procedure Print;
Begin
f := t;
For i := 1 to n do
    Begin
    Write(f^.inf,' ');
    f := f^.lnk;
    End;
End;

Procedure Schet(s: Byte);
Begin
t := top;
For o := 1 to n - 1 do
    Begin
    i := 1;
    Repeat
    If (t^.off = False) then inc(i);
    t := t^.lnk;
    Until (i = k) and (t^.off = False);
    Writeln('Вычеркнули ',t^.inf);
    t^.off := True;
    End;
End;

Begin
ClrScr;
top := nil;
For i := n downto 1 do
    Begin
    t := New(tp);
    t^.inf := i;
    t^.lnk := top;
    t^.off := False;
    top := t;
    End;
f := t;
For i := 1 to n-1 do
    Begin
    f := f^.lnk;
    End;
f^.lnk := t;
Print;
Write(#13#10,'До скольки считать: '); Readln(k);
Schet(k);
While (t^.off = True) do
      t := t^.lnk;
Writeln('Остался  ',t^.inf);
ReadKey;
End.

[fortpost]

А можно посчитать экспериментально. Одна девочка написала: «Мой папа командир полка. Он выстроил по кругу 300 солдат и приказал им пересчитаться в соответствии с  условием. Остался солдат под номером 191 . Он помог мне решить остальные задачи олимпиады, так как окончил 2 курса  математического факультета».

[семеныч]

тогда решите такую-же

У Васи день рождения такой:
365 дней.Выбрасываем каждое пятое число пока и не останется 1 день - день рождения Васи

это будет какое число какого месяца??

[kiwi]

У меня вышел 86-й день, то есть 26 марта
Правда, вероятность, что я в ходе вычёркиваний ошиблась, ОООчень велика...

[Seamew]

ну должен же быть какой-то алгоритм... на 1-ом, 2-ом шаге симметрию нашла..
а дальше никак((

[kiwi]

Я делала тупо: сказали вычеркивать - окай, будем вычёркивать

[Seamew]

ну это одноразовый подход.. должна же быть общая формула для расчета любого набора цифр

[fortpost]

После долгих и сложных расчетов получается 91 день. Ему соответствует дата 1 апреля. Зная Семёныча, приходим к выводу, что ответ правильный.

[fortpost]

ну это одноразовый подход.. должна же быть общая формула для расчета любого набора цифр

Та не так все просто. Этой задаче почти 2000 лет, и общее решение до сих пор не найдено.
Подробности здесь. //текст доступен после регистрации//

[moonlight]

Я тоже программой считал. Вот моя.

Код:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Fortpost
{
    class Program
    {
        struct A
        {
            public int pred, next;
        }

        static int F(int n, int k)
        {
            A[] mass = new A[n];
            for (int i = 0; i < n; i++)
            {
                mass[i].pred = (i == 0 ? n - 1 : i - 1);
                mass[i].next = (i == n - 1 ? 0 : i + 1);
            }
            int p = 0;
            while (mass[p].next != mass[p].pred)
            {
                int s = 0;
                while (s < k)
                {
                    p = mass[p].next;
                    s++;
                }
                mass[mass[p].pred].next = mass[p].next;
                mass[mass[p].next].pred = mass[p].pred;
            }
            return mass[p].next;
        }

        static void Main(string[] args)
        {
            Console.WriteLine(F(300, 3));
            Console.ReadLine();
        }
    }
}