ლექცია 17, Recursive data types

Problem 11.3 (a,b)

Here is a simple recursive definition of the set, E, of even integers:
Definition. Base case: 0 ∈ E.
                Constructor cases: If n ∈ E, then so are n +2 and −n.
Provide similar simple recursive definitions of the following sets:
(a)
The set S ::= {2^k*3^m*5^n | k,m,n ∈ N} .

• 1∈S
• თუ n∈S, მაშინ 2*n, 3*n და 5*n ეკუთვნის S-ს.

(b)
The set T ::= {2^k*3^(2*k+m)*5^(m+n) | k,m,n ∈ N} .

• 1 ∈ S 
• თუ n ∈ S, მაშინ 18n, 15n, და 5n ეკუთვნის S-ს.

Problem 11.7

Fractals are example of a mathematical object that can be defined recursively. In this problem, we consider the Koch snowflake. Any Koch snowflake can be constructed by the following recursive definition.

•Base Case: An equilateral triangle with a positive integer side length is a Koch snowflake.

•Recursive case: Let K be a Koch snowflake, and let l be a line segment on the snowflake. Remove the middle third of l, and replace it with two line segments of the same length.

The resulting figure is also a Koch snowflake.

Prove by structural induction that the area inside any Koch snowflake is of the form q√3, where q is a rational number.

კოხის ფიფქი შედგება ტოლგვერდა სამკუთხედებისგან, რომელთა გვერის სიგრძეა (ამ შემთხვევაში) √3. ტოლგვერდა სამკუთხედის ფართობია (თუ სწორად მახსოვს :) ) a^2*√3/4 = 3*√3/4.   ეს იქნება ერთი ცალი სამკუთხედის ფართობი. ამ რიცხვს გავამრავლებთ ასეთი სამკუთხედების რაოდენობაზე - n-ზე - და მივიღებთ:

n*3*√3/4

Problem 11.2 (a)

???? - help needed

4)თეორემა 11.4.5 –ის დამტკიცება ისეთი სასრული თამაშებისთვის, რომლებიც მხოლოდ მოგება–წაგებით მთავრდებიან (ფრე არ არის).

Theorem 11.4.5. Fundamental Theorem for Two-Person Games: For every two-person terminating game of perfect information, there is a winning strategy for one of the players.

Proof. The proof is by structural induction on the definition of a 2PTG, G. The induction hypothesis is that there is a winning strategy for G.

Base cases:

1.G = {leaf, win}. Then the first player has the winning strategy: “make the winning move.”

2.G = {leaf, lose}. Then the second player has a winning strategy: “Let the first player make the losing move.”

Constructor case: 

Suppose G = {tree, G}. By structural induction, we may assume that some player has a winning strategy for each G' ∈G. There are two cases to consider:

•some G0 ∈G has a winning strategy for its second player. Then the first player in G has a winning strategy: make the move to G0 and then follow the second player’s winning strategy in G0.

•every G' ∈G has a winning strategy for its first player. Then the second player in Ghas a winning strategy: if the first player’s move in Gis to G0 ∈G, then follow the winning strategy for the first player in G0.

So in any case, one of the players has a winning strategy for G, which completes the proof of the constructor case. It follows by structural induction that there is a winning strategy for every 2PTG, G.

5)ჩამოაყალიბეთ და დაამტკიცეთ თეორემა 11.4.5 ისეთი თამაშებისთვისაც, სადაც ფრეც არის შესაძლებელი (მაგალითად „კრესტიკი–ნოლიკის“ თამაშის შემთხვევაში).

6. მაგიდაზეა 11 მონეტა. ორი მოთამაშე თამაშობს მორიგეობით: ჯერ ერთი იღებს 2 ან 3 მონეტას (როგორც თვითონ უნდა), შემდეგ მეორე იღებს 2 ან 3–ს, და ასე გრძელდება თამაში. წაგებულია ის, ვინც სვლას ვეღარ გააკეთებს (0 ან 1 მონეტა დარჩა მაგიდაზე). 

ა) სრული ხის დახაზვის საშუალებით გაარკვიეთ ვის აქვს ამ თამაშში მოსაგები სტრატეგია. 

ბ) იგივე ამოცანა ოღონდ დასაშვებ სვლად ითვლებოდეს ერთი მონეტის აღებაც მხოლოდ იმ შემთხვევაში, თუ მაგიდაზე ერთადერთი მონეტაა დარჩენილი.

და ამასაც ამოვხსნი(თ) :)