Пионеры и школьники

[DjD USB]

Ученики школы посещают кружки. Докажите, что можно несколько школьников принять в пионеры так, чтобы в каждом кружке был бы хотябы один пионер и для любого пионера нашелся бы кружок, в котором он был бы единственным пионером.

[Yamike2]

Индукция по кол-ву школьников:
База: 1 школьник. В этом случае, все очевидно.
Пусть имеется n школьников, тогда, либо для любого школьника найдется кружок, в который ходит только он, либо найдется школьник, с которым на каждый из кружков ходит еще некотрое количество школьников. В первом случае пионерами можно сделать всех, во втором можно убрать найденного школьника и применить предположение индукции.

[_Ivana]

Если бы я писал программу выбора кого принять в пионеры, я бы делал так: принять школьника, посещающего максимальное количество кружков, из оставшихся принять того, кто посещает максимальное количество кружков и при этом набор его кружков не совпадает с первым (так у нас будет гарантия что у каждого пионера найдется кружок где он единственен) и т.д. При таком алгоритме ещё и гарантируется минимальное количество получившихся пионеров, удовлетворяющих условию задачи.

UPD минимум пионеров не гарантируется - только что придумал контрпример, при котором алгоритм примет в пионеры не минимальное число. Но алгоритм работает. Задача поиска минимального количества пионеров может быть поставлена дополнительно.

UUPD и алгоритм тоже не работает, придумал контрпример который он отработает неверно. Начинаем думать сначала и по другому

[_Ivana]

Придумал и реализовал очередной алгоритм, но не минимизирующий количество пионеров. Если есть кружок, который посещает единственный школьник, то этого школьника край как надо принимать в пионеры, иначе кружок останется без пионера. Соответственно, все другие кружки, которые посещает этот новоявленный пионер уже будут с пионером. Получаем оставшиеся кружки, каждый из которых посещает более одного школьника. Если есть один школьник, который посещает их все - принимаем его и дело с концом. Если же нет - наступает самое интересное: убираем из рассмотрения первого попавшегося школьника до тех пор, пока снова не появится кружок, который посещает единственный школьник - и переходим к первому пункту. Собственно, произвольность убирания из рассмотрения школьников приводит к тому, что метод не минимизирует количество пионеров. На словах расписал подробно, в коде же это всего несколько строчек (учитывая то, что это Матлаб, а там есть много зашитых функций по работе с матрицами )

[_Ivana]

% строки - кружки, колонки - ученики, 1 - ученик посещает кружок, 0 - нет
A = [
     1,0,0,0,0,0,0
     1,0,0,0,0,0,0
     0,1,0,0,0,0,0
     0,1,1,0,0,0,0
     0,0,1,1,0,0,0
     0,0,0,0,1,1,0
     0,0,0,0,0,1,1
     0,0,1,0,1,0,1
     ]
% результат - массив учеников, 1 - пионер, 0 - нет
P = zeros(numel(sum(A, 1)), 1)';

while numel(A)
    % номера учеников, которых принимаем в пионеры
    nP = find( sum(A(find(sum(A, 2) == 1), :), 1) );
    % принимаем
    P(nP) = 1;
    % удаляем кружки, которые посещают вновь принятые пионеры
    A(find( sum(A(:, nP), 2) ), :) = [];
    
    S = sum(A, 1);
    if max(S) == numel(sum(A, 2))
        % принимаем в пионеры ученика, посещающего все оставшиеся кружки
        P( find(S == max(S), 1) ) = 1;
        A(:, :) = [];    
    else
        % убираем из рассмотрения первого попавшегося ученика, посещающего
        % часть оставшихся кружков
        A(:, find(S, 1)) = 0;
    end
end
P