ლექცია 9, State machines: invariants

problem 9.4
ვიწყებთ (0,0) წერტილში. უნდა მივიდეთ (0,2)-ში. ვმოძრაობთ მხოლოდ შემდეგი ნაბიჟებით:
1.(+2,−1)
2. (+1,−2)
3. (+1, +1)
4. (−3, 0)

ამ თავის ამოცანის მთელი მუღამი ისაა, რომ უნდა ვიპოვოთ ისეთი პირობა, რომელიც ყოველთვის შესრულდება ამ ამოცანისთვის, რაც არ უნდა ვქნათ.
ამ შემთხვევაში, კოორდინატების 2y+x ყოველთვის გაიყოფა 7-ზე, რადგან საწყისი წერტილიც და ყველა ბიჯიც ამ პირობას აკმაყოფილებს. (0,2) წერტილი არ აკმაყოფილებს ამ პიროვას, რაც ნიშნავს რომ მანდ ვერ მივალთ. კიდევ ერთი, რაც უნდა დაიმახსოვროთ: რომ დაეკმაყოფილებინა დანიშნულების წერტილს პირობა, დანამდვილებით მაინც ვერ ვიტყოდით, რომ მანდ მივალთ.


Problem 9.6

კარტები გვაქვს დალაგებული შემდეგნაირად:
გულები ტუზიდან კაკომდე, ყვავები იგივენაირად, ჯვრები და აგურები.
დაასაბუთეთ, რომ inshuffling-ისა და outshuffling-ის ნებისმიერი თანმიმდევრობით/რაოდენობით შესრულებისას, ვერ მივიღებთ კარტებს ისე, რომ პირველ ნახევარში სულ წითლები იყო, მეორეში - შავები.

მუღამი ისაა, რომ ცენტრიდან თანაბრად დაშორებული კარტები ერთმანეთის სიმეტრიულები რჩებიან. განვიხილოთ დასტის პირველი და უკანასკნელი კარტები:
ტუზ გული და კაკო აგური.
თუ გავაკეთებთ ინშაფლინგს:
პირველი კარტი ისევ იქნება ტუზ გული, ბოლო - კაკო აგური. სიმეტრიულობა შენარჩუნდა.
თუ გავაკეთებთ აუთშაფლინგს:
პირველი კარტი გახდება ტუზ ყვავი, ტუზ გული იქნება მეორე. ბოლო კარტი გახდება კაკო ჯვარი, კაკო აგური გახდება ბოლოსწინა. ანუ, ბოლო კარტებიდან ერთი გახდა მეორე ცალი მხრიდა, მეორე კი მეორე სხვა მხრიდან, ანუ სიმეტრიულობა შენარჩუნდა.
ეს კარტები რომ არ ყოფილიყო, მაშინ ანალოგიურად მოხდებოდა იგივე მეორე და ბოლოსწინა კარტებისთვის და ა.შ. ანუ სიმეტრიულობა ყოველთვის სრულდება. ასე რომ, მიზანს ვერ მივაღწევთ
Problem 9.8
fifteen puzzle - ვიწყებთ ასე:

უნდა მივიღოთ:

ამჟამინდელი მდგომარეობა გამოვსახოთ რიცხვების თანმიმდევრობით (1,2,3...,15) და ცარიელი უჯრის კოორდინატებით - ((4,4)).

რიცხვების თანმიმდევრობას დავარქვთ L. L-ში რიცხვთა წყვილი არეულადაა, თუ პირველი რიცხვი მეორეზე ადრე "დგას" და უფრო დიდია. მაგალითად, თუ L={1,2,4,5,4}, არეულობის ხარისხია 2: (4,3) და (5,3).

