Задачка

← →
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, потому что тогда супруг этой пары должен знать стольких же, скольких знает Жена Васи, что противоречит условию.

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

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

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

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

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

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

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

* 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 © (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 знакомых.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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