Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2010.08.27;
Скачать: CL | DM;

Вниз

Задачка   Найти похожие ветки 

 
Kerk ©   (2010-02-04 23:10) [0]

Никак не пойму как решить вот такую задачку.
(ответ я знаю, но не понимаю почему он такой)

И так, условие:
В комнате 7 семейных пар (т.е. 14 человек). Знакомы они между собой согласно следующим условиям:
1) Супруги знакомы
2) Если A знает B, то и B знает A
3) Никто не знаком сам с собой

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

Вопрос: сколько человек знает жена Васи?


 
Kerk ©   (2010-02-04 23:19) [1]

Интуитивно чувствую, что надо раскручивать ситуацию от того, что каждый в группе 13ти автоматически увеличивает на единицу количество знакомых своего супруга, а жена Васи не увеличивает, т.к. Вася за пределами группы 13ти.


 
жена   (2010-02-05 00:49) [2]

жена Васи знает 1 чел.
правильно?


 
Kerk ©   (2010-02-05 00:59) [3]


> жена   (05.02.10 00:49) [2]
>
> жена Васи знает 1 чел.
> правильно?

Не правильно.
Жена Васи знает самого Васю (правило 1). Если она больше никого не знает, то и ее никто не знает (правило 2). В таком случае не сходится условие "из 13 опрошенных человек каждый знает разное количество людей", ибо никто не будет знать всех 13 человек.


 
ProgRAMmer Dimonych ©   (2010-02-05 01:24) [4]

Ответ случайно не 12?


 
Kerk ©   (2010-02-05 01:27) [5]


> ProgRAMmer Dimonych ©   (05.02.10 01:24) [4]
>
> Ответ случайно не 12?

Почему 12? Объяснение давай :)
Ответ, который мне сказали, не 12. Но я не могу перепроверить, т.к. не знаю принципа решения, так что давайте представим, что ответа я не знаю.


 
ProgRAMmer Dimonych ©   (2010-02-05 01:37) [6]

Уже не дам. Мысль, которая вертелась в голове, когда меня потянуло отписать предположение, улетучилась быстро, а сейчас смотрю и вижу, что ответ - любое натуральное число, кроме 1 и 13 :(


 
ProgRAMmer Dimonych ©   (2010-02-05 02:04) [7]

Ответ: 7. Могу объяснить, кажется... Ещё минутки 2 подумаю только :)


 
ProgRAMmer Dimonych ©   (2010-02-05 02:22) [8]

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

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


Пара        М      Ж
1          *1     13
2           2      2
3           2      2
4           2      2
5           2      2
6           2      2
Вася        2      2


Пойдём от бОльших чисел. Помним, что человек 1М не может быть ни с кем знаком (это отмечено *). Может ли Жена Васи знать 12 человек? Двоих она уже знает: 1Ж и ВасяМ. Остаётся как раз ещё 10 человек. Но! Если она перезнакомится с ними со всеми, то для каждого из тех, у кого сейчас 2 знакомства (кроме Жены), знакомств станет 3. У Жены их будет 12, а Вася не считается. Т.е. получится, что нет числа 2. Вот эта ситуация:


Пара        М      Ж
1          *1     13
2           3      3
3           3      3
4           3      3
5           3      3
6           3      3
Вася        2     12


Значит, 12 знакомых у кого-то из пар 2-6. Для определённости пусть это будет человек 2Ж. Причёи из этих 12 получатся двое - это 2М (супруг) и 1Ж ("знаток"). Сама с собой и с 1М она не познакомится, так что знакомства будут установлены со всеми представителями семейных пар 3-6:


Пара        М      Ж
1          *1     13
2           2     12
3           3      3
4           3      3
5           3      3
6           3      3
Вася        3      3


Продолжаем рассуждать. Теперь попробуем сделать Жену Васи знакомой с 11 человеками. Трое - это Вася, 1Ж и 2Ж. Ещё 8 человек - это представители пар 3-6. Но тогда, как и в прошлом случае, не останется числа 3 ни у кого, кроме Васи, который нас не спасёт. Значит, Жена Васи не может быть знакома с 11 человеками и это кто-то из пар 3-6. Для определённости пусть будет 3Ж. Рассуждая как и на предыдущем шаге, приходим к выводу, что 3Ж (муж) может быть тогда знаком только с 3-мя:


Пара        М      Ж
1          *1     13
2           2     12
3           3     11
4           4      4
5           4      4
6           4      4
Вася        4      4


Дальше всё аналогично, приведу просто промежуточные таблицы:


Пара        М      Ж
1          *1     13
2           2     12
3           3     11
4           4     10
5           5      5
6           5      5
Вася        5      5



Пара        М      Ж
1          *1     13
2           2     12
3           3     11
4           4     10
5           5      9
6           6      6
Вася        6      6



Пара        М      Ж
1          *1     13
2           2     12
3           3     11
4           4     10
5           5      9
6           6      8
Вася        7      7


Задача, кажется, решена :)


 
Kerk ©   (2010-02-05 02:43) [9]

Похоже, что так :)
Вот этого я почему-то сразу не сообразил:

> Значит, из оставшихся 12 человек всех может знать только
> супруг(а) этого "знающего одного"


 
ProgRAMmer Dimonych ©   (2010-02-05 02:51) [10]

Это-то как раз самое сложное было. Почему нельзя Жене знать 12 человек понял через пару минут после того, как ответ про 12 написал. Потом пытался прикинуть, может ли она знать двоих. В общем, чего только не было там, в головушке. Дядюшке Фрейду и не снилось. А так, если ошибок нет, то, кажется, общее решение записать тож несложно. Для произвольного N семейных пар...


 
ProgRAMmer Dimonych ©   (2010-02-05 02:53) [11]

А откуда, кстать, задачка?


 
Kerk ©   (2010-02-05 03:37) [12]


> ProgRAMmer Dimonych ©   (05.02.10 02:53) [11]
>
> А откуда, кстать, задачка?

На собеседовании была.


 
J_f_S ©   (2010-02-05 04:43) [13]

>На собеседовании была.
SPb Software house& ;-)


 
Kerk ©   (2010-02-05 04:44) [14]


> J_f_S ©   (05.02.10 04:43) [13]

Нет, но вообще я эту тему комментировать не буду, чтоб не сглазить :)


 
brother ©   (2010-02-05 04:48) [15]

> комментировать не буду, чтоб не сглазить

на собеседовании гоняли? ;)


 
Kerk ©   (2010-02-05 08:28) [16]


> brother ©   (05.02.10 04:48) [15]
>
> на собеседовании гоняли? ;)

Да в принципе не особо. Мне даже понравилось :)


 
brother ©   (2010-02-05 08:35) [17]

> Мне даже понравилось :)

лучше, шоб на собеседования ты больше не ходил)


 
Sha ©   (2010-02-05 14:32) [18]

ProgRAMmer Dimonych  [8]

Теперь заметим, что Васей может быть любой из М и даже любая из Ж.

Поэтому единственное, что можно утверждать:
если Вася знаком с N человек, то супруг(а) Васи знаком(а) с 14-N человек.


 
ProgRAMmer Dimonych ©   (2010-02-05 14:45) [19]


> [18] Sha ©   (05.02.10 14:32)
> Теперь заметим, что Васей может быть любой из М и даже любая
> из Ж.

Эм-м-м, смелое утверждение. Секс-меньшинства, когда (если) придут к власти Вам этого не забудут, премию выпишут ;)


> Поэтому единственное, что можно утверждать:
> если Вася знаком с N человек, то супруг(а) Васи знаком(а)
> с 14-N человек.

Если я нигде не ступил, то количество знакомых у Васи и его Жены всегда будет одинаковым и равным общему количеству семейных пар. Сейчас ещё прикину, сколько у них будет общих знакомых, - и будем дальше их подкалывать :)


 
Sha ©   (2010-02-05 14:59) [20]

> ProgRAMmer Dimonych
> количество знакомых у Васи и его Жены всегда будет одинаковым и равным общему количеству семейных пар

Даже если в каждая супружеская пара состоит из Василия и Василисы?
Любой из этих 14 Васей удовлетворяет условию задачи и вполне мог ходить с опросным листом.


 
ProgRAMmer Dimonych ©   (2010-02-05 15:03) [21]

> [20] Sha ©   (05.02.10 14:59)
> Даже если в каждая супружеская пара состоит из Василия и
> Василисы?

Об таких раскладах я не думал :)


> Любой из этих 14 Васей удовлетворяет условию задачи и вполне
> мог ходить с опросным листом.