შემოვიღოთ ცნება S.   S(L,(i,j)) = (P(L)+i)%2.  ახლა ეს რას ნიშნავს :D S ტოლია არეულობის ხარისხს პლიუს ცარიელი უჯრის რიგის ნაშთი ორზე. (j-ცარიელი უჯრის სვეტი, j-რიგი) დასაწყისში S=0. მიზანში S=1. ახლა უნდა დავამტკიცოთ, რომ ცარიელუ უჯრის ნებისმიერი გადაადგილებით S არ იცვლება. ჰორიზონტალური გადაადგილება, ტივიალურია, არაფერს არ ცვლის. ვერტიკალური გადაადგილება i+ს ცვლის ერთით, P(L)-ს 3-ით ან ერთით. ჯამში P(L)+i იცვლება ლუწი რიცხვით, ანუ S ყოველთვის რჩება 0.

problem 9.10

პირველის ანალოგიურია, ოღონდ ამ შემთხვევაში ინვარიანტია 3x-y იყოფა 7-ზე.

5)  ა) შეიძლება თუ არა 10×10 ზომის დაფა დაიფაროს 1×4 ზომის ფილებით? მითითება: ჩაწერეთ პირველ სტრიქონში რიცხვები 1,1,1,–3,1,1,1,–3,1,1. იგივე რიცხვები ჩაწერეთ პირველ სვეტშიც. ნებისმიერ სხვა უჯრაში ჩაწერეთ ამ უჯრის ვერტიკალზე უკიდურეს ზედა უჯრაში ჩაწერილი რიცხვის და ამ უჯრის ჰორიზონტალზე უკიდურეს მარცხენა უჯრაში ჩაწერილი რიცხვის ნამრავლი. რისი ტოლი იქნება ერთი ფილით დაფარული ოთხი უჯრის რიცხვების ჯამი? 

ბ) დაასაბუთეთ, რომ m×n ზომის დაფა შეიძლება დაიფაროს 1×k ზომის ფილებით მაშინ და მხოლოდ მაშინ, როცა m ან n იყოფა k-ზე.

ა)მიყევით მითითებას. ერთი ფილით დაფარული უჯრების ჯამი 0 იქნება, შესაბამისად ყველა ფილით დაგფარული უჯრების ჯამიც 0 უნდა იყოს, მაგრამ ადვილი გადასათვლელია, რომ ყველა უჯრის ჯამი 0 არაა, შესაბამისად არ დაიფარება.

ბ)მსგავსია, ოღონდ უნდა ვიპოვოთ გზა იმის დასამტკიცებლად, რომ mXn უჯრების რიცხვთა ჯამი 0 არაა, რაც მე ვერ გავაკეთე შუალედურზე :) ვინმემ თუ იცით, დაწერეთ.

problem 9.12

(a) Model this situation as a state machine, carefully defining the set of states, the start state, and 

the possible state transitions.

თუ ვიწყებთ h რაოდენობის არიოლით და t რაოდენობის რეშკით (ან პირიქით, მაგას არ აქვს მნიშვნელობა);

state machine:

ოპერაცია 1) (h,t) ---> (h − a + (10 − a) ,t + a − (10 − a)) - 10 ხურდის გადაბრუნება. 0 <= a <= min(10,h)

ან

ოპერაცია 2) (h,t) ---> (h, t + h + 1) არიოლის რაოდენობაზე ერთით მეტი რეშკის დამატება.

b) როგორ მივიდეთ იქამდე, რომ მხოლოდ ერთი რეშკა დარჩეს. h=98, t=4.

გავაკეთოთ ოპერაცია 2 3-ჯერ. მივიღებთ : (98, 301).

30-ჯერ გადავაბრუნოთ 10-10 არიოლი. გამოვა (398, 1).

c) ადვილია

d) არც ერთი ოპერიაცია არ ცვლის h-ის ლუწობას:

პირველის შედეგად, თუ კენტს გადავაბრუნებთ, კენტს გადმოვაბრუნებთ და მაინც ლუწი იქნება. თუ ლუწს გადავაბრუნებთ, მითუმეტეს.

მეორე ოპერაციას კი საერთოდ არანაირი გავლენა არ აქვს h-ზე.