ผมจะเฉลยข้อสอบวิทยาการคอมพิวเตอร์ 26. ทฤษฎีเกม. ค้นหากลยุทธ์แห่งชัยชนะ

ผู้เล่นสองคน Pasha และ Vova กำลังเล่นเกมถัดไป มีกองหินอยู่ข้างหน้าผู้เล่น ผู้เล่นผลัดกัน Pasha ทำการเคลื่อนไหวครั้งแรก ในเทิร์นหนึ่ง ผู้เล่นสามารถเพิ่มหิน 1 ก้อนหรือ 10 ก้อนลงในกองได้ ตัวอย่างเช่น การมีก้อนหิน 7 กอง ในการเคลื่อนไหวครั้งเดียว คุณจะได้ก้อนหิน 8 หรือ 17 ก้อน ผู้เล่นแต่ละคนมีหินไม่จำกัดจำนวนในการเคลื่อนที่ เกมจะจบลงเมื่อจำนวนหินในกองมีอย่างน้อย 31 ก้อน ผู้ชนะคือผู้เล่นที่เดินครั้งสุดท้าย นั่นคือเป็นคนแรกที่ได้รับกองที่มีหิน 31 ก้อนขึ้นไป

ในตอนแรกมีหิน S อยู่ในกอง 1 ≤ S ≤ 30

สารละลาย.

1. a) Pasha สามารถชนะได้หาก S = 21, ..., 30 ด้วยค่า S ที่น้อยกว่าในการเคลื่อนไหวครั้งเดียวจึงเป็นไปไม่ได้ที่จะได้กองที่มีหินมากกว่า 30 ก้อน Pasha ต้องการเพิ่มจำนวนหินเพียง 10 ก้อน สำหรับ S 1 b) Vova สามารถชนะได้ในการย้ายครั้งแรก (ไม่ว่า Pasha จะเล่นอย่างไร) หากฮีปเริ่มแรกมีหิน S = 20 ก้อน หลังจากการเคลื่อนไหวครั้งแรกของ Pasha จะมีหิน 21 ก้อนหรือ 30 ก้อนในกอง ในทั้งสองกรณี Vanya จะเพิ่มจำนวนหิน 10 ก้อนและชนะในครั้งเดียว

2. ค่าที่เป็นไปได้ของ S: 10, 19 ในกรณีเหล่านี้ เห็นได้ชัดว่ามหาอำมาตย์ไม่สามารถชนะได้ในการเคลื่อนไหวครั้งแรก อย่างไรก็ตาม เขาสามารถเก็บหินได้ 20 กอง (ที่ S=10 เขาจะเพิ่มจำนวนหินได้ 10 ก้อน และที่ S=19 เขาจะเพิ่มหิน 1 ก้อน) ตำแหน่งนี้จะกล่าวถึงในวรรค 1 ข ในนั้นผู้เล่นที่จะเคลื่อนไหว (ตอนนี้คือ Vova) ไม่สามารถชนะได้ แต่คู่ต่อสู้ของเขา (นั่นคือ Pasha) จะชนะในการเคลื่อนไหวครั้งต่อไป

3. ค่าที่เป็นไปได้ของ S: 18 หลังจากการเคลื่อนไหวครั้งแรกของ Pasha จะมีหิน 19 หรือ 28 ก้อนในกอง หากมีหิน 28 ก้อนในกอง Vova จะเพิ่มจำนวนหิน 10 ก้อนและคุณจะเล่นด้วยการเคลื่อนไหวครั้งแรก สถานการณ์เมื่อมีหิน 19 ก้อนในกองได้รับการจัดการในวรรค 2 ในสถานการณ์นี้ผู้เล่นที่จะเคลื่อนไหว (ตอนนี้คือ Vova) ชนะด้วยการเคลื่อนไหวครั้งที่สอง

แขก 26.05.2014 12:31

จุดที่ 3. แต่สถานการณ์เมื่อเริ่มแรกมีหิน 9 ก้อนในกองล่ะ หลังจากการเคลื่อนไหวของ Pasha หินจะกลายเป็น 10 หรือ 19 Vasya จบได้ถึง 20 และต่อไปตามข้อ 1.b.

คอนสแตนติน ลาฟรอฟ

ใช่แล้ว 9 ก็เป็นคำตอบที่ถูกต้องเช่นกัน ก็เพียงพอที่จะระบุค่าที่ถูกต้องอย่างน้อยหนึ่งค่า

ผู้เล่นสองคน Pasha และ Vova กำลังเล่นเกมถัดไป มีกองหินอยู่ข้างหน้าผู้เล่น ผู้เล่นผลัดกัน Pasha ทำการเคลื่อนไหวครั้งแรก ในเทิร์นหนึ่ง ผู้เล่นสามารถเพิ่มหิน 1 ก้อนหรือ 10 ก้อนลงในกองได้ ตัวอย่างเช่น การมีก้อนหิน 7 กอง ในการเคลื่อนไหวครั้งเดียว คุณจะได้ก้อนหิน 8 หรือ 17 ก้อน ผู้เล่นแต่ละคนมีหินไม่จำกัดจำนวนในการเคลื่อนที่ เกมจะจบลงเมื่อจำนวนหินในกองมีอย่างน้อย 41 ก้อน ผู้ชนะคือผู้เล่นที่เคลื่อนไหวครั้งสุดท้าย นั่นคือเป็นคนแรกที่ได้รับกองที่มีหิน 41 ก้อนขึ้นไป

ในตอนแรกมีหิน S อยู่ในกอง 1 ≤ S ≤ 40

เราจะบอกว่าผู้เล่นมีกลยุทธ์ในการชนะหากเขาสามารถชนะด้วยการเคลื่อนไหวของคู่ต่อสู้ การอธิบายกลยุทธ์ของผู้เล่นหมายถึงการอธิบายว่าเขาควรเคลื่อนไหวอย่างไรในสถานการณ์ใดๆ ที่เขาอาจเผชิญกับการเล่นที่แตกต่างจากศัตรู

ทำงานต่อไปนี้ให้เสร็จสิ้น ในทุกกรณี ให้เหตุผลในคำตอบของคุณ

1. ก) ระบุค่าดังกล่าวทั้งหมดของหมายเลข S ที่มหาอำมาตย์สามารถชนะได้ในครั้งเดียว แสดงให้เห็นว่าพบค่าที่ต้องการทั้งหมดของ S และระบุการเคลื่อนไหวที่ชนะ

b) ระบุค่าของ S เพื่อให้ Pasha ไม่สามารถชนะได้ในการเคลื่อนไหวครั้งเดียว แต่ด้วยการเคลื่อนไหวใด ๆ ของ Pasha Vova สามารถชนะได้ในการเคลื่อนไหวครั้งแรก อธิบายกลยุทธ์แห่งชัยชนะของ Vova

2. ระบุค่าสองค่าของ S ที่ Pasha มีกลยุทธ์ในการชนะ และ Pasha ไม่สามารถชนะได้ในกระบวนท่าเดียว แต่สามารถชนะได้ด้วยกระบวนท่าที่สอง ไม่ว่า Vova จะเคลื่อนไหวอย่างไร สำหรับค่าที่กำหนดของ S ให้อธิบายกลยุทธ์การชนะของ Pasha

3. ระบุค่าของ S ที่ Vova มีกลยุทธ์ในการชนะที่ทำให้เขาชนะด้วยการเคลื่อนไหวครั้งแรกหรือครั้งที่สองในเกมของ Pasha แต่ Vova ไม่มีกลยุทธ์ที่จะทำให้เขาชนะด้วยการเคลื่อนไหวครั้งแรก สำหรับค่า S ที่ระบุ ให้อธิบายกลยุทธ์การชนะของ Vova สร้างแผนผังของเกมทั้งหมดที่เป็นไปได้ด้วยกลยุทธ์แห่งชัยชนะของ Vova (ในรูปแบบของรูปภาพหรือตาราง) ที่ขอบต้นไม้ระบุว่าใครกำลังเคลื่อนไหวและที่โหนด - จำนวนก้อนหินในกอง

สารละลาย.

1. a) Pasha สามารถชนะได้หาก S = 31, ..., 40 ด้วยค่า S ที่น้อยกว่าในการย้ายครั้งเดียวจึงเป็นไปไม่ได้ที่จะได้กองที่มีหินมากกว่า 40 ก้อน มหาอำมาตย์ต้องเพิ่มจำนวนหินเพียง 10 ก้อน ด้วย S b) Vova สามารถชนะได้ในการย้ายครั้งแรก (ไม่ว่ามหาอำมาตย์จะเล่นอย่างไร) หากกองเริ่มแรกมีหิน S = 30 ก้อน หลังจากการเคลื่อนไหวครั้งแรกของมหาอำมาตย์ จะมีหิน 31 ก้อนหรือ 40 ก้อนอยู่ในกอง ในทั้งสองกรณี Vanya จะเพิ่มจำนวนหิน 10 ก้อนและชนะในครั้งเดียว

2. ค่าที่เป็นไปได้ของ S: 20, 29 ในกรณีเหล่านี้ เห็นได้ชัดว่ามหาอำมาตย์ไม่สามารถชนะได้ในการเคลื่อนไหวครั้งแรก อย่างไรก็ตาม เขาสามารถรับก้อนหินได้ 30 กอง (สำหรับ S = 20 เขาจะเพิ่มจำนวนก้อนหินขึ้น 10 ก้อน สำหรับ S = 29 เขาจะเพิ่มหิน 1 ก้อน) ตำแหน่งนี้จะกล่าวถึงในวรรค 1 b) ในนั้นผู้เล่นที่จะเคลื่อนไหว (ตอนนี้คือ Vova) ไม่สามารถชนะได้ แต่คู่ต่อสู้ของเขา (นั่นคือ Pasha) จะชนะในการเคลื่อนไหวครั้งต่อไป