Еп-пископ Кондратий! Всё, моск будет зохаван сваренным :) Главное - чтобы они там промеж собой разобрались, кто кому жена...


 
Kerk ©   (2010-02-05 16:48) [22]

Да, как-то печально все вышло.
Пока что получается, что нет решения, либо описанный подход неверен.


 
ProgRAMmer Dimonych ©   (2010-02-05 17:00) [23]

Стоп!.. Так ответ другой, что ли?


 
tesseract ©   (2010-02-05 17:07) [24]

По моим прикидкам - если кто то знает одного стороннего человека - он автоматом знает минимум трёх. Правило 2 + правило 3.


1 2 3 4 5  6  7   - пары
1 3 5 7 9 11 13  - количество знакомых.  


13 или 1  быть вместе не может . И тогда задачка решения как-бы не имеет - Вася жену тоже опрашивал. Если бы не опрашивал - ответ сам собой - 11. Хотя может быть и 1.


 
tesseract ©   (2010-02-05 17:07) [25]

Хотя нет,  чет не то.


 
Kerk ©   (2010-02-05 17:17) [26]


> ProgRAMmer Dimonych ©   (05.02.10 17:00) [23]

Ответ не другой, но sha понятно показал, что с описанным подходом ответ реально N и 14-N.


 
Kerk ©   (2010-02-05 17:20) [27]

Хотя нет, все верно.
Даже если представить, что все 14 человек ходят с опросным листом, то есть еще условие "у всех 13 разное количество знакомых" и под него него подходит только один человек.


 
ProgRAMmer Dimonych ©   (2010-02-05 17:23) [28]

Тогда советую вернуться к описанию решения и попытаться ещё раз разобраться, как получается, что Жена Васи не может знать 13 человек, и почему если 13 человек знает 1Ж, то одного человека знает обязательно 1М. И следующий этап, где получается 12 и 2. Если я не туплю и ничего не упускаю, то Жена Васи знакомится до тех пор, пока мы не разберёмся со всеми остальными.

Ответы 14-N и N справедливы для любой семейной пары. Фишка в том, что если мы утверждаем, что Жена Васи знает N человек, то никто из 6 обычных пар не может знать 14-N, потому что тогда супруг этой пары должен знать стольких же, скольких знает Жена Васи, что противоречит условию.

Как-то так, хоть и путанно :(


 
ProgRAMmer Dimonych ©   (2010-02-05 17:24) [29]

Ну, собственно, я есколько опоздал с постом :)


 
tesseract ©   (2010-02-05 17:34) [30]


> и под него него подходит только один человек.


Вася себя не спрашивал. Значит он может повторяться в выборке:-) Но это по борту - он то может знать от одного до 13 без проблем.

Ж и М тут по барабану.


 
Kerk ©   (2010-02-05 17:46) [31]


> tesseract ©   (05.02.10 17:34) [30]
>
> > и под него него подходит только один человек.
>
> Вася себя не спрашивал. Значит он может повторяться в выборке:
> -) Но это по борту - он то может знать от одного до 13 без
> проблем.

Ну да. Именно поэтому с точки зрения всех остальных не будет в комнате у всех разное количество знакомых.


 
12 ©   (2010-02-05 19:32) [32]

* 123456789ABCD!

1 *1111111111111
2 1*000000000000
3 10*11111111111
4 101*0000000000
5 1010*111111111
6 10101*00000000
7 101010*1111111
8 1010101*000000
9 10101010*11111
A 101010101*0000
B 1010101010*111
C 10101010101*00
D 101010101010*1
!  1010101010101*

! - Вася, D - его жена
по 7


 
ProgRAMmer Dimonych ©   (2010-02-05 19:37) [33]

Правильность построения видна. Подход к построению чисто эвристический или есть какой-то подход? (Меня всё беспокоит общее решения для класса задач)


 
Стенка ©   (2010-02-06 10:14) [34]

> ProgRAMmer Dimonych ©   (05.02.10 19:37) [33]

В твоем подходе не хватает самой малости.
На каждом шаге надо попутно доказывать, что наш Вася не входит в отсекаемую супружескую пару. Тогда он будет обязан войти в последнюю. И все.

Обозначим через N количество супружеских пар. В случае N=1 решение задачи очевидно. Решим ее для N>1.

