A puzzle about criminals in a room (Two perspectives).

in this video I will share with you a super nice puzzle but before getting into it I want to say whilst the result which follows from the problem is definitely important and interesting I want to highlight how different observations made in the early stages of the problem solving process will lead to different and yet equally beautiful proofs although on the surface it may seem like these two proofs were found artificially just to illustrate this point the premise of this video is actually based anecdotally on the two approaches me and a friend of mine use to solve this problem my friend being the person who suggested this problem to [Music] me the puzzle we are addressing is suppose there are an odd number of criminals in a room so that the distance between any pair of criminals is distinct in other words no two pairs of criminals have the same distance from each other every criminal watches the criminal closest to them prove that there's always at least one criminal who is unwatched by any other criminal before we get into solving I want to iterate that I encourage you to try this problem yourself and pause at the key breaks and chapters to complete the proofs independently to get a better feel for the problem it makes sense to look at small cases with a small number of criminals but before that we need a better way to represent this problem observe that we can represent the criminals with dots which I refer to as vertices or nodes and if a criminal is watched by another criminal then I will place an edge between these two in particular a directed Edge together these form a directed graph and if we have n criminals then we must have n vertices and N edges now looking back at the problem the first question you might have is how is oddness important if you think about it for a bit you may realize with an even number of criminals you can pair them up in such a way that each pair look at each other a sort of staring contest so no criminal is left unwatched with that out of the way we should start looking at some small odd cases when there is one criminal obviously this criminal is unwatched when we have three criminals you might notice something observe that the pair of criminals whose distance is minimal over all three pairs are both watching each other this leaves the third criminal unwatched this idea of considering the pair of criminals whose distance is minimal was the key to the proof that I used however as we go up to five criminals and then seven criminals and then nine criminals you might spot another pattern there doesn't appear to be any sort of closed Loops of directed edges known as Cycles longer than two criminals and this is something that we may conjecture more simply put the only cycle that seems to form is a sort of St a in contest between two criminals this was the conjecture that my friend used in his proof but before we go to see exactly how my friend proved this conjecture I want to return to my observation about the minimal length my crucial idea was to see what happens if we remove these specific two criminals from the room whose distance is minimal for convenience lab these two criminals as a and b and suppose that there were 2 n+ 1 criminals in total we know if there is some unwatched criminal say x then X is neither a nor B since A and B both watch each other hence by removing A and B we're left with 2 N minus one criminals which should hopefully still contain X this sort of recursive logic where the truth of the previous case implies truth of the next case should Scream one thing induction I will formalize this induction argument shortly but the conjecture that we'd made about the length of the longest cycle seems like something we should try and prove assume for a contradiction that there exists some cycle of length K greater than two criminals which we can label A1 A2 all the way up to a where A1 watches A2 A2 watches A3 and so on until it Cycles back to AK watches A1 now the key is that a criminal watches Another criminal if and only if there is no other criminal Closer by we can use this to form some inequalities A1 watch is A2 so AK is further from A1 than A2 hence A1 A2 is less than AK A1 but AK watches A1 so AK A1 is less than Aus one AK we can keep repeating this around the entire cycle going backwards to Ain the following inequality but look at the two ends of our inequality we're saying that A1 A2 is less than A1 A2 which is nonsense and is exactly the contradiction we were looking for after seeing this it starts to seem clear why oddness was important to the question we can suppose that there are M pairs of criminal who are in such a staring contest with a cycle of length two and then all the other criminals must be in some path on the graph however any criminal which is at the start of a path in the graph is unwatched since there exists no Edge going into that vertex and since the number of criminals was odd at least one such criminal must exist since we can't pair all of these criminals together which completes the proof that my friend used for completeness of this video let's go back and formalize our inductive proof we already established when there is one criminal trivially this criminal must be unwatched and this acts as our base case now assume for some K that with 2 K minus one criminals exists some unwatched criminal X then for the next case in our inductive step with 2K + 1 criminals we choose criminals A and B such that their distance is minimal over all possible pairs of criminals and remove these from the room this leaves us with 2K minus one criminals but we have to be careful and note that some of our criminals who were originally watching A or B and now watching some different Criminal by our assumption in this new room there must be some unwatched criminal X but when we go back and reintroduce A and B back into the room some of these criminals might convert to watching A or B but since the length of a was minimal then neither A or B would convert to watching X so this criminal X remains unwatched as required to complete the proof to conclude I think both methods despite coming from very different observations both provide their own Merit generally direct proofs help understand why a particular result is true and induction has a reputation for skimping over the real understanding of why the conclusion is what it is because the assumption jumps over any deeper understanding of the problem while to a certain extent this might also apply to this problem the induction does still do a good explanation as to why an unwatched Soldier must exist even if not as explicit as a direct proof the purpose of this video isn't to say that one approach was better than the other I'd argue they're just as elegant but to highlight the nuances which led to these different of thoughts and then these different proofs [Music]

Channel: PolyaMath

Views: 104,808

Keywords: Maths, Math, Olympiad, Geometry, Number Theory, Mathematics, BMO2, BMO1, UKMT, British Mathematical Olympiad, combinatorics, algebra, Cuboid, Cube, Polynomial, Graph, Graph Theory

Id: 3LYCjjYkdvo

Length: 10min 16sec (616 seconds)

Published: Wed Apr 17 2024