C, PHP, VB, .NET

Задача 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"-тата стъпка?

Ако намерим наличностите на Иван директно можем да намерим наличностите на Петър и Мария. Знаменателят е винаги 2ⁿ, тоест ние го знаем. Виждаме също, че при Иван винаги коефициентите пред "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 е четно или нечетно.  Тоест спокойно можем да кажем, че:

a_n = b_n + (-1)ⁿ

Остана да намерим общия член на една от двете редици. Тук ни озарява голямо щастие - имаме позната редица. Това е "Редицата на Якобщал": 0,1,1,3,5,11,21,43,... Нейният общ член е:

b_n = (2ⁿ-(-1)ⁿ)/3

От тук получаваме и формулата за коефициента пред "a":

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