Очевидно, каждый из 2N присутствующих имеет не менее 1 знакомого (своего  супруга) и не более 2N-1 (всех кроме себя). Значит, ровно у двух присутствующих одинаковое число знакомых, и наш Вася – один из этих двоих, т.к. по результатам его опроса совпадений не обнаружено. А это возможно только в том случае, когда Вася не опрашивал сам себя (что вполне естественно).

Теперь рассмотрим супружескую пару, в которой есть супруг А, имеющий единственного знакомого – своего супруга B. Предположим, что супруг B имеет K знакомых, причем 1<=K<=2N-2. В этом случае один из оставшихся присутствующих должен иметь 2N-1 знакомых, т.е. быть знаком со всеми, включая A. Но это противоречит нашему предположении. Значит A имеет 1 знакомого, B имеет K=2N-1 знакомых, а остальные от 2 до 2N-2.

Заметим, что наш Вася не входит в только что рассмотренную супружескую пару. Т.к. если Вася – это А, то среди оставшихся должен быть C, знакомый только со своим супругом D, у которого 2N-1 знакомых, и тогда мы имеем двойное повторение количества знакомых. А если Вася – это B, то среди оставшихся должен быть E, также знакомый со всеми присутствующими и общее число знакомых  составит (1+(2N-1))*N+(2N-1)=2N^2+2N-1. А это нечетное число, и такого быть не может, т.к. каждое знакомство существует между двумя людьми.

Теперь давайте попросим удалиться супругов A и B из комнаты. В комнате у нас останется наш Вася, N-1 супружеских пар, и та же задача (если считать знакомых только в пределах комнаты). Повторяя процесс далее, мы оставим в комнате только Васю с супругой. При каждом удалении (а их было N-1) они теряли по одному общему знакомому, ну и, конечно, они знакомы друг с другом. Значит, они имеют по N знакомых.


 
ProgRAMmer Dimonych ©   (2010-02-06 13:17) [35]

> [34] Стенка ©   (06.02.10 10:14)

Вчитался, вник. Теперь как-то стройнее выглядит.

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


 
Стенка ©   (2010-02-06 17:04) [36]

На графе это выглядит совсем просто.

Супружеская пара изображается парой точек, одна под другой. Cледующую супружескую пару рисуем правее предыдущей. Правило соединения точек простое: каждую точку верхнего ряда соединяем со всеми точками левее нее и точкой, расположенной непосредственно под ней.

Левая пара точек - Вася и его жена.


 
Стенка ©   (2010-02-06 17:40) [37]

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

0123456789ABCDE
101111111111111
210111111111110
311011111111100
411101111111000
511110111110000
611111011100000
711111101000000
811111110000000
911111100000000
A11111000000000
B11110000000000
C11100000000000
D11000000000000
Е10000000000000

7 и 8 - Вася с супругой.


 
dmk ©   (2010-02-06 20:19) [38]

3) Никто не знаком сам с собой

Мне это условие похоже на ошибку деления на ноль :-) IMHO все знакомы друг с другом :-)


 
Стенка ©   (2010-02-06 20:34) [39]

> dmk ©   (06.02.10 20:19) [38]
> 3) Никто не знаком сам с собой
> Мне это условие похоже на ошибку деления на ноль :-)

Ну, можно пойти чуть дальше и спросить: "сколько раз знаком?"  )


 
12 ©   (2010-02-08 09:10) [40]


> Правильность построения видна

Все просто.
Начинаем избавляться от больших чисел, маленькие приткнуть легче
Начинаем с 13ти знакомых, далее предполагал, что следующий - супруг, следовательно, 1, иначе никак.
Потом 12, и 2 и т.д.

>> Если нумеровать точки верхнего ряда справа налево,
а вот если супруга первого поставить последним - действительно, вывглядит красивее



Страницы: 1 2 вся ветка

Текущий архив: 2010.08.27;
Скачать: CL | DM;

Наверх




Память: 0.59 MB
Время: 0.146 c
15-1265377108
vovko26
2010-02-05 16:38
2010.08.27
С чего начать?


15-1272738123
Pavia
2010-05-01 22:22
2010.08.27
утечка конфиденцальных данных


3-1239892608
Сантропе
2009-04-16 18:36
2010.08.27
Подскажите утилиту для работы с PARADOX


2-1274357365
Nucer
2010-05-20 16:09
2010.08.27
Значок в ресурсе


2-1270481004
Fantasy
2010-04-05 19:23
2010.08.27
Shortcut на рабочем столе. Проблема с функцией GetDir(0,sPath);