Две фирмы по очереди нанимают программистов, среди которых есть 4 гения. Первого программиста каждая фирма выбирает произвольно, а каждый следующий должен быть знаком с кем-то из ранее нанятых данной фирмой. Если фирма не может нанять программиста по этим правилам, она прекращает приём, а другая может продолжать. Список программистов и их знакомств заранее известен. Могут ли знакомства быть устроены так, что фирма, вступающая в игру второй, сможет нанять по крайней мере 3 гениев, как бы ни действовала первая фирма?

Выдыхай, бобер!

(0) а если предположить, что программистов всего 4 и они между друг другом знакомы все, то как тогда? Или я неправильно прочитал условия?

(2) тогда первая фирма примет 2 гениев по-любому, без всяких стратегий

надо организовать совместную конференцию. Там все участники перезнакомятся. И мы сможем нанять всех гениев

(0)
Не понял задачу. Если все 4 гения знакомы друг с другом, то первая нанимает двух гениев железно.

четыре гения организовывают франча и вуаля

А понял, есть ли такой набор знакомств.....

(5) там же написано "Могут ли знакомства быть устроены так", то есть Вам предлагается граф знаком выстроить

(5)Если все знакомы, то первая нанимает всех, так как очередь передается когда нельзя нанять следующего

А фирмы граф знают знакомств и кто гений знают?

(9) неправильно, очередь передается после каждого приема

(10) да, там же написано

(11) То есть после того, как первая фирма остановится, вторая добирает всех?

(0) если заранее известен список программистов и список знакомств, то в таком случае вторая фирма может нанять 3-х гениев только в том случае, если первая фирма выберет заранее неправильную стратегию.

+(13) Или вторая тоже может остановится и тогда оставшиеся не достаются никому?

Может

(13) нет))) 1-я набирает одного, 2-я одного, 1-я одного и т.д., кто не может - пропускает ход

если гении и негении знакомы по кольцу через одного

А не, чтоп

стоп

(17) Он один ход пропускает, или до упора?

(18) то есть всего 8 человек? первая гарантирует себе двух гениев

(0) а первая выборка совсем любого?

(21) ну после пропуска ничего же для него не меняется, значит до упора

(23) да, можно брать сразу гения

А чем на работе гении, тем более 1С, может достаточно обычных быдлокодеров?

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

(27) почему?

+(28) вопрос снят ))

можно построить схему, где первая фирма может получить троих гениев, но второй как-то не получается...

Для первой и четверых легко построить

Я думал ,Гений один...а их вон сколько,чувак руки на себя наложит

(31) четверых нереально, так как вторая может сразу гения взять

Получается, с учетом (27) каждый гений сидит в своей компоненте связности. то есть компонент минимум 4. первая фирма берет компоненту с любым гением, вторая за ход не сможет взять 3х оставшихся, значит первая фирма своим вторым ходом сможет взять второго гения...

(0) если и существует цепочка, по которой можно получить 3-х гениев, то ею может с чистой совестью воспользоваться первая фирма. поэтому - ответ - нет.

(35) выяснили, что ход передается каждый раз, а не так, как написано в (0)

(36) а как тогда? а то что-то я тогда не понимаю

+ связи каждого из 4 гениев должны быть симметричны, иначе опять же, первая фирма нарушит стратегию

(36) в (0) именно так и написано

В 0 написано "...по очереди. бла бла бла ... вторая может продолжать." Значит в бла бла бла описан один ход игры.

Можно.
Программистов должно быть всего 4.
Они знакомы все друг с другом, но через HRов второй компании. Первая компания нанимает одного и на этом всё. Остальные достаются второй компании.

(41) Я тоже так подумал, но тут есть выигрышная для первой стратегия: первая переманивает HRa, потом вторая берет гения, а первая остальных.

(41) ну если по условию с кем-то из нанятых вообще, то тогда да - единственная стратегия, что все знакомы с сотрудником другой компании, а между собой нет.

есть такая структура

(0) это из разряда игры в точки или что-то в этом роде wiki:Точки стратегия есть, нужно придумать поле на котором возможно условие из (0)

(0) Нет.
Для полноты картины нам нужно определить знакомства первого программиста с остальными, второго с третьим и четвертым и третьего с четвертым.
При этом каждый программист должен иметь хоть одно знакомство, иначе его выберут первым.
Предположим, что решение есть.
Тогда берем первого выбранного программиста, у него должна быть связь со вторым программистом, которого выберем мы.
У второго не может быть связи с третьим и четвертым, потому что иначе цепочка не прервется.
У следующего, которого мы выберем, то есть у третьего (они симметричны с четвертым, поэтому равнозначны), не может быть связи со вторым (из предыдущего шага) и с четвертым (потому что тогда цепочка не прервется). Но при этом хотя бы одна связь должна быть, поэтому остается связь с первым.
Остается определить связи четвертого программиста. С третьим связи нет. Со вторым тоже нет. Остается связь с первым.
Итого:

1-2
|\
3 4

Но это ошибочное решение, потому что можно первым выбрать второго программиста.

"а каждый следующий должен быть знаком с кем-то из ранее нанятых данной фирмой"
Имеется ввиду - должен быть знаком с кем-то из ранее нанятых ГЕНИЕВ (тех самых 4-х) данной фирмой?

(47) А, пардоньте, пропустил, что людей не четверо :))
Тогда (1) :))

(46) Научи схемы вставлять пж.

+(45) вопрос выбора количества связей, граф в котором каждая вершина связана не более чем с (3-5 подумать еще нужно) вершинами, количество вершин большое, гениев можно разбросать по углам, кто ходит первым тот проигрывает, стратегия второго захватывать вершины (перекрывать путь)  которые ведут к гениям

(44) а чем моя структура не подходит?
1 2 3 4
| | | |
сотрудник второй компании, которого приняли до этого

(51) ты начальную схему нарисуй

(49) Используй теги, описанные здесь http://www.forum.mista.ru/about.php.
Тег 1С и /1С в квадратных скобках.

(52) это и есть начальная. Все знакомы с сотрудником второй компании, в этом случае первая фирма, выбрав любого, не может продолжать набор, а вторая собирает всех.

(54) Ну может тем, что до того, как выберет первая во второй нет ни одного сотрудника?

+(55) На то она и вторая в общем то.

хм... "знаком" - симметричное понятие?
если нет то все просто

а то "А знает Б, Б знает В, В знает Г, Г знает А"... но например по книгам =)

Конструкция на пальцах

Пусть G0,G1,G2,G3 - гении
Пусть есть еще 4 программиста A0,A1,A2,A3 - особые
Пусть есть цепочки знакомств между Ai и Gj Ai=P[i,j,0]<=>P[i,j,1]<=>P[i,j,2]<=>...<=>P[i,j,K(i,j)]=Gj
где <=> - обозначает знакомство, а K(i,j)=N+[(i+j) mod 4], N - достаточно большое число, например 10, mod - остаток от деления
И пусть других программистов и знакомств нет

Если первая фирма выбирает:
1. гения, то вторая выбирает произвольного особого Ai
2. особого Ai, тогда вторая выбирает такого Aj, что расстояния до трех гениев короче к Aj чем к Ai
3. некоего P[i,j,k], тогда вторая выбирает Ai

(0) По-моему задача элементарная. Цепочка знакомств Г1-Г2-А1-Г3-Г4-А2-Г1, закольцованная. При любом первом выборе, второй игрок отсекает 3 гения.

+(60) В принципе комбинации гениев и обычных прогов могут быть любыми, лишь бы знакомства были закольцованы и не встречалось три гения подряд.

(60) нет, тут ты неправ
первая выбирает Г1, вторая вынуждена брать Г2, тогда первой достается Г4

(62) Да, действительно.

(46) Есть ещё один критерий - время. Программист может становиться со временем выдающимся, всемирно известным. Если критерий времени подключить и со временем неизвестные становятся известными, при том знакомство не обязательно обоюдное. Вот, например ,Путин. Был когда-то вам неизвестным. Но потом стал всем известным. Но никого из вас Путин не знает. А потом появился ещё один - Медведев. ТЕПЕРЬ - тоже всем известный. Но раньше Путин, возможно, не знал Медведева. Хотя Медведев уже знал путина ибо Путин уже был всемирно известным...
Тут поле для решеий дофига...

(58) Ну да, типа того..

Прием на работу по инвайтам.

.....одна фирма приняла на работу четырех Гениев1С...

+(67) В разное время, при том не знакомых друг  с другом.

+(68) и всем от 120 тыр...

И все с Нокиями3310 наперевес..

Если все четыре "гения" висят на концах цепочки знакомств, и эта цепочка замкнута в центре, то у второй фирмы есть шанс "отрубить" первую, так как она может выбирать любого программиста в первый раз.
То есть, чтобы первая проиграла, в цепочке должно быть более одного узла, в котором сходятся ветки от всех "гениев" - только тогда вторая сможет перебить,
а с точки зрения топологии это невозможно.

P.S. не очень понятно "а другая может продолжать" - то есть, если фирма может продолжить набор, когда первая "заткнулась", тогда две несвязанных цепочки с "гениями" по краям - вторая сможет нанять вторую цепочку.
Если же они "в одинаковых условиях", то такое невозможно.

P.P.S. в задаче ничего не сказано про увольнение ???

шо курим ?

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