Користувач:Дядько Ігор/Задачі

Хто тримає зебру?

Формулювання задачі

• Є п'ять будинків.
• У кожного будинку унікальний колір.
• Власники всіх будинків різних національностей.
• У всіх різні тварини.
• Всі п'ють різні напої.
• Всі смалять різні сигарети.
• Англієць живе у червоному будинку.
• У шведа є пес.
• Данець п'є чай.
• Зелений будинок стоїть лівіше від білого.
• У зеленому будинку п'ють каву.
• Чоловік, що смалить Pall-Mall тримає пташок.
• У жовтому будинку смалять Dunhill.
• В середньому будинку п'ють молоко.
• Норвежець живе у першому будинку.
• Чоловік, що смалить Blend живе у будинку поруч із будинком, де тримають котів.
• У будинку поруч з будинком, де тримають коня, смалять Dunhill.
• Чоловік, що смалить Blue Master п'є пиво.
• Німець смалить Prince.
• Норвежець живе у будинку поряд із блакитним.
• У будинку, що розташований поряд із будинком, де смалять Blend, п'ють воду.
• Питання: хто тримає зебру?

Позначення

Вводимо булеву алгебру для задачі.

Проіндексуємо будинки від 1 до 5. Властивість будинку позначатимемо великою літерою, його номер нижнім індексом, значення властивості - верхнім індексом.

Властивість	Позначення	Значення
Колір будинку	H	r - червоний, b - блакитний, g - зелений, y - жовтий, w - білий
Національність власника	N	n - норвежець, e - англієць, g - німець, d - данець, s - швед
Напій	D	m - молоко, w - вода, b - пиво, t - чай, c - кава
Тварини	P	d - пес, z - зебра, b - пташки, c - коти, h - кінь
Сигарети	S	b - Blend, pm- Pall-Mall, p- Prince, bm- Blue Master, d- Dunhill

Використовуючи ці позначення ми можемо записати твердження $Y_{i}^{k}$, яке означає, що властивість $Y$ $i$-го будинку приймає значення $k$. Це твердження може бути істинним або хибним. Якщо твердження істинне можна записати

$Y_{i}^{k}=1$.

Вилучення варіантів

Наше завдання переписати умови задачі за допомогою запроваджених позначень.

Перші п'ять умов - умови унікальності, тому справедливо

$Y_{i}^{k}Y_{j}^{k}=0,\qquad i\neq j$,

що простою мовою означає - два різні будинки не можуть мати однакову властивість, наприклад, не можуть бути водночас червоними, або заселеними шведами.

Для будинків також можна записати

$Y_{i}^{k}Y_{i}^{p}=0,\qquad k\neq p$

що означає, що дві властивості одного роду не можуть належати до одного будинку: англієць і данець не можуть мешкати одночасно в одному будинку (тільки в цій задачі).

Ці умови можна використати для вилучення членів із будь-яких інших тверджень.

Умови задачі в математичній формі

У задачі задані певні умови $C_{i}$, які приймають значення істина.

$C_{i}=1,\qquad i=1,2\dots N,$

Тут $N$ загальне число умов.

Наприклад

Англієць мешкає в червоному будинку

записується

$\sum _{i=1}^{5}N_{i}^{e}H_{i}^{r}=1.$

і читається: перший, або другий, або третій, або четвертий, або п'ятий будинок червоний і в ньому мешкає англієць.

Загальний метод розв'язку

Оскільки значення цих виразів - правда, то їхній добуток теж повинен давати правду. Виходячи з цього міркування, ми отримуємо алгоритм розв'язку. Перемножимо всі умови. Результат буде сумою добутків окремих власитвостей. Умови виключення можна застосувати для вилучення тих термів, значення яких неправда. В результаті виживуть тільки члени, які задовільняють всім умовам. Якщо пропадуть усі члени, то у задачі немає розв'язків. Якщо залишиться два або більше членів, то задача має кілька розв'язків.

Розв'язок задачі про зебру

Множення окремих тверджень можна проводити в довільному порядку, проте зручно множити так, щоб число членів не було великим.

• Норвежець живе у першому будинку.

$C_{1}=N_{1}^{n}=1.$

• Норвежець живе у будинку поряд із блакитним.

$C_{2}=\sum _{i=1}^{5}(N_{i}^{n}H_{i+1}^{b}+N_{i+1}^{n}H_{i}^{b})=1.$

Перемноживши ці дві умови, отримуємо.

$C_{1}\cdot C_{2}=N_{1}^{n}H_{2}^{b}.$

• Зелений будинок стоїть лівіше від білого.

$C_{3}=\sum _{i=1}^{4}H_{i}^{g}H_{i+1}^{w}=1.$

$\prod _{j=1}^{3}C_{j}=N_{1}^{n}H_{2}^{b}(H_{3}^{g}H_{4}^{w}+H_{4}^{g}H_{5}^{w}).$

• Англієць живе у червоному будинку.

$C_{4}=\sum _{i=1}^{5}N_{i}^{e}H_{i}^{r}=1.$

$\prod _{j=1}^{4}C_{j}=N_{1}^{n}H_{2}^{b}(H_{3}^{g}H_{4}^{w}N_{5}^{e}H_{5}^{r}+N_{3}^{e}H_{3}^{r}H_{4}^{g}H_{5}^{w}).$

• У жовтому будинку смалять Dunhill.

$C_{5}=\sum _{i=1}^{5}S_{i}^{d}H_{i}^{y}=1.$

$\prod _{j=1}^{5}C_{j}=N_{1}^{n}S_{1}^{d}H_{1}^{y}H_{2}^{b}(H_{3}^{g}H_{4}^{w}N_{5}^{e}H_{5}^{r}+N_{3}^{e}H_{3}^{r}H_{4}^{g}H_{5}^{w}).$

• У будинку поруч з будинком, де тримають коня, смалять Dunhill.

$C_{6}=\sum _{i=1}^{4}(P_{i}^{h}S_{i+1}^{d}+P_{i+1}^{h}S_{i}^{d})=1.$

$\prod _{j=1}^{6}C_{j}=N_{1}^{n}S_{1}^{d}H_{1}^{y}H_{2}^{b}P_{2}^{h}(H_{3}^{g}H_{4}^{w}N_{5}^{e}H_{5}^{r}+N_{3}^{e}H_{3}^{r}H_{4}^{g}H_{5}^{w}).$

• У зеленому будинку п'ють каву.

$C_{7}=\sum _{i=1}^{5}H_{i}^{g}D_{i}^{c}=1.$

$\prod _{j=1}^{7}C_{j}=N_{1}^{n}S_{1}^{d}H_{1}^{y}H_{2}^{b}P_{2}^{h}(H_{3}^{g}D_{3}^{c}H_{4}^{w}N_{4}^{e}H_{5}^{r}+N_{3}^{e}H_{3}^{r}H_{4}^{g}D_{4}^{c}H_{5}^{w}).$

• У середньому будинку п'ють молоко.

$C_{8}=D_{3}^{m}=1.$

$\prod _{j=1}^{8}C_{j}=N_{1}^{n}S_{1}^{d}H_{1}^{y}H_{2}^{b}P_{2}^{h}N_{3}^{e}H_{3}^{r}D_{3}^{m}H_{4}^{g}D_{4}^{c}H_{5}^{w}.$

$\prod _{j=1}^{8}C_{j}=T(H)N_{1}^{n}S_{1}^{d}P_{2}^{h}N_{3}^{e}D_{3}^{m}D_{4}^{c}$

де

$T(H)=H_{1}^{y}H_{2}^{b}H_{3}^{r}H_{4}^{g}H_{5}^{w};$

Тепер кольори всіх будинків визначені.

• Данець п'є чай.

$C_{9}=\sum _{i=1}^{5}N_{i}^{d}D_{i}^{t}=1.$

$\prod _{j=1}^{9}C_{j}=T(H)N_{1}^{n}S_{1}^{d}P_{2}^{h}N_{3}^{e}D_{3}^{m}D_{4}^{c}(N_{2}^{d}D_{2}^{t}+N_{5}^{d}D_{5}^{t}).$

• У шведа є пес.

$C_{10}=\sum _{i=1}^{5}N_{i}^{s}P_{i}^{d}=1.$

$\prod _{j=1}^{10}C_{j}=T(H)N_{1}^{n}S_{1}^{d}P_{2}^{h}N_{3}^{e}D_{3}^{m}D_{4}^{c}\times (N_{2}^{d}D_{2}^{t}N_{4}^{s}P_{4}^{d}+N_{2}^{d}D_{2}^{t}N_{5}^{s}P_{5}^{d}+N_{4}^{s}P_{4}^{d}N_{5}^{d}D_{5}^{t}).$

• Німець смалить Prince.

$C_{11}=\sum _{i=1}^{5}N_{i}^{g}S_{i}^{p}=1.$

$\prod _{j=1}^{11}C_{j}=T(H)N_{1}^{n}S_{1}^{d}P_{2}^{h}N_{3}^{e}D_{3}^{m}D_{4}^{c}\times (N_{2}^{d}D_{2}^{t}N_{4}^{s}P_{4}^{d}N_{5}^{g}S_{5}^{p}+N_{2}^{d}D_{2}^{t}N_{4}^{g}S_{4}^{p}N_{5}^{s}P_{5}^{d}+N_{2}^{g}S_{2}^{p}N_{4}^{s}P_{4}^{d}N_{5}^{d}D_{5}^{t})$

• Чоловік, який смалить Blue Master, п'є пиво.

$C_{12}=\sum _{i=1}^{5}S_{i}^{bm}D_{i}^{b}=1.$

$\prod _{j=1}^{12}C_{j}=T(H)N_{1}^{n}S_{1}^{d}P_{2}^{h}N_{2}^{d}D_{2}^{t}N_{3}^{e}D_{3}^{m}D_{4}^{c}N_{4}^{g}S_{4}^{p}N_{5}^{s}P_{5}^{d}S_{5}^{bm}D_{5}^{b}.$

$\prod _{j=1}^{12}C_{j}=T(H)T(N)S_{1}^{d}P_{2}^{h}D_{2}^{t}D_{3}^{m}D_{4}^{c}S_{4}^{p}P_{5}^{d}S_{5}^{bm}D_{5}^{b}.$

де

$T(N)=N_{1}^{n}N_{2}^{d}N_{3}^{e}N_{4}^{g}N_{5}^{s}.$

Національності власників усіх будинків визначено.

• У будинку, що розташований поряд із будинком, де смалять Blend, п'ють воду.

$C_{13}=\sum _{i=1}^{4}(D_{i}^{w}S_{i+1}^{b}+D_{i+1}^{w}S_{i}^{b})=1.$

$\prod _{j=1}^{13}C_{j}=T(H)T(N)T(D)S_{1}^{d}P_{2}^{h}S_{2}^{b}S_{4}^{p}P_{5}^{d}S_{5}^{bm}.$

де

$T(D)=D_{1}^{w}D_{2}^{t}D_{3}^{m}D_{4}^{c}D_{5}^{b}.$

Напої, які вживають у всіх будинках, визначено.

• Чоловік, що смалить Pell-Mell, тримає пташок.

$C_{14}=\sum _{i=1}^{5}S_{i}^{pm}P_{i}^{b}=1.$

$\prod _{j=1}^{14}C_{j}=T(H)T(N)T(D)T(S)P_{2}^{h}P_{3}^{b}P_{5}^{d}.$

де

$T(S)=S_{1}^{d}S_{2}^{b}S_{3}^{pm}S_{4}^{p}S_{5}^{bm}.$

Визначено сорт сигарет для кожного будинку.

• Чоловік, що смалить Blend живе у будинку поруч із будинком, де тримають котів.

$C_{15}=\sum _{i=1}^{4}(S_{i}^{b}P_{i+1}^{c}+S_{i+1}^{b}P_{i}^{c})=1.$

$\prod _{j=1}^{15}C_{j}=T(H)T(N)T(D)T(S)P_{1}^{c}P_{2}^{h}P_{3}^{b}P_{5}^{d}.$

• Хтось тримає зебру.

$C_{16}=\sum _{i=1}^{5}P_{i}^{z}=1.$

$\prod _{j=1}^{16}C_{j}=T(H)T(N)T(D)T(S)P_{1}^{c}P_{2}^{h}P_{3}^{b}P_{4}^{z}P_{5}^{d}.$

Задача розв'язана. Роз'язок можна помістити в таблицю

Номер будинку	Колір	Національність	Сигарети	Напій	Тварини
1	жовтий	норвежець	Dunhill	вода	коти
2	блакитний	данець	Blend	чай	кінь
3	червоний	англієць	Pall Mall	молоко	птахи
1	зелений	німець	Prince	кава	зебра
1	білий	швед	Blue Master	пиво	пес

Доволі цікавий варіант розв'язання. Чи не міг би ти додати його в статтю Задача Ейнштейна, бо мені трохи складно зрозуміти поки що його суть?--Kovelman 13:21, 3 липня 2010 (UTC)

Це дуже формалізований варіант. Я не думаю, що він годиться для вікіпедії, тому пропоную його для вікіпідручника. --Дядько Ігор 13:29, 3 липня 2010 (UTC)

Задача про блакитнооких

Поміщу тут розв'язок задачі про блакитнооких теж. Думаю, що всі вже розв'язали.

Теорема. Будь-яке число блакитнооких N, може визначити колір своїх очей за N днів.

Доведення. Методом математичної індукції.

Крок 1. Для N = 1. Один блакитноокий одразу ж визначить колір своїх очей, оскільки він не бачить жодного іншого блакитноокого, а, отже, блакитноокий саме він.

Крок 2. Припустимо, що твердження теореми справедливе. Докажемо його для N+1. В цьому випадку кожен блакитноокий бачить N блакитнооких. Якщо, після N днів вони не змогли визначити колір своїх очей (тобто не здійснили сеппуку), то їх число дорівнює N+1 - N, яких блакитноокий бачить + він сам.