3. ค่าที่เป็นไปได้ของ S: 28 หลังจากการเคลื่อนไหวครั้งแรกของ Pasha จะมีหิน 29 หรือ 38 ก้อนในกอง หากกองหินถึง 38 ก้อน Vova จะเพิ่มจำนวนหิน 10 ก้อนและคุณจะเล่นด้วยการเคลื่อนไหวครั้งแรก สถานการณ์เมื่อมีหิน 29 ก้อนในกองได้รับการจัดการในวรรค 2 ในสถานการณ์นี้ผู้เล่นที่จะเคลื่อนไหว (ตอนนี้คือ Vova) ชนะด้วยการเคลื่อนไหวครั้งที่สอง

ตารางแสดงแผนผังเกมที่เป็นไปได้สำหรับกลยุทธ์ของ Vova ที่อธิบายไว้ข้างต้น ตำแหน่งสุดท้าย (Vova ชนะในนั้น) จะถูกขีดเส้นใต้ ในภาพ มีการแสดงต้นไม้ต้นเดียวกันเป็นภาพกราฟิก (ยอมรับได้ทั้งสองวิธีในการแสดงภาพต้นไม้)

ผู้เล่นสองคน Petya และ Vanya กำลังเล่นเกมถัดไป ด้านหน้าพวกเขามีก้อนหินสองกองกองแรกประกอบด้วย 2 ก้อนและก้อนที่สอง - 3 ก้อน ทุกเกมมีหินมากมาย ผู้เล่นผลัดกันโดย Petya เคลื่อนไหวเป็นคนแรก การเคลื่อนไหวประกอบด้วยความจริงที่ว่าผู้เล่นเอาหินจำนวนหนึ่งในกองออกหรือเพิ่มหิน 4 ก้อนลงในกองบางกอง เกมจะจบลงในขณะที่จำนวนหินทั้งหมดในสองกองมีอย่างน้อย 31 ก้อน หากในขณะนี้เกมจบลงจำนวนหินรวมในสองกองอย่างน้อย 40 ก้อน Petya จะชนะ มิฉะนั้น Vanya จะชนะ คุณเล่นใครเมื่อผู้เล่นทั้งสองเล่นโดยไม่มีข้อผิดพลาด? การเคลื่อนไหวครั้งแรกของเกมของคุณควรเป็นอย่างไร? อธิบายคำตอบ.

สารละลาย.

วานย่าชนะ

เพื่อพิสูจน์ ลองพิจารณาแผนผังเกมที่ไม่สมบูรณ์ ซึ่งออกแบบมาในรูปแบบของตาราง โดยแต่ละเซลล์จะมีคู่ของตัวเลขคั่นด้วยเครื่องหมายจุลภาค ตัวเลขเหล่านี้สอดคล้องกับจำนวนหมากในแต่ละด่านของเกมในกองที่หนึ่งและสองตามลำดับ

ตารางมีทุกสิ่ง ตัวเลือกที่เป็นไปได้การเคลื่อนไหวของผู้เล่นคนแรก มันแสดงให้เห็นว่าการเคลื่อนไหวใดๆ ของผู้เล่นคนแรก คนที่สองมีการเคลื่อนไหวที่นำไปสู่ชัยชนะ

ผู้เล่นสองคน Petya และ Vasya กำลังเล่นเกมต่อไปนี้ ข้างหน้าพวกเขามีก้อนหินสองกองกองแรกประกอบด้วย 2 ก้อนและกองที่สอง - 1 ก้อน ผู้เล่นแต่ละคนมีหินไม่จำกัดจำนวน ผู้เล่นผลัดกัน Petya ไปก่อน การเคลื่อนไหวคือผู้เล่นเพิ่มจำนวนหินในบางกอง 3 ครั้งหรือเพิ่มหิน 3 ก้อนในกองบางกอง ผู้เล่นชนะ หลังจากที่มีก้อนหินอย่างน้อย 24 ก้อนในกองใดกองหนึ่ง ใครชนะเมื่อเล่นโดยไม่มีข้อผิดพลาด? การเคลื่อนไหวครั้งแรกของผู้เล่นที่ชนะควรเป็นอย่างไร?

ชี้แจงคำตอบของคุณ

สารละลาย.

Petya ชนะ ในการเคลื่อนไหวครั้งแรกเขาจะต้องเพิ่มจำนวนหินในกองที่สอง 3 เท่า เพื่อพิสูจน์ ลองพิจารณาแผนผังเกมที่ไม่สมบูรณ์ ซึ่งออกแบบมาในรูปแบบของตาราง โดยแต่ละเซลล์จะมีคู่ของตัวเลขคั่นด้วยเครื่องหมายจุลภาค ตัวเลขเหล่านี้สอดคล้องกับจำนวนหมากในแต่ละขั้นตอนของเกมในกองที่หนึ่งและสองตามลำดับ

ตารางประกอบด้วยตัวเลือกที่เป็นไปได้ทั้งหมดสำหรับการเคลื่อนไหวของ Vasya มันแสดงให้เห็นว่าไม่ว่าจะตอบอย่างไร Petya ก็มีความเคลื่อนไหวที่นำไปสู่ชัยชนะ

ผู้เล่นสองคน Petya และ Vanya เล่นเกมต่อไปนี้ มีกองหินอยู่ข้างหน้าผู้เล่น ผู้เล่นผลัดกัน Petya เคลื่อนไหวครั้งแรก ในคราวเดียว ผู้เล่นสามารถเพิ่มหินหนึ่งก้อนลงในกองหรือเพิ่มจำนวนหินในกองได้ห้าครั้ง ตัวอย่างเช่น ถ้าคุณมีกองหิน 10 ก้อน คุณก็จะได้กองหิน 11 หรือ 50 ก้อนในการย้ายครั้งเดียว ผู้เล่นแต่ละคนมีหินไม่จำกัดจำนวนในการเคลื่อนที่

เกมจะจบลงทันทีที่จำนวนหินในกองมีมากกว่า 100 ก้อน ผู้ชนะคือผู้เล่นที่เดินครั้งสุดท้าย นั่นคือเป็นคนแรกที่ได้รับกองที่มีหิน 101 ก้อนขึ้นไป

ในตอนแรกมีหิน S อยู่ในกอง 1 ≤ S ≤ 100

กล่าวกันว่าผู้เล่นมีกลยุทธ์ในการชนะหากเขาสามารถชนะด้วยการเคลื่อนไหวของคู่ต่อสู้ การอธิบายกลยุทธ์ของผู้เล่นหมายถึงการอธิบายว่าเขาควรเคลื่อนไหวอย่างไรในสถานการณ์ใดๆ ที่เขาอาจเผชิญกับการเล่นที่แตกต่างจากศัตรู

ทำงานต่อไปนี้ให้เสร็จสิ้น ในทุกกรณี ให้เหตุผลในคำตอบของคุณ

1. ก) Petya สามารถชนะค่า S ของตัวเลขใดในการเคลื่อนไหวครั้งแรก? แสดงรายการค่าดังกล่าวทั้งหมดและการเคลื่อนไหวที่ชนะของ Petit

b) ระบุค่า S เพื่อให้ Petya ไม่สามารถชนะได้ในการเคลื่อนไหวครั้งเดียว แต่สำหรับการเคลื่อนไหวใดๆ ที่ Petya ทำ Vanya สามารถชนะได้ในการเคลื่อนไหวครั้งแรก อธิบายกลยุทธ์แห่งชัยชนะของ Vanya

2. ระบุค่าสองค่าของ S ที่ Petya มีกลยุทธ์ในการชนะ และ Petya ไม่สามารถชนะได้ด้วยการเคลื่อนไหวครั้งแรก แต่ Petya สามารถชนะได้ด้วยการเคลื่อนไหวครั้งที่สอง ไม่ว่า Vanya จะเคลื่อนไหวอย่างไร สำหรับค่าที่กำหนดของ S ให้อธิบายกลยุทธ์การชนะของ Petit

3. ระบุค่าของ S เพื่อให้ Vanya มีกลยุทธ์ในการชนะที่ทำให้เขาชนะด้วยการเคลื่อนไหวครั้งแรกหรือครั้งที่สองในเกม Petya ใด ๆ และในขณะเดียวกัน Vanya ก็ไม่มีกลยุทธ์ที่จะทำให้เขาชนะด้วยการเคลื่อนไหวครั้งแรก เคลื่อนไหว.

สำหรับค่าที่กำหนดของ S ให้อธิบายกลยุทธ์การชนะของ Vanya สร้างแผนผังของเกมทั้งหมดที่เป็นไปได้ด้วยกลยุทธ์แห่งชัยชนะของ Vanya นำเสนอเป็นรูปภาพหรือตาราง สำหรับแต่ละขอบของต้นไม้ ให้ระบุว่าใครเป็นผู้เคลื่อนไหว สำหรับแต่ละโหนด ให้ระบุจำนวนหินในตำแหน่ง

สารละลาย.

1. a) Petya สามารถชนะได้หาก S = 21, ..., 100 ด้วยค่า S ที่น้อยกว่าในการเคลื่อนไหวครั้งเดียวจึงเป็นไปไม่ได้ที่จะได้กองที่มีหินมากกว่า 100 ก้อน สำหรับ Petya ก็เพียงพอที่จะเพิ่มจำนวนก้อนหินได้ 5 เท่า เมื่อ S 1. b) Vanya สามารถชนะได้ด้วยการเคลื่อนไหวครั้งแรก (ไม่ว่า Petya จะเล่นอย่างไร) หากในตอนแรกมีหิน S = 20 ก้อนอยู่ในกอง หลังจากการเคลื่อนไหวครั้งแรกของ Petya จะมีหิน 21 ก้อนหรือ 100 ก้อนในกอง ในทั้งสองกรณี Vanya จะเพิ่มจำนวนหิน 5 ครั้งและชนะในครั้งเดียว

2. ค่าที่เป็นไปได้ของ S: 4, 19 ในกรณีเหล่านี้ Petya ไม่สามารถชนะได้อย่างชัดเจนในการเคลื่อนไหวครั้งแรก อย่างไรก็ตาม เขาสามารถเก็บหินได้ 20 กอง (โดย S = 4 เขาจะเพิ่มจำนวนหินได้ 5 เท่า และด้วย S = 19 เขาจะเพิ่มหิน 1 ก้อน) ตำแหน่งนี้จะกล่าวถึงในวรรค 1 b) ในนั้นผู้เล่นที่จะเคลื่อนไหว (ตอนนี้ Vanya) ไม่สามารถชนะได้ แต่คู่ต่อสู้ของเขา (นั่นคือ Petya) จะชนะในการเคลื่อนไหวครั้งต่อไป

3. ค่าที่เป็นไปได้ของ S: 18 หลังจากการเคลื่อนไหวครั้งแรกของ Petya จะมีหิน 19 หรือ 90 ก้อนอยู่ในกอง หากมีหิน 90 ก้อนในกอง Vanya จะเพิ่มจำนวนหิน 5 ครั้งและชนะในการเคลื่อนไหวครั้งแรก สถานการณ์เมื่อมีหิน 19 ก้อนในฮีปได้รับการจัดการในวรรค 2 ในสถานการณ์นี้ผู้เล่นที่จะเคลื่อนไหว (ตอนนี้คือ Vanya) ชนะด้วยการเคลื่อนไหวครั้งที่สอง

ตารางแสดงแผนผังเกมที่เป็นไปได้สำหรับกลยุทธ์ของ Vanya ที่อธิบายไว้ข้างต้น ตำแหน่งสุดท้าย (Vanya ชนะในนั้น) จะถูกขีดเส้นใต้ ในภาพ มีการแสดงต้นไม้ต้นเดียวกันเป็นภาพกราฟิก (ยอมรับทั้งสองวิธีในการพรรณนา)

ทำแบบทดสอบเกี่ยวกับงานเหล่านี้

ส่วนที่ยากที่สุดของปัญหานี้คือการเขียนวิธีแก้ปัญหาอย่างถูกต้องและมีเหตุผล

เรามาเริ่มด้วยการพยายามทำความเข้าใจเงื่อนไขกันดีกว่า

1. เรามีก้อนหินสองกองและผู้เล่นสองคน: คนแรก (Petya) และคนที่สอง (Vanya)
2. ผู้เล่นผลัดกัน
3. ในระหว่างการเคลื่อนที่ คุณสามารถเพิ่มก้อนหินหนึ่งก้อนลงในกองใดก็ได้ หรือเพิ่มจำนวนก้อนหินในกองเป็นสองเท่าก็ได้
4. ทันทีที่มีหิน 73 ก้อนขึ้นไปในกอง เกมจะจบลง
5. คนสุดท้ายที่จะไปชนะ

หมายเหตุสำคัญ

1. ในบางงานเราจะสร้างแผนผังปาร์ตี้ เราจำเป็นต้องทำเช่นนี้ตามเงื่อนไขในภารกิจที่ 3 เท่านั้น ในภารกิจที่ 2 เรา ไม่จำเป็นสร้างปาร์ตี้ทรี
2. ในแต่ละงาน แค่บอกว่าใครเป็นผู้ชนะนั้นไม่เพียงพอ คุณต้องอธิบายและระบุจำนวนขั้นตอนที่เป็นไปได้ที่จะต้องชนะ
3. การเรียกกลยุทธ์ที่ชนะนั้นไม่เพียงพอ จำเป็นต้อง พิสูจน์ว่ามันนำไปสู่การชนะ แม้แต่ข้อความที่ชัดเจนก็ยังต้องมีหลักฐาน

ภารกิจที่ 1

ตอนนี้เรามาดูภารกิจที่ 1 กันดีกว่า มีหิน (6, 33) ก้อนอยู่ในกอง (ส่วนแรกของภารกิจที่ 1) และหิน (8, 32) ก้อน (ส่วนที่สองของภารกิจที่ 1) เราจำเป็นต้องพิจารณาว่าผู้เล่นคนใดมีกลยุทธ์ในการชนะ กล่าวอีกนัยหนึ่ง ผู้เล่นคนไหนหากเล่นอย่างถูกต้องจะเป็นผู้ชนะอย่างแน่นอนไม่ว่าฝ่ายตรงข้ามจะกระทำอย่างไร

ต่อไปนี้เราจะแบ่งโซลูชันออกเป็นสองส่วน ขั้นแรกจะมีคำอธิบายเบื้องต้น (ไม่จำเป็นต้องเขียนในการสอบ Unified State) จากนั้น - "การตัดสินใจอย่างเป็นทางการ" นั่นคือสิ่งที่ต้องเขียนในแบบฟอร์มการสอบ Unified State เอง

การอภิปราย.

ลองคิดดู: เห็นได้ชัดว่าผู้เล่นคนแรกไม่สามารถชนะได้ในการเคลื่อนไหวครั้งเดียว เนื่องจากไม่ว่าเขาจะทำอะไรก็ตาม ผลรวมจะไม่ใช่ 73 การกระทำที่ "ยิ่งใหญ่ที่สุด" ที่เขาสามารถทำได้คือเพิ่มจำนวนหินในกองที่สองเป็นสองเท่า ทำให้มี 66 ก้อน แต่ (6, 66) คือ 72 ก้อน ไม่ใช่ 73 ซึ่งหมายความว่าสามารถชนะก้อนแรกได้อย่างชัดเจนในครั้งเดียว ไม่สามารถ. อย่างไรก็ตาม คนที่สองมีความสามารถค่อนข้างมาก คนแรกสามารถทำสี่การกระทำ: เพิ่ม 1 ลงในกองแรก, เพิ่มจำนวนก้อนหินในกองแรกเป็นสองเท่า, เพิ่ม 1 ลงในกองที่สอง, เพิ่มจำนวนก้อนหินในกองที่สองเป็นสองเท่า มาดูกันว่าสิ่งนี้นำไปสู่อะไร:

• (6.33) -> (7.33) ในกรณีนี้ ผู้เล่นคนที่สองสามารถเพิ่มจำนวนหินเป็นสองเท่าในกองที่สองได้ เราได้ (7, 66) รวม - 73 ดังนั้นอันที่สองชนะ
• (6.33) -> (12, 33) ในกรณีนี้ ผู้เล่นคนที่สองสามารถเพิ่มจำนวนหินในกองที่สองเป็นสองเท่า เราได้ (12, 66) รวม - 78 ดังนั้นอันที่สองชนะ
• (6.33) -> (6.34) ในกรณีนี้ ผู้เล่นคนที่สองสามารถเพิ่มจำนวนหินในกองที่สองเป็นสองเท่า เราได้ (6, 68) รวม - 74 ดังนั้นอันที่สองชนะ
• (6.33) -> (6.66) ในกรณีนี้ ผู้เล่นคนที่สองสามารถเพิ่มจำนวนหินเป็นสองเท่าในกองที่สองได้ เราได้ (6, 132) รวม - 138 ดังนั้นอันที่สองชนะ

ทั้งหมด: ไม่ว่าผู้เล่นคนแรกจะมีพฤติกรรมอย่างไร คนที่สองจะชนะในการเคลื่อนไหวครั้งเดียว

แก้ได้เช่นเดียวกันกับ (8.32)

วิธีแก้ปัญหาอย่างเป็นทางการสำหรับงานที่ 1

ผู้เล่นคนที่สองมีกลยุทธ์ในการชนะ มาพิสูจน์และแสดงกลยุทธ์นี้กัน เพื่อทำเช่นนี้ เราจะสร้างแผนผังปาร์ตี้สำหรับแต่ละตำแหน่งเริ่มต้น ในแผนผังเกม เราจะระบุสถานะของทั้งสองกองในรูปแบบ (a,b) โดยที่ a คือจำนวนก้อนหินในกองแรก b คือจำนวนก้อนหินในกองที่สอง เมื่อผู้เล่นคนแรกเปลี่ยน เราจะพิจารณาสี่ตัวเลือกที่เป็นไปได้สำหรับพฤติกรรมของเขา: เพิ่ม 1 ก้อนในกองแรก, เพิ่มจำนวนหินในกองแรกเป็นสองเท่า, เพิ่ม 1 ก้อนในกองที่สอง, เพิ่มจำนวนหินในกองที่สองเป็นสองเท่า สำหรับผู้เล่นคนที่สอง เราจะระบุการเคลื่อนไหวหนึ่งครั้งที่นำไปสู่การชนะ เราจะแสดงการเคลื่อนไหวในรูปแบบของลูกศร ถัดจากที่เราเขียนว่า I ในกรณีของการเคลื่อนไหวครั้งแรก และ II ในกรณีของการเคลื่อนไหวครั้งที่สอง

แผนผังเกมสำหรับตำแหน่งเริ่มต้น (6, 33)

แผนผังเกมสำหรับตำแหน่งเริ่มต้น (8, 32)

ตามแผนผังเกม โดยไม่คำนึงถึงการเคลื่อนไหวของครั้งแรก ครั้งที่สองมักจะมีกลยุทธ์การชนะที่ทำให้เขาชนะในการเคลื่อนไหวครั้งเดียวตามที่อธิบายไว้ในแผนภูมิ (ผลรวมหลังจากการเคลื่อนไหวของ Vanya คือจากซ้ายไปขวา 73, 80 , 74 และ 136 ตามลำดับ) ยิ่งไปกว่านั้น ตามแผนผังเกม ผู้เล่นคนที่สองสามารถชนะได้ในการเคลื่อนไหวเพียงครั้งเดียว

ภารกิจที่ 2

วิธีแก้ปัญหาอย่างเป็นทางการ

พิจารณาตำแหน่งเริ่มต้น (6,32) โปรดทราบว่ามันใกล้กับ (6,33) จากภารกิจที่ 1 ในงานที่ 1 เราพบว่าในตำแหน่ง (6, 33) ครั้งที่สองชนะ และในการเคลื่อนไหวครั้งเดียว เงื่อนไขนี้สามารถกำหนดรูปแบบใหม่ได้: ในตำแหน่ง (6.33) ผู้ที่ชนะในการเคลื่อนไหวครั้งเดียวคือ ไม่เดิน (นั่นคือเดินที่สอง) หรืออีกนัยหนึ่งคือผู้ที่เคลื่อนไหวจะสูญเสียในการเคลื่อนไหวครั้งเดียว

ในตำแหน่ง (6.32) คนแรกชนะในสองการเคลื่อนไหว มาพิสูจน์กัน ในการเคลื่อนที่ครั้งแรก Petya จะเพิ่ม +1 ให้กับกองที่สอง จึงได้ตำแหน่ง (6.33) ดังที่เราทราบก่อนหน้านี้ ในตำแหน่ง (6,33) ผู้ที่เคลื่อนไหวจะสูญเสีย ในกรณีของเรา มันจะเป็นการเคลื่อนไหวของ Vanya ดังนั้น Vanya จะแพ้ในคราวเดียว ในกรณีนี้ Petya จะต้องเคลื่อนไหวทั้งหมดสองครั้ง: ครั้งแรก (เพิ่ม 1 หินลงในกองที่สอง) + การเคลื่อนไหวครั้งที่สองตาม Party Tree ในภารกิจที่ 1 ซึ่งดำเนินการตามกลยุทธ์ของ Vanya

ในตำแหน่งเดียวกัน (7, 32) ในการเคลื่อนไหวครั้งแรก Petya จะเพิ่มหิน +1 ให้กับกองแรกเพื่อรับตำแหน่ง (8, 32) ในตำแหน่งนี้ตามเหตุผลเดียวกันผู้ที่เคลื่อนไหวจะสูญเสีย มันจะเป็นการเคลื่อนไหวของ Vanya ดังนั้น Vanya จะแพ้ กลยุทธ์การชนะของ Petya มีดังนี้: Petya เพิ่มหิน +1 ให้กับกองแรก จากนั้นทำตามกลยุทธ์ของ Vanya จากภารกิจที่ 1

ในตำแหน่งเดียวกัน (8, 31) ในการเคลื่อนไหวครั้งแรก Petya จะเพิ่มหิน +1 ก้อนให้กับกองที่สอง เพื่อให้ได้ตำแหน่ง (8, 32) ในตำแหน่งนี้ ด้วยเหตุผลเดียวกัน ผู้ที่เคลื่อนไหวจะสูญเสีย มันจะเป็นการเคลื่อนไหวของ Vanya ดังนั้น Vanya จะแพ้ กลยุทธ์การชนะของ Petya มีดังนี้: Petya เพิ่มหิน +1 ก้อนให้กับกองที่สอง จากนั้นทำตามกลยุทธ์ของ Vanya จากภารกิจที่ 1

ภารกิจที่ 3

การอภิปราย

โปรดทราบว่าจากสถานการณ์ (7, 31) มันง่ายมากที่จะจบลงทั้งในสถานการณ์ (8, 31) และ (7, 32) ซึ่งตามงานก่อนหน้า ผู้ที่เคลื่อนไหวจะชนะหรือในสถานการณ์ ( เลข 14, 31) และ (7, 62) ซึ่งผู้ที่เคลื่อนไหวสามารถชนะในการเคลื่อนไหวครั้งเดียวโดยการเพิ่มจำนวนหินในกองที่สองเป็นสองเท่า ดังนั้นปรากฎว่า Vanya ต้องมีกลยุทธ์ในการชนะ ยิ่งไปกว่านั้น เขาสามารถชนะได้ทั้ง 2 กระบวนท่า (สองกรณีแรก) และในกระบวนท่าเดียว (สองกรณีหลัง)

วิธีแก้ปัญหาอย่างเป็นทางการ

ในตำแหน่งเริ่มต้น (7, 31) Vanya ชนะในหนึ่งหรือสองการเคลื่อนไหว มาพิสูจน์กัน เพื่อที่จะทำสิ่งนี้ เราจะสร้างแผนผังของทุกฝ่าย

แผนผังเกมทั้งหมดสำหรับตำแหน่งเริ่มต้น (7, 31)

ตามแผนผังของเกมทั้งหมด Vanya ชนะไม่ว่าจะในการเคลื่อนไหวครั้งเดียว (หาก Petya เพิ่มจำนวนหินเป็นสองเท่าในกองแรกหรือกองที่สอง) หรือในสองการเคลื่อนไหว (หาก Petya เพิ่มจำนวนก้อนหินในกองแรกหรือกองที่สอง 1) .

ดังนั้นในตำแหน่งเริ่มต้น (7, 31) Vanya จึงมีกลยุทธ์ที่จะชนะ และ Vanya จะชนะในหนึ่งหรือสองครั้ง

เยฟเจนี สมีร์นอฟ

ผู้เชี่ยวชาญด้านไอที ครูสอนวิทยาการคอมพิวเตอร์

บทเรียนครอบคลุมการวิเคราะห์ภารกิจที่ 26 ของการสอบ Unified State ในวิทยาการคอมพิวเตอร์: มีการให้คำอธิบายโดยละเอียดและแนวทางแก้ไขสำหรับงานปี 2560

ภารกิจที่ 26 - "ทฤษฎีเกม ค้นหากลยุทธ์ที่ชนะ" - มีลักษณะเป็นงาน ระดับสูงความซับซ้อน เวลาเสร็จสิ้น – ประมาณ 30 นาที คะแนนสูงสุด – 3

* รูปภาพและตัวอย่างหน้าบางส่วนนำมาจากสื่อการนำเสนอของ K. Polyakov

ทฤษฎีเกม ค้นหากลยุทธ์แห่งชัยชนะ

ในการแก้ไขภารกิจที่ 26 คุณต้องจำหัวข้อและแนวคิดต่อไปนี้:

กลยุทธ์การชนะ

• เพื่อค้นหากลยุทธ์การชนะในเกมง่าย ๆ ก็เพียงพอที่จะใช้วิธีการระบุตัวเลือกที่เป็นไปได้ทั้งหมดสำหรับการเคลื่อนไหวของผู้เล่น
• เพื่อแก้ปัญหา 26 งานมักใช้สำหรับสิ่งนี้ วิธีการก่อสร้างต้นไม้;
• หากกิ่งก้านสองกิ่งยื่นออกมาจากแต่ละโหนดของทรี นั่นคือ ตัวเลือกที่เป็นไปได้สำหรับการเคลื่อนไหว จากนั้นจึงเรียกต้นไม้ดังกล่าว ไบนารี่(หากมีทางเลือกต่อเนื่องสามทางจากแต่ละตำแหน่ง ต้นไม้จะเป็นแบบไตรภาค)

ตำแหน่งที่ชนะและแพ้

• ตำแหน่งทั้งหมดในเกมง่ายๆ แบ่งออกเป็นการชนะและแพ้
• ตำแหน่งที่ชนะ– นี่คือตำแหน่งที่ผู้เล่นที่เคลื่อนไหวครั้งแรกจะต้องชนะอย่างแน่นอนไม่ว่าฝ่ายตรงข้ามจะทำอะไร เว้นแต่ว่าเขาจะทำผิดพลาด ในขณะเดียวกันก็บอกว่านักเตะคนนี้มี กลยุทธ์การชนะ– อัลกอริธึมสำหรับการเลือกการเคลื่อนไหวครั้งต่อไปที่ทำให้เขาชนะ
• ถ้าผู้เล่นที่ทำการย้ายครั้งแรกเข้ามา สูญเสียตำแหน่งแล้วเขาจะแพ้อย่างแน่นอนเว้นแต่คู่ต่อสู้ของเขาจะทำผิดพลาด ในกรณีนี้ว่ากันว่านักเตะคนนี้มี ไม่มีกลยุทธ์ในการชนะ- ดังนั้นกลยุทธ์ทั่วไปของเกมคือการสร้างตำแหน่งที่แพ้ให้กับคู่ต่อสู้ด้วยการเคลื่อนไหวของคุณ
• ตำแหน่งที่ชนะและแพ้มีลักษณะดังนี้:
• ตำแหน่งที่การเคลื่อนไหวที่เป็นไปได้ทั้งหมดนำไปสู่ตำแหน่งที่ชนะ – การสูญเสีย;
• ตำแหน่งที่อย่างน้อยหนึ่งการเคลื่อนไหวที่เป็นไปได้ตามมาจะนำไปสู่การสูญเสียตำแหน่ง - ชนะและกลยุทธ์ของผู้เล่นก็คือ เปลี่ยนเกมให้เป็นฝ่ายแพ้(สำหรับฝ่ายตรงข้าม) ตำแหน่ง.

ใครจะชนะด้วยเกมที่ถูกต้องตามกลยุทธ์?

• เพื่อตัดสินว่าผู้เล่นคนใดจะชนะด้วยเกมที่ถูกต้อง จำเป็นต้องตอบคำถาม:
• ผู้เล่นคนใดสามารถชนะได้ ไม่ว่าผู้เล่นคนอื่นจะเคลื่อนไหวอย่างไร?
• ผู้เล่นที่มีกลยุทธ์ในการชนะจะต้องทำอะไรในการเคลื่อนไหวครั้งแรกเพื่อที่จะชนะ โดยไม่คำนึงถึงการกระทำของผู้เล่น?

ลองดูตัวอย่าง:

เกม:มี 5 แมตช์ในกอง; เล่นโดยผู้เล่นสองคนที่ผลัดกันเอาไม้ขีดออกจากกอง เงื่อนไข: ในการเคลื่อนไหวครั้งเดียวคุณสามารถลบการแข่งขัน 1 หรือ 2 นัด ผู้ชนะคือผู้ที่ออกจากการแข่งขัน 1 นัดในกอง

สารละลาย:

คำตอบ:ด้วยเกมที่ถูกต้อง (กลยุทธ์เกม) ผู้เล่นคนแรกจะชนะ เมื่อต้องการทำเช่นนี้ เขาต้องลบนัดเดียวในการเคลื่อนไหวครั้งแรกเท่านั้น

แก้งานสอบ Unified State 26 งานในสาขาวิทยาการคอมพิวเตอร์

การวิเคราะห์งานที่ 26 ของการสอบ Unified State ในวิทยาการคอมพิวเตอร์ 2017 FIPI ตัวเลือก 5 (Krylov S.S., Churkina T.E.):

ผู้เล่นสองคน Pasha และ Valya กำลังเล่นเกมต่อไปนี้ มีกองหินอยู่ข้างหน้าผู้เล่น ผู้เล่นผลัดกัน มหาอำมาตย์เริ่มการเคลื่อนไหวครั้งแรก หนึ่ง สองครั้ง. ตัวอย่างเช่น การมีก้อนหิน 7 กอง คุณก็จะได้ก้อนหิน 14 หรือ 8 ก้อนในการเคลื่อนไหวครั้งเดียวผู้เล่นแต่ละคนมีหินไม่จำกัดจำนวนในการเคลื่อนที่

เกมจะจบลงเมื่อจำนวนหินในกองกลายเป็นอย่างน้อย 28 - หากในเวลาเดียวกันมีไม่เกิน 44 สโตน ผู้ชนะคือผู้เล่นที่เคลื่อนไหวครั้งสุดท้าย ใน มิฉะนั้นคู่ต่อสู้ของเขากลายเป็นผู้ชนะ ตัวอย่างเช่น หากมีหิน 23 ก้อนในกอง และ Pasha เพิ่มจำนวนหินในกองเป็นสองเท่า เกมจะจบลงและ Valya จะเป็นผู้ชนะในตอนแรกมีหิน S อยู่ในกอง 1≤ ส ≤ 27.

ภารกิจที่ 1
ก) มีค่าเท่ากับเท่าใด สมหาอำมาตย์สามารถชนะได้ในกระบวนท่าเดียวหรือไม่? แสดงรายการค่าดังกล่าวทั้งหมดและการเคลื่อนไหวที่เกี่ยวข้องของ Pasha
b) ผู้เล่นคนไหนมีกลยุทธ์ในการชนะเมื่อใด ส = 26, 25, 24- อธิบายกลยุทธ์ในการชนะสำหรับกรณีเหล่านี้

ภารกิจที่ 2
ส = 13, 12- อธิบายกลยุทธ์การชนะที่เกี่ยวข้อง

ภารกิจที่ 3
ผู้เล่นคนไหนมีกลยุทธ์ในการชนะเมื่อ ส=11- สร้างแผนผังของเกมทั้งหมดที่เป็นไปได้ด้วยกลยุทธ์แห่งชัยชนะ (ในรูปแบบของรูปภาพหรือตาราง) ที่ขอบต้นไม้แสดงว่าใครกำลังเคลื่อนไหว ในโหนด - จำนวนหินในตำแหน่ง

✍ วิธีแก้ไข:

สำหรับคำอธิบายโดยละเอียดของภารกิจที่ 26 ของการสอบ Unified State โปรดดูวิดีโอ:

การวิเคราะห์ภารกิจที่ 26 ของการสอบ Unified State ในวิทยาการคอมพิวเตอร์ 2017 (หนึ่งในตัวเลือกตามผู้สำเร็จการศึกษา):

Petya และ Vanya เล่นเกม: มีชุดคำคุณต้องตั้งชื่อตัวอักษรของคำเหล่านี้อย่างสม่ำเสมอ ผู้ชนะคือผู้เล่นที่ตั้งชื่อตัวอักษรตัวสุดท้ายของคำใดๆ จากชุด เพชรยาไปก่อน.

เช่น มีชุดคำ (หมาป่า, วิทยาการคอมพิวเตอร์, น่ากลัว)- สำหรับชุดคำที่กำหนด Petya สามารถตั้งชื่อตัวอักษรได้ด้วยการเคลื่อนไหวครั้งแรก ใน, และหรือ กับ- ถ้าเพชรยาเลือกจดหมาย ในจากนั้น Vanya จะชนะ (กระบวนท่าถัดไป: Petya - ใน, วานย่า - เกี่ยวกับ, เพชรยา - ล, วานย่า - ถึง).

ภารกิจที่ 1
A) ให้คำ 2 คำ (ชุดตัวอักษร) ( IKLMNIKLMNH, NMLKINMLKI- กำหนดกลยุทธ์แห่งชัยชนะ

B) ให้ 2 คำ ( ไตรไตรตรี...สาม, ริต้าริต้าริต้าริต้า...ริต้า- ในคำแรก 99 ตัวอักษรในวินาที 164 - กำหนดกลยุทธ์แห่งชัยชนะ

ภารกิจที่ 2
จำเป็นต้องสลับตัวอักษรสองตัวจากชุดรายการ 1เอในคำที่มีความยาวสั้นที่สุดเพื่อให้กลยุทธ์การชนะเป็นผู้เล่นคนอื่น อธิบายกลยุทธ์แห่งชัยชนะ

ภารกิจที่ 3
ให้ชุดของคำ ( อีกา, หมาป่า, คลื่น, อนุพันธ์, โปรโคร์, ข้าวฟ่าง- ผู้เล่นคนไหนมีกลยุทธ์ในการชนะ? พิสูจน์คำตอบของคุณและเขียนแผนผังของเกมที่เป็นไปได้ทั้งหมดเพื่อกลยุทธ์ในการชนะ

✍ วิธีแก้ไข:

* สำหรับ Vanya จะแสดงเฉพาะการเคลื่อนไหวของกลยุทธ์เท่านั้น
**วงกลมสีแดงหมายถึงชนะ

สำหรับรายละเอียดเพิ่มเติมเกี่ยวกับการแก้ปัญหาคำศัพท์ โปรดดูวิดีโอบทช่วยสอน:

โซลูชันที่ 26 วิทยาการคอมพิวเตอร์ Unified State Exam 2018 เวอร์ชันสาธิต:

ผู้เล่นสองคน Petya และ Vanya เล่นเกมต่อไปนี้ มีกองหินอยู่ข้างหน้าผู้เล่น ผู้เล่นผลัดกัน Petya เคลื่อนไหวครั้งแรก ในเทิร์นหนึ่ง ผู้เล่นสามารถเพิ่มลงในกองได้ หนึ่งหินหรือเพิ่มจำนวนหินในกอง สองครั้ง. ตัวอย่างเช่น ถ้าคุณมีกองหิน 15 ก้อน คุณสามารถมีกองหิน 16 หรือ 30 ก้อนในการย้ายครั้งเดียวผู้เล่นแต่ละคนมีหินไม่จำกัดจำนวนในการเคลื่อนที่

เกมจะจบลงเมื่อจำนวนหินในกองกลายเป็น อย่างน้อย 29- ผู้ชนะคือผู้เล่นที่เคลื่อนไหวครั้งสุดท้าย นั่นคือคนแรกที่ได้รับกองที่มีหิน 29 ก้อนขึ้นไป ในตอนแรกมีหิน S อยู่ในกอง 1 ≤ ส ≤ 28.

เราจะบอกว่าผู้เล่นมีกลยุทธ์ในการชนะหากเขาสามารถชนะด้วยการเคลื่อนไหวของคู่ต่อสู้ การอธิบายกลยุทธ์ของผู้เล่นหมายถึงการอธิบายว่าเขาควรเคลื่อนไหวอะไรในสถานการณ์ใดๆ ที่เขาอาจเผชิญกับการเล่นที่แตกต่างจากคู่ต่อสู้ คำอธิบายของกลยุทธ์การชนะ ไม่ควรรวมถึงการเคลื่อนไหวของผู้เล่นที่เล่นตามกลยุทธ์นี้ที่ไม่ชนะเขาอย่างไม่มีเงื่อนไขเช่น ไม่ชนะโดยไม่คำนึงถึงการเล่นของฝ่ายตรงข้าม

ภารกิจที่ 1
ก)ระบุค่าดังกล่าวของหมายเลข S ที่ Petya สามารถชนะได้ในครั้งเดียว
ข)ระบุค่าของ S เพื่อให้ Petya ไม่สามารถชนะได้ในการเคลื่อนไหวครั้งเดียว แต่สำหรับการเคลื่อนไหวใดๆ ที่ Petya ทำ Vanya สามารถชนะได้ด้วยการเคลื่อนไหวครั้งแรก อธิบายกลยุทธ์แห่งชัยชนะของ Vanya

ภารกิจที่ 2
ระบุค่า S สองค่าดังกล่าวซึ่ง Petya มีกลยุทธ์ในการชนะ และ:
— Petya ไม่สามารถชนะได้ในกระบวนท่าเดียว
- Petya สามารถชนะได้ด้วยการเคลื่อนไหวครั้งที่สอง ไม่ว่า Vanya จะเคลื่อนไหวอย่างไรก็ตาม
สำหรับค่าที่กำหนดของ S ให้อธิบายกลยุทธ์การชนะของ Petit

ภารกิจที่ 3
ระบุค่าของ S โดยที่:
— Vanya มีกลยุทธ์ในการชนะที่ทำให้เขาชนะด้วยการเคลื่อนไหวครั้งแรกหรือครั้งที่สองในเกมของ Petya
— Vanya ไม่มีกลยุทธ์ที่จะรับประกันว่าเขาจะต้องชนะในการเคลื่อนไหวครั้งแรก

สำหรับค่าที่กำหนดของ S ให้อธิบายกลยุทธ์การชนะของ Vanya สร้างแผนผังของเกมทั้งหมดที่เป็นไปได้ด้วยกลยุทธ์แห่งชัยชนะ (ในรูปแบบของรูปภาพหรือตาราง) ที่ขอบต้นไม้แสดงว่าใครกำลังเคลื่อนไหว ในโหนด - จำนวนสโตนในตำแหน่ง

ต้นไม้ไม่ควรมีเกมที่เป็นไปไม่ได้หากผู้เล่นที่ชนะใช้กลยุทธ์การชนะของเขา ตัวอย่างเช่น แผนผังเกมที่สมบูรณ์ไม่ใช่คำตอบที่ถูกต้องสำหรับงานนี้

✍ วิธีแก้ไข:

ภารกิจที่ 1
• ก) Petya สามารถชนะได้หาก ส = 15, … 28

15, ..., 28 - ตำแหน่งที่ชนะตั้งแต่การย้ายครั้งแรก

b) Vanya สามารถชนะได้ด้วยการเคลื่อนไหวครั้งแรก (ไม่ว่า Petya จะเล่นอย่างไร) หากมี ส=14หิน หลังจากการเคลื่อนไหวครั้งแรกของ Petya จะมีหิน 15 หรือ 28 ก้อนอยู่ในกอง ในทั้งสองกรณี Vanya จะเพิ่มฮีปเป็นสองเท่าและชนะในครั้งเดียว

S = 14 Petya: 14 + 1 = 15 ตำแหน่งที่ชนะ (ดูจุด a) Vanya Petya ชนะ: 14 * 2 = 28 ตำแหน่งที่ชนะ (ดูจุด a) Vanya ชนะ 14 - แพ้ตำแหน่ง

ภารกิจที่ 2

ค่าที่เป็นไปได้ ส: 7, 13- ในกรณีเหล่านี้ Petya ไม่สามารถชนะได้อย่างชัดเจนในการเคลื่อนไหวครั้งแรก อย่างไรก็ตาม เขาสามารถเก็บหินได้ 14 กอง ในกรณีแรกเพิ่มเป็นสองเท่า ในกรณีที่สองโดยเพิ่มหิน 1 ก้อน ตำแหน่งนี้จะกล่าวถึงในวรรค 1b ในนั้นผู้เล่นที่จะเคลื่อนไหว (ตอนนี้ Vanya) ไม่สามารถชนะได้ แต่คู่ต่อสู้ของเขา (นั่นคือ Petya) จะชนะในการเคลื่อนไหวครั้งต่อไป

S = 7 Petya: 7 * 2 = 14 ตำแหน่งที่สูญเสีย (ดูจุดที่ 1 b) Petya ชนะ S = 13 Petya: 13 + 1 = 14 แพ้ตำแหน่ง (ดูจุดที่ 1 b) Petya ชนะ 7, 13 - ชนะตำแหน่งจากการย้ายครั้งที่สอง

ภารกิจที่ 3

ค่าที่เป็นไปได้ ส: 12- หลังจากการเคลื่อนไหวครั้งแรกของ Petya จะมีหิน 13 หรือ 24 ก้อนในกอง หากมี 24 ก้อนในกอง Vanya จะเพิ่มจำนวนหินเป็นสองเท่าและชนะในการเคลื่อนไหวครั้งแรก สถานการณ์เมื่อมีหิน 13 ก้อนในฮีปได้รับการจัดการในวรรค 2 ในสถานการณ์นี้ผู้เล่นที่จะเคลื่อนไหว (ตอนนี้คือ Vanya) ชนะด้วยการเคลื่อนไหวครั้งที่สอง

S = 12 Petya: 12 + 1 = 13 Vanya: 13 + 1 = 14 เสียตำแหน่ง (ดูจุดที่ 1 b) วานย่าชนะ ที่สองขณะเดินทาง!

ตารางแสดงแผนผังของเกมที่เป็นไปได้ (และเฉพาะเกมเท่านั้น) สำหรับกลยุทธ์ที่ Vanya อธิบายไว้ ตำแหน่งสุดท้าย (Vanya ชนะในนั้น) จะถูกขีดเส้นใต้ ในรูปมีการแสดงต้นไม้ต้นเดียวกันเป็นภาพกราฟิก


แผนผังของเกมทั้งหมดที่เป็นไปได้ด้วยกลยุทธ์ของ Vanya:

*วงกลมสีแดงหมายถึงชนะ

การสอบเบื้องต้นด้านวิทยาการคอมพิวเตอร์ปี 2561 ตัวเลือกที่ 1 ภารกิจที่ 26:

ผู้เล่นสองคนคือ Pasha และ Vasya กำลังเล่นเกมต่อไปนี้ มีกองหินอยู่ข้างหน้าผู้เล่น ผู้เล่นผลัดกัน มหาอำมาตย์เริ่มการเคลื่อนไหวครั้งแรก- ในเทิร์นหนึ่ง ผู้เล่นสามารถเพิ่มลงในกองได้ หนึ่งหรือ สี่หินหรือ เพิ่มจำนวนก้อนหินในกองห้าเท่า- เกมจะจบลงเมื่อถึงจำนวนหิน ฮีปจะมีอย่างน้อย 69.
ผู้ชนะคือผู้เล่นที่เคลื่อนไหวครั้งสุดท้าย นั่นคือคนแรกที่ได้รับกองที่มีหิน 69 ก้อนขึ้นไป ในตอนแรกมีหิน S อยู่ในกอง 1 ≤ ส ≤ 68.

ภารกิจที่ 1
ก)ระบุค่าทั้งหมดของหมายเลข S ที่มหาอำมาตย์สามารถชนะได้ในครั้งเดียว แสดงให้เห็นว่าพบค่าที่ต้องการทั้งหมดของ S และระบุการเคลื่อนไหวที่ชนะสำหรับแต่ละค่าที่ระบุของ S

ข)ระบุค่าของ S เพื่อให้ Pasha ไม่สามารถชนะได้ในการเคลื่อนไหวครั้งเดียว แต่ด้วยการเคลื่อนไหวใด ๆ ของ Pasha วาสยาสามารถชนะได้ในการเคลื่อนไหวครั้งแรก อธิบายกลยุทธ์แห่งชัยชนะของวาสยา

ภารกิจที่ 2ระบุ 2 ค่าดังกล่าวของ S ที่ Pasha มีกลยุทธ์ในการชนะ และ Pasha ไม่สามารถชนะได้ในกระบวนท่าเดียวและสามารถชนะได้ด้วยกระบวนท่าที่สอง ไม่ว่า Vasya จะเคลื่อนไหวอย่างไร สำหรับแต่ละค่าของ S ให้อธิบายกลยุทธ์การชนะของมหาอำมาตย์

ภารกิจที่ 3ระบุค่า S อย่างน้อยหนึ่งค่าซึ่ง Vasya มีกลยุทธ์ในการชนะที่ทำให้เขาชนะด้วยการเคลื่อนไหวครั้งแรกหรือครั้งที่สองในเกมของ Pasha และ Vasya ไม่มีกลยุทธ์ที่จะทำให้เขาชนะด้วยการเคลื่อนไหวครั้งแรก สำหรับค่า S ที่ระบุ ให้อธิบายกลยุทธ์การชนะของ Vasya สร้างแผนผังของเกมทั้งหมดที่เป็นไปได้ด้วยกลยุทธ์แห่งชัยชนะของ Vasya (ในรูปแบบของรูปภาพหรือตาราง)

✍ วิธีแก้ไข:

1.
ก) ส ≥ 14- หากจำนวนหินในกองคือ 14 ก้อนขึ้นไป Pasha จะต้องเพิ่มจำนวนห้าครั้งจึงจะได้หิน 70 ก้อนขึ้นไป

S ≥ 14 ตำแหน่งที่ชนะ

ข) ส=13- มหาอำมาตย์สามารถสร้างหินได้ 14, 17 หรือ 65 ก้อนในการเคลื่อนไหวครั้งแรก หลังจากนั้นวาสยาจะเพิ่มจำนวนห้าครั้งโดยได้หิน 70, 85 หรือ 325 ก้อนในกอง

S = 13 Pasha การเคลื่อนไหวครั้งที่ 1: 13 + 1 = 14 Pasha การเคลื่อนไหวครั้งที่ 1: 13 + 4 = 17 Pasha การเคลื่อนไหวครั้งที่ 1: 13 * 5 = 65 Vanya การเคลื่อนไหวครั้งที่ 1: * 5 = S ≥ 14 Vanya ชนะ 13 - สูญเสียตำแหน่ง

2. ส = 9, 12- ในกรณีเหล่านี้ Pasha ต้องเพิ่มหิน 4 ก้อนลงในกองหิน 9 ก้อน หรือ 1 ก้อนต่อกองหิน 12 ก้อน และรับกองหิน 13 ก้อน
หลังจากนั้นเกมก็มาถึงกลยุทธ์ที่อธิบายไว้ในย่อหน้า 1ข.

S = 13 Pasha การเคลื่อนไหวครั้งที่ 1: 9 + 4 = 13 Pasha ชนะ Pasha การเคลื่อนไหวครั้งที่ 1: 12 + 1 = 13 Pasha ชนะ 9, 12 - ตำแหน่งที่ชนะจากการเคลื่อนไหวครั้งที่สอง

3. ส=8- ด้วยการเคลื่อนไหวครั้งแรก Pasha สามารถสร้างจำนวนหินในกองได้ 9, 12 หรือ 40 หาก Pasha เพิ่มจำนวนห้าครั้ง Vasya จะชนะในการเคลื่อนไหวครั้งแรกโดยเพิ่มจำนวนหินขึ้นห้าเท่า
สำหรับกรณีหิน 9 และ 12 ก้อน วาสยาใช้กลยุทธ์ที่ระบุไว้ใน ข้อ 2.

S = 8 Pasha การเคลื่อนไหวครั้งที่ 1: 8 + 1 = 9 Vanya ชนะ (ดูจุดที่ 2) Pasha การเคลื่อนไหวครั้งที่ 1: 8 + 4 = 12 Vanya ชนะ (ดูจุดที่ 2) Pasha การเคลื่อนไหวครั้งที่ 1: 8 * 5 = 40

ดูวิดีโอเพื่อดูวิธีแก้ปัญหาสำหรับงานที่ 26:

เครื่องจำลองการสอบ Unified State ในวิทยาการคอมพิวเตอร์ 2018 เวอร์ชันทดสอบ 1 ภารกิจ 26 (Krylov S. , Ushakov D. ):

หินหนึ่งก้อนหรือ . เกมจะจบลงในขณะที่จำนวนหินทั้งหมดในกองกลายเป็น อย่างน้อย 73.
ผู้ชนะคือผู้เล่นที่เคลื่อนไหวครั้งสุดท้าย เช่น คนแรกที่ได้รับตำแหน่งดังกล่าวกองจะมีหิน 73 ก้อนขึ้นไป

ภารกิจที่ 1
(6, 33), (8, 32) ระบุว่าผู้เล่นคนใดมีกลยุทธ์ในการชนะ ในแต่ละกรณี ให้อธิบายกลยุทธ์แห่งชัยชนะ อธิบายว่าเหตุใดกลยุทธ์นี้จึงนำไปสู่การชนะและระบุว่าอะไร จำนวนมากที่สุดอาจจำเป็นต้องมีการเคลื่อนไหวเพื่อให้ผู้ชนะชนะด้วยกลยุทธ์นี้

ภารกิจที่ 2
สำหรับแต่ละตำแหน่งเริ่มต้น (6, 32), (7, 32), (8, 31) ระบุว่าผู้เล่นคนใดมีกลยุทธ์ในการชนะ

ภารกิจที่ 3
สำหรับตำแหน่งเริ่มต้น (7, 31) ระบุว่าผู้เล่นคนใดมีกลยุทธ์ในการชนะ สร้างแผนผังของเกมทั้งหมดที่เป็นไปได้ด้วยกลยุทธ์การชนะที่คุณระบุ ลองนึกภาพต้นไม้เป็นรูปภาพหรือตาราง

✍ วิธีแก้ไข:

โซลูชันวิดีโอสำหรับงาน 26 ที่มีสองฮีป:

26_6: การวิเคราะห์ภารกิจ 26 จากเว็บไซต์ของ K. Polyakov (หมายเลข 31):

ผู้เล่นสองคน Petya และ Vanya เล่นเกมต่อไปนี้ ด้านหน้าของผู้เล่นมีกองหินสองกอง ผู้เล่นผลัดกัน Petya เคลื่อนไหวครั้งแรก ในเทิร์นหนึ่ง ผู้เล่นสามารถเพิ่มกองใดกองหนึ่งได้ (ตามที่เขาเลือก) หินสองก้อนหรือ จำนวนหินในกองเป็นสองเท่า- เพื่อที่จะเคลื่อนไหว ผู้เล่นแต่ละคนจะมีหินไม่จำกัดจำนวน เกมจะจบลงในขณะที่จำนวนหินทั้งหมดในกองกลายเป็น อย่างน้อย 44.
ผู้ชนะคือผู้เล่นที่เคลื่อนไหวครั้งสุดท้าย เช่น คนแรกที่ได้รับตำแหน่งที่กองจะมีหิน 44 ก้อนขึ้นไป

ในช่วงแรกในฮีปแรกก็มี 5 ก้อนในฮีปที่สอง – สหิน; 1 ≤ ส ≤ 38.
ภารกิจที่ 1
ที่อะไรส: 1ก) Petya ชนะด้วยการเคลื่อนไหวครั้งแรก 1ข) Vanya ชนะด้วยการเคลื่อนไหวครั้งแรกหรือไม่?

ภารกิจที่ 2
ตั้งชื่อค่าใดค่าหนึ่ง สซึ่ง Petya สามารถชนะได้ด้วยการเคลื่อนไหวครั้งที่สอง

ภารกิจที่ 3
ให้ค่าของ S ที่ Vanya ชนะในการเคลื่อนไหวครั้งแรกหรือครั้งที่สอง

✍ วิธีแก้ไข:

5 + 20*2 = 45 (>44) * 5 - จำนวนหินในฮีปแรกไม่เปลี่ยนแปลงตามเงื่อนไข

ตามนั้นทุกค่า ใหญ่ 20จะส่งผลให้มีจำนวนมากขึ้น 44 - มาระบุสิ่งนี้ในตาราง + หมายถึง ตำแหน่งที่ชนะตั้งแต่การย้ายครั้งแรก:

ตอบ 1 ก): ส= (ในการสอบ Unified State ให้อธิบายการเคลื่อนไหว เช่น (5; 20) -> (การเคลื่อนไหวของ Petit) -> (5; 40); 40 + 5 = 45)

งาน 1 ข):

เนื่องจาก Vanya จะขึ้นอันดับสอง จึงจำเป็นต้องเปลี่ยนจำนวนหินในกองแรก ลองพิจารณาสถานการณ์ที่ Petya สามารถย้ายเข้ามาก่อนได้ (7;ส)และใน (10;ส)- ให้เราระบุว่าตำแหน่งเหล่านี้จะชนะในการเคลื่อนไหวครั้งเดียวหรือไม่: ตัวอย่างเช่น (7;19) ตำแหน่งที่ชนะเพราะว่า ผู้เล่นจะย้ายเข้า (7;38) และจะชนะ (7 + 38 = 45) ดังนั้นทุกตำแหน่งจึงเป็นผู้ชนะ (7;มากกว่า 19)- มาวิเคราะห์ตารางกัน เพิ่มจำนวนหมากในกองแรกและค้นหาตำแหน่งที่ชนะในคราวเดียว:

ตรรกะของการให้เหตุผลต่อไปนี้: Vanya สามารถชนะได้ด้วยการเคลื่อนไหวครั้งแรก ในขณะที่ Petya ที่มีการเคลื่อนไหวครั้งแรกสามารถย้ายไปยังตำแหน่งที่ชนะได้ตั้งแต่การเคลื่อนไหวครั้งแรกเท่านั้น (ใน +) เรามาทำเครื่องหมายตำแหน่งเหล่านี้โดยคำนึงว่านี่คือการเคลื่อนไหวครั้งแรกของ Petya และจำนวนหินในกองแรกควรเป็น 5 ตำแหน่งที่พบจะสูญเสียตำแหน่ง (-):

เราพบค่าดังกล่าวเท่านั้น - (5; 19) เหล่านั้น. ส = 19.

ตอบ 1 ข): ส=19 (ในการสอบ Unified State ให้อธิบายการเคลื่อนไหว เช่น (5; 19) -> (การเคลื่อนไหวของ Petya): (5;21),(5;28);(7;19);(7;28) Vanya จะชนะทุกที่ในท่าถัดไป ดูย่อหน้าก่อนหน้า)

ภารกิจที่ 2:

โปรดทราบว่าในตาราง "มุม" ที่เกิดขึ้นทั้งหมดจะสูญเสียตำแหน่ง (ตั้งแต่การเคลื่อนไหวครั้งแรก): นั่นคือหากผู้เล่นพบว่าตัวเองอยู่ในตำแหน่งดังกล่าว เขาสามารถย้ายไปยังตำแหน่งที่ชนะเท่านั้น (นั่นคือคู่ต่อสู้ จะชนะในครั้งต่อไป) :

ตรรกะของการให้เหตุผล: Petya จะสามารถชนะได้ในการเคลื่อนไหวครั้งที่สอง เมื่อการเคลื่อนไหวครั้งแรกของเขาจบลงในตำแหน่งที่พ่ายแพ้ กล่าวคือ จะทำให้คู่ต่อสู้ของคุณตกอยู่ในสถานการณ์ที่พ่ายแพ้ ค่าเหล่านี้คือ: S = 16, 17 หรือ 18 เรียกตำแหน่งเหล่านี้ว่าชนะจากการย้ายครั้งที่สอง (2+):

คำตอบ 2: ส = 16, 17 หรือ 18

ภารกิจที่ 3:

ให้เราระบุในตำแหน่งตารางที่ชนะจากการเคลื่อนไหวครั้งที่ n: เมื่อผู้เล่นสามารถโอนคู่ต่อสู้ไปยังตำแหน่งที่แพ้:

ให้เราระบุตำแหน่งที่แพ้จากการย้ายครั้งที่สองด้วย: ผู้เล่นที่พบว่าตัวเองอยู่ในตำแหน่งดังกล่าวสามารถย้ายไปยังตำแหน่งที่ชนะเท่านั้น (จากนั้นฝ่ายตรงข้ามจะชนะ):

ตรรกะของการให้เหตุผล: Vanya สามารถชนะได้ด้วยการเคลื่อนไหวครั้งแรกหรือครั้งที่สอง เมื่อ Petya สามารถโจมตีได้ด้วยการเคลื่อนไหวครั้งแรก เท่านั้นไปยังตำแหน่งที่ชนะจากการเคลื่อนไหวครั้งแรก (+) หรือไปยังตำแหน่งที่ชนะจากการเคลื่อนไหวครั้งที่สองหรือการเคลื่อนไหวครั้งที่ n (2+) นี่คือตำแหน่งที่ S = 14:

คำตอบ 3: ส=14 (ในการสอบ Unified State อธิบายความเคลื่อนไหวโดยอ้างอิงคำอธิบายในย่อหน้าที่แล้ว)

การวิเคราะห์งานที่ 26 ของการสอบ Unified State ในสาขาวิทยาการคอมพิวเตอร์ปี 2017 จากเวอร์ชันสาธิต นี่เป็นงานจากส่วนที่สองของความยากระดับสูง เวลาโดยประมาณในการทำงานให้เสร็จสิ้นคือ 30 นาที คะแนนสูงสุดสำหรับการทำงานให้สำเร็จคือ 3

องค์ประกอบเนื้อหาที่ตรวจสอบ:
— ความสามารถในการสร้างแผนผังเกมตามอัลกอริธึมที่กำหนดและปรับกลยุทธ์การชนะ

ภารกิจที่ 26

ผู้เล่นสองคน Pasha และ Valya กำลังเล่นเกมต่อไปนี้ มีกองหินอยู่ข้างหน้าผู้เล่น ผู้เล่นผลัดกัน Pasha ทำการเคลื่อนไหวครั้งแรก ในเทิร์นหนึ่ง ผู้เล่นสามารถเพิ่มลงในกองได้ หนึ่งหินหรือเพิ่มจำนวนหินในกอง สองครั้ง- ตัวอย่างเช่น ถ้าคุณมีกองหิน 15 ก้อน คุณสามารถมีกองหิน 16 หรือ 30 ก้อนในการย้ายครั้งเดียว ผู้เล่นแต่ละคนมีหินไม่จำกัดจำนวนในการเคลื่อนที่
เกมจะจบลงในขณะที่จำนวนหินในกองมีอย่างน้อย 20 ก้อน หากในเวลาเดียวกันมีหินในกองไม่เกิน 30 ก้อน ผู้เล่นที่เคลื่อนไหวครั้งสุดท้ายถือเป็นผู้ชนะ มิฉะนั้นคู่ต่อสู้ของเขาจะกลายเป็นผู้ชนะ ตัวอย่างเช่น หากมีหิน 17 ก้อนในกองและ Pasha เพิ่มจำนวนหินในกองเป็นสองเท่า เกมจะจบลงและ Valya จะเป็นผู้ชนะ ในช่วงแรกมีอยู่ในกอง สหิน 1 ≤ S ≤ 19

เราจะบอกว่านักพนันได้ กลยุทธ์การชนะหากเขาสามารถชนะด้วยการเคลื่อนไหวใด ๆ ของคู่ต่อสู้ การอธิบายกลยุทธ์ของผู้เล่นหมายถึงการอธิบายว่าเขาควรเคลื่อนไหวอย่างไรในสถานการณ์ใดๆ ที่เขาอาจเผชิญกับการเล่นที่แตกต่างจากศัตรู

ทำงานต่อไปนี้ให้เสร็จสิ้น
1.ก) มีค่าเท่ากับเท่าใด สมหาอำมาตย์สามารถชนะได้ในกระบวนท่าเดียวหรือไม่?
แสดงรายการค่าดังกล่าวทั้งหมดและการเคลื่อนไหวที่เกี่ยวข้องของ Pasha
b) ผู้เล่นคนไหนมีกลยุทธ์ในการชนะเมื่อใด ส = 18, 17, 16?
อธิบายกลยุทธ์ในการชนะสำหรับกรณีเหล่านี้
2. ผู้เล่นคนไหนมีกลยุทธ์ในการชนะเมื่อ ส= 9.8? อธิบายกลยุทธ์การชนะที่เกี่ยวข้อง
3. ผู้เล่นคนไหนมีกลยุทธ์ในการชนะเมื่อ ส= 7? สร้างแผนผังของเกมทั้งหมดที่เป็นไปได้ด้วยกลยุทธ์แห่งชัยชนะ (ในรูปแบบของรูปภาพหรือตาราง) ที่ขอบต้นไม้แสดงว่าใครกำลังเคลื่อนไหว ในโหนด – จำนวนสโตนในตำแหน่ง

1. ก) มหาอำมาตย์สามารถชนะได้ถ้า ส= 19 หรือ ส= 10, 11, 12, 13, 14, 15. เมื่อใด ส= 19 ก้าวแรกคือเพิ่มหินหนึ่งก้อนลงในกองโดยระบุค่าที่เหลือ สคุณต้องเพิ่มจำนวนหินเป็นสองเท่า

ข) เมื่อใด ส= 16, 17 หรือ 18 การเพิ่มจำนวนหินเป็นสองเท่าไม่สมเหตุสมผลเนื่องจากหลังจากการเคลื่อนไหวดังกล่าวคู่ต่อสู้จะชนะ ดังนั้นเราจึงสรุปได้ว่าวิธีเดียวที่เป็นไปได้คือเพิ่มหินหนึ่งก้อนลงในกอง

ที่ ส= 18 หลังจากที่มหาอำมาตย์เคลื่อนไหวเช่นนี้ จะมีหิน 19 ก้อนในกอง ในตำแหน่งนี้ผู้ที่เดิน (เช่นวัลยา) เป็นผู้ชนะ (ดูข้อ 1a): ที่ ส= 18 มหาอำมาตย์ (ผู้เล่นที่ต้องไปก่อน) แพ้

วัลยามีกลยุทธ์แห่งชัยชนะ

ที่ ส= 17 หลังจากที่มหาอำมาตย์เพิ่มหินหนึ่งก้อนในการเคลื่อนไหวครั้งแรก จะมีหิน 18 ก้อนในกอง ในตำแหน่งนี้ ผู้เล่น (เช่น วัลยา) จะแพ้ (ดูด้านบน): ที่ ส= 17 Pasha (ผู้เล่นที่ต้องไปก่อน) ชนะ มหาอำมาตย์มีกลยุทธ์แห่งชัยชนะ

ที่ ส= 16 วัลยามีกลยุทธ์แห่งชัยชนะ อันที่จริงถ้ามหาอำมาตย์เพิ่มจำนวนหินเป็นสองเท่าในการเคลื่อนไหวครั้งแรก กองนั้นก็จะกลายเป็น 32 ก้อน และเกมจะจบลงทันทีเมื่อวาลีชนะ ถ้ามหาอำมาตย์เพิ่มหินหนึ่งก้อน กองจะกลายเป็น 17 ก้อน ดังที่เราทราบแล้ว ในตำแหน่งนี้ ผู้เล่นที่ต้องเคลื่อนไหว (เช่น วาลยา) จะเป็นผู้ชนะ

ในทุกกรณี การชนะจะเกิดขึ้นได้ก็ต่อเมื่อในระหว่างการเคลื่อนไหว ผู้เล่นที่มีกลยุทธ์ในการชนะจะต้องเพิ่มหินหนึ่งก้อนลงในกอง

เป็นไปได้ที่จะวาดแผนผังของฝ่ายที่เป็นไปได้ทั้งหมดตามค่าที่ระบุ ส.
ความเป็นไปได้อีกอย่างหนึ่งคือ (1) ชี้ให้เห็นว่าการเพิ่มฮีปเป็นสองเท่านั้นไม่สมเหตุสมผล และ (2) ลดขนาดเคสตามลำดับ ส= 18 ต่อกรณี ส= 19 กรณี ส= 17 – ถึงโอกาส ส= 18 เป็นต้น

2. เมื่อไหร่ ส= 9 หรือ 8 Pasha มีกลยุทธ์ในการชนะ ประกอบด้วยการเพิ่มจำนวนหินในกองเป็นสองเท่าและรับกองซึ่งจะมี 18 หรือ 16 ก้อนตามลำดับ ในทั้งสองกรณี ผู้เล่นที่เคลื่อนไหว (ปัจจุบันคือวัลยา) จะแพ้ (ดูข้อ 1b).

3. เมื่อไหร่ ส= 7 วาลยามีกลยุทธ์แห่งชัยชนะ หลังจากการเคลื่อนไหวครั้งแรกของ Pasha กองสามารถมีหินได้ 8 หรือ 14 ก้อน ในทั้งสองตำแหน่งนี้ ผู้เล่นที่เคลื่อนไหว (ปัจจุบันคือ วัลยา) จะเป็นผู้ชนะ กำลังเกิดขึ้น ส= 8 พิจารณาแล้ว ในจุดที่ 2, กรณี ส= 14 รีวิวแล้ว ในจุดที่ 1a.

ตารางแสดงแผนผังของเกมที่เป็นไปได้สำหรับกลยุทธ์ที่อธิบายไว้ของ Vali ตำแหน่งสุดท้าย (วัลยาชนะในตำแหน่งนั้น) จะถูกขีดเส้นใต้ ในภาพ มีการแสดงต้นไม้ต้นเดียวกันเป็นภาพกราฟิก (ยอมรับได้ทั้งสองวิธีในการแสดงภาพต้นไม้)

แผนผังของเกมทั้งหมดที่เป็นไปได้ภายใต้กลยุทธ์ของ Valya เครื่องหมาย >> ระบุตำแหน่งที่เกมจบลง