1. [4 pt] The Hidden Leaf Village is organising the Chunin exam. candidate ninja needs to...

Transcribed Image Text:

1. [4 pt] The Hidden Leaf Village is organising the Chunin exam. candidate ninja needs to fight with all other candidates one on one. Each (a) [1 pt] Suppose that three ninjas, Naruto, Sasuke, and Gaara are the only candidates. Show that when all the three fights are finished, we can always put these three ninjas in a queue, so that each ninja defeats the one who is standing right behind him/her (see Figure 2). (b) [3 pt] Now suppose that n ninjas are participating in the Chunin exam. i. [1 pt] Show that there will be n(n - 1) fights. (a) Naruto 411 (b) Gaara (c) Sasuke Figure 2: Three candidates of Chunin exam standing in the queue, given that Naruto beats Gaara, Gaara beats Sasuke, Sasuke beats Naruto. ii. [2 pt] Show that when all the fights are finished, we can always put these three ninjas in a queue, so that each ninja defeats the one who is standing right behind him/her (i.e., the 1st ninja beats the 2nd ninja, the 2nd ninja beats the 3rd ninja..., the (n - 1) th ninja beats the nth ninja ). 5. [4 pt] Gol D. Roger has divided the map of ONE PIECE into 2023 pieces and delivered to 2023 pirates. Each pirate has a Den Den Mushi, so they can call others to obtain information from each other. Show that there is a way that after 1042 calls, all pirates will know where is the ONE PIECE. 1. [4 pt] The Hidden Leaf Village is organising the Chunin exam. candidate ninja needs to fight with all other candidates one on one. Each (a) [1 pt] Suppose that three ninjas, Naruto, Sasuke, and Gaara are the only candidates. Show that when all the three fights are finished, we can always put these three ninjas in a queue, so that each ninja defeats the one who is standing right behind him/her (see Figure 2). (b) [3 pt] Now suppose that n ninjas are participating in the Chunin exam. i. [1 pt] Show that there will be n(n - 1) fights. (a) Naruto 411 (b) Gaara (c) Sasuke Figure 2: Three candidates of Chunin exam standing in the queue, given that Naruto beats Gaara, Gaara beats Sasuke, Sasuke beats Naruto. ii. [2 pt] Show that when all the fights are finished, we can always put these three ninjas in a queue, so that each ninja defeats the one who is standing right behind him/her (i.e., the 1st ninja beats the 2nd ninja, the 2nd ninja beats the 3rd ninja..., the (n - 1) th ninja beats the nth ninja ). 5. [4 pt] Gol D. Roger has divided the map of ONE PIECE into 2023 pieces and delivered to 2023 pirates. Each pirate has a Den Den Mushi, so they can call others to obtain information from each other. Show that there is a way that after 1042 calls, all pirates will know where is the ONE PIECE.