* Кражби от съседчето
Публикувано на 29 февруари 2012 в раздел Математика.
Задача 1. Иван има „a“ на брой ябълки, а Петър има „b“ на брой ябълки. Иван решил да открадне половината ябълки на Петър, а Петър решил да открадне половината ябълки на Иван. С колко ябълки са останали?
Решение: Тук няма какво да се мисли – Иван е имал „a“, изгубил е „a/2“ и е спечелил „b/2“, следователно той ще има a-a/2+b/2 = (a+b)/2. Петър пък е имал „b“, изгубил е „b/2“ и е спечелил „a/2“, следователно ще има b-b/2+a/2 = (a+b)/2
=> двамата ще имат по равно ябълки.
Задача 2. Условието е същото, както в задача 1, но кражбите са се повторили „n“ пъти. Колко ябълки са им останали?
Решение: Още след първият път са останали с поравно ябълки. Следователно от тук нататък, независимо колко пъти крадат, те ще губят (a+b)/4 и ще печелят (a+b)/4, т.е. ще си остават със същото количество ябълки.
Задача 3. Иван има „a“ на брой ябълки, Петър има „b“ на брой ябълки, а Мария има „c“ на брой ябълки. Иван решил да открадне половината ябълки на Петър и Мария, Петър решил да открадне половината ябълки на Иван и Мария, а Мария решила да открадне половината ябълки на Иван и Петър. Кражбите се повторили „n“ пъти. С колко ябълки са останали?
Решение: Ще решим задачата на две стъпки
а) Съставяне на индукционна хипотеза:
Тук нещата не са толкова прости, както в „двумерния случай“. Нека съставим таблица с първите 7 кражби:
| N | Иван | Петър | Мария |
| 0 | a | b | c |
| 1 | (b+c)/2 | (a+c)/2 | (a+b)/2 |
| 2 | (2a+b+c)/4 | (a+2b+c)/4 | (a+b+2c)/4 |
| 3 | (2a+3b+3c)/8 | (3a+2b+3c)/8 | (3a+3b+2c)/8 |
| 4 | (6a+5b+5c)/16 | (5a+6b+5c)/16 | (5a+5b+6c)/16 |
| 5 | (10a+11b+11c)/32 | (11a+10b+11c)/32 | (11a+11b+10c)/32 |
| 6 | (22a+21b+21c)/64 | (21a+22b+21c)/64 | (21a+21b+22c)/64 |
| 7 | (42a+43b+43c)/128 | (43a+42b+43c)/128 | (43a+43b+42c)/128 |
Виждаме, че наличностите са симетрични. Освен това виждаме, че все повече и повече и трите започват да клонят към (a+b+c)/3. Но колко точно ще са на „n“-тата стъпка?
Ако намерим наличностите на Иван директно можем да намерим наличностите на Петър и Мария. Знаменателят е винаги 2n, тоест ние го знаем. Виждаме също, че при Иван винаги коефициентите пред „b“ и „c“ са равни, а пред „a“ е различен. Значи е достатъчно да определим коефициентът пред „a“ и коефициентът пред „b“, за да намерим самото число. Да видим тези коефициенти (припомням, че не разглеждаме знаменателя, а само числителя на коефициента – знаменателя е познат):
| N | Коефициент пред „а“ | Коефициент пред „b“ |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 2 | 2 | 1 |
| 3 | 2 | 3 |
| 4 | 6 | 5 |
| 5 | 10 | 11 |
| 6 | 22 | 21 |
| 7 | 42 | 43 |
Виждаме, че коефициентът пред „a“ винаги е по-голям или по-малък с 1 от „b“, при това в зависимост от това дали n е четно или нечетно. Тоест спокойно можем да кажем, че:
an = bn + (-1)n
Остана да намерим общия член на една от двете редици. Тук ни озарява голямо щастие – имаме позната редица. Това е „Редицата на Якобщал„: 0,1,1,3,5,11,21,43,… Нейният общ член е:
bn = (2n-(-1)n)/3
От тук получаваме и формулата за коефициента пред „a“:
an = (2n-(-1)n)/3 + (-1)n = (2n+2.(-1)n)/3
Накрая имаме и обща формула за наличността на ябълките на Иван след „n“ на брой стъпки. Тук ще напиша формулата на LateX, за да изглежда по-добре. Ако някой не я вижда – да отвори самия сайт, а да не гледа пред „RSS reader“-и:
[math]S(Ivan) = \frac{\left(2^{n}+2.(-1)^{n}\right).a+\left(2^{n}-(-1)^{n}\right).b+\left(2^{n}-(-1)^{n}\right).c}{3.2^{n}}[/math]
От тук лесно намиране и броя на ябълките на Петър и Мария:
[math]S(Petar) = \frac{\left(2^{n}-(-1)^{n}\right).a+\left(2^{n}+2.(-1)^{n}\right).b+\left(2^{n}-(-1)^{n}\right).c}{3.2^{n}}[/math]
[math]S(Maria) = \frac{\left(2^{n}-(-1)^{n}\right).a+\left(2^{n}-(-1)^{n}\right).b+\left(2^{n}+2.(-1)^{n}\right).c}{3.2^{n}}[/math]
Именно тези формули са нашата индукционна хипотеза.
б) Проверка на индукционната хипотеза:
Сега да докажем индукционното предположение. Приемаме, че горното е вярно за n=k (вече е проверено за k=0,1,2,3,4,5,6 и 7). Трябва да докажем, че е вярно и за n=k+1. Първо да разгледаме Иван – той ще е изгубил всичко свое и ще е взел по половината от количеството на другите, т.е.:
[math]S(Ivan)_{k+1} = \frac{\frac{\left(2^{k}-(-1)^{k}\right).a+\left(2^{k}+2.(-1)^{k}\right).b+\left(2^{k}-(-1)^{k}\right).c}{3.2^{k}}}{2}+
+\frac{\frac{\left(2^{k}-(-1)^{k}\right).a+\left(2^{k}-(-1)^{k}\right).b+\left(2^{k}+2.(-1)^{k}\right).c}{3.2^{k}}}{2}[/math]
=>
[math]S(Ivan)_{k+1} = \frac{\left(2^{k}-(-1)^{k}+2^{k}-(-1)^{k}\right).a}{3.2^{k+1}}+
+\frac{\left(2^{k}+2.(-1)^{k}+2^{k}-(-1)^{k}\right).b}{3.2^{k+1}}+\frac{\left(2^{k}-(-1)^{k}+2^{k}+2.(-1)^{k}\right).c}{3.2^{k+1}}[/math]
=>
[math]S(Ivan)_{k+1} = \frac{\left(2^{k+1}-2.(-1)^{k}\right).a+\left(2^{k+1}+(-1)^{k}\right).b+\left(2^{k+1}+(-1)^{k}\right).c}{3.2^{k+1}}[/math]
=>
[math]S(Ivan)_{k+1} = \frac{\left(2^{k+1}+2.(-1)^{k+1}\right).a+\left(2^{k+1}-(-1)^{k+1}\right).b+\left(2^{k+1}-(-1)^{k+1}\right).c}{3.2^{k+1}}[/math]
С което индукционната хипотеза е доказана. Аналогично можете да докажете и за Петър и за Мария. С което и задачата е решена.
Допълнителна задача 1: Решете задача 3, но този път нека всеки да краде 1/r част от ябълките на останалите, като „r“ е число по-голямо или равно на 2.
Допълнителна задача 2: Решете задачата за „k“ на брой хора, всеки от които краде 1/(k-1) части от ябълките на останалите.
Допълнителна задача 3: Решете допълнителна задача 2, но този път нека всеки да краде 1/r част от ябълките на останалите, като „r“ е число по-голямо или равно на (k-1).
Заключение и извод: Интуитивно ясно стана, че с напредването на кражбите броят на ябълките в различните хора започна да се уеднаквява. Значи спокойно можем да намерим формула, по която всички хора в държавата да са равни по богатство. Ако приемем, че хората в държавата ни са 7 милиона на брой, то нека всеки от нас започне регулярно да краде 1/6999999 част от богатството на всеки друг. С напредване на времето, с което и броят на кражбите, ще стигнем до момент, в който няма да има смисъл да се краде от никой (защото разликите в богатството ни ще са части от стотинки, а на кой ще му се „работи“ за толкова?), а от там ще можем спокойно да кажем, че „всички сме станали приблизително равни по богатство“. Или грубо казано – регулярната и повсеместна кражба е един от възможните пътища за постигане на икономическо равенство между индивидите в обществото :) :) :)
Това е друга задача, в която имаме ред на кражбите, т.е. първо краде единия и се получават нови количества, после втория краде от тези нови количества и т.н. Тя също е интересна, ще помисля и над нея.
В тази имаме в предвид, че се краде половината от количеството преди съответната стъпка.
П.П. Добавих и доказателството на индукционната хипотеза.
След като Иван открадне половината ябълки значи вече има а+b/2 и Петър като му открадне половината ще има а/2+3b/4.
Към статията са нанесени малки (но не незначителни) корекции. На едно-две места бях объркал знаци и числа. Сега бих казал, че статията е в завършен вид.