C, PHP, VB, .NET

Дневникът на Филип Петров


* Кражби от съседчето

Публикувано на 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 част от богатството на всеки друг. С напредване на времето, с което и броят на кражбите, ще стигнем до момент, в който няма да има смисъл да се краде от никой (защото разликите в богатството ни ще са части от стотинки, а на кой ще му се "работи" за толкова?), а от там ще можем спокойно да кажем, че "всички сме станали приблизително равни по богатство". Или грубо казано - регулярната и повсеместна кражба е един от възможните пътища за постигане на икономическо равенство между индивидите в обществото :) :) :)

 



3 коментара


  1. Това е друга задача, в която имаме ред на кражбите, т.е. първо краде единия и се получават нови количества, после втория краде от тези нови количества и т.н. Тя също е интересна, ще помисля и над нея.

    В тази имаме в предвид, че се краде половината от количеството преди съответната стъпка.

    П.П. Добавих и доказателството на индукционната хипотеза.

  2. След като Иван открадне половината ябълки значи вече има а+b/2 и Петър като му открадне половината ще има а/2+3b/4.

  3. Към статията са нанесени малки (но не незначителни) корекции. На едно-две места бях объркал знаци и числа. Сега бих казал, че статията е в завършен вид.

Добави коментар

Адресът на електронната поща няма да се публикува


*