A puzzle about criminals in a room (Two perspectives).
Вставка
- Опубліковано 19 чер 2024
- PolyaMath Community Discord Server: Discord: / discord
In this video I explore an interesting puzzle involving graph theory disguised as criminals in a room.
This video was created using: Davinci Resolve (free version)
Background Music:
Music by Vincent Rubinetti
Download the music on Bandcamp:
vincerubinetti.bandcamp.com/a...
Stream the music on Spotify:
open.spotify.com/playlist/3zN...
Chapters:
0:00 Introduction
1:33 Observations
5:16 Proofs
9:06 Conclusion
A third approach (being pointed out by some comments) involves the observation that if some vertex has 2 or more incoming edges i.e a weight ≥ 2, then the pigeonhole principle implies some vertex has a weight = 0 i.e is unwatched
There are probably a variety of proofs to why a vertex of weight ≥ 2 exists but some care is required in the argument
Let A and B be the criminals on the minimal length edge (so they watch each other). If another criminal watches A or B we're done (since their weight ≥ 2)
However if you imagine A and B were both "really far away" from the other criminals then nobody else may watch A or B. Here we'd need some induction argument to show the remaining criminals excluding A and B contain a vertex of weight ≥ 2
(Also i think the only way every vertex can have a weight of 1 is if they're in a cycle, so the acyclic nature of the graph also implies this result)
Isn't there a more intuitive solution?
Each criminal will have a counterpart that it is closest to. We can call this the minimum distance.
For the set of minimum distances, there will always be a greatest minimum distance, a second greatest minimum distance, and so on.
We know that for the greatest minimum distance, if both were being watched by a closer criminal, that would change the pair with the greatest minimum distance, which is contradictory. One of the two criminals must also be closer to at least one other point, otherwise this would also not be the pair that makes greatest minimum distance.
Ergo at least 1 criminal is closest to one other criminal, which has other criminals watching it. In turn, this criminal is further from every other criminal.
Therefore at least 1 criminal cannot be being watched.
Following two proofs that if there is no vertex of weight >= 2 then the graph is an union of cycles.
From there to solve the problem you can just say that no cycle must be larger then 2 then it's not possible to have #C odd and have that there is no vertex of weight >=2, since it would have an odd-cycle.
(edit: let C be the set of criminals)
1. Unnecessarily formal proof
The case of 2 people it's obvious, the only way is having a 2-cycle
In the case of N people then we have two options
a - it is not connected, then there are connected parts which are smaller then N then the thesis is true by (strong) inductive hypotesis
b - it is connected, then the graph is a N-cycle, since for any pair of verteces you must be able to construct a path between them, but since every node watches only another node, starting from one node A ∈ C, all the other nodes must be constructed by w(A), w²(A), w³(A), where w : C -> C is the name of the function that tells which node watches which node (successor). Then necessarily N is the least integer such that w^(N) (A) = A, since otherwise A would never reach some of the nodes. But this means that the graph of C is an N-cycle.
2. Fun Cannon Group Theory
Consider the function w: C -> C. It is clearly bijective since it is a function and no node has two entering edges so it is injective, being between finite sets it is also surjective. So it is a permutation of C without fixed points (no criminal watches themselves). Now it being a permutation it is a product of disjoint cycles. This means there exist distinct sets of subsets of C such that w restrained on each of those is a cycle.
@@Slashem123 I think that mostly works, except you need induction for the case where the pair of greatest minimum distance is watching each other, and can thus be removed from the problem. Removing such pairs iteratively, you'd either end up with 1 criminal remaining, or with a pair of greatest minimum distance where the watcher isn't being watched.
Phrased a bit differently, the only way for the watcher to be watched in the pair of greatest minimum distance, is if the other criminal in that pair watches the watcher back, in which case the pair can be removed to simplify the problem until that's no longer possible.
You may have not seen it but I gave another proof.
Another proof.
Label each node with the distance of the closer neighbor.
1. Since all distances are distinct, we can have that u and v have the same label but no 3 nodes u, v, w can.
2. If 2 nodes have the same label, then they stare at each other. Mark the nodes of all such pairs as dead. Only living nodes can stare at living nodes.
3. Since the number of nodes is odd, there is at least one living node.
4. Since distance are symmetric, nobody watches the node with the highest label (by definiton of the labels, everybody has somebody which is closer).
If A and B are really far away, and noone is watching them, then A and B are not the closest criminal to any criminal other than A or B, so the remaining criminals form a set of (n-2) criminals that follows the same rules (since removing a criminal from the set will not change who any other criminal watches, unless that other criminal was watching the removed criminal).
At that point, you're in one of three cases:
the new shortest pair (C and D) only watch each other, with no other watchers - remove them, and repeat.
at least one of the new shortest pair is watched by a criminal not in that pair, so has 2 or more watchers
only one criminal remains, so is unwatched.
I paused and tried the problem. Becoming a criminal was no problem but when they caught me they kept me in separate rooms from the other criminals.
Tricky problem.
Another fast way: if someone is watched twice, there will be someone who isn't watched at al. It's not hard to see that at least one pair of people looking to each other, have to be watched by someone else, completing the proof
Having a pair of criminals watching each other isn't the same as having one criminal watched twice tho (not saying this is wrong, just it's not so simple)
@@TheArizus, I see your point but don't agree. I guess "it's not hard to see" needs some expanding. It's certainly true that for n criminals there are n watchers, and n watchees. Any criminal being watched more than once must therefore leave an unwatched criminal elsewhere. While any given mutual pair might not be being watched by a third criminal, with n being odd, there must be a pair somewhere being watched by someone else. I think the proof that there can be no closed cycles greater than two nodes is important here. Every criminal must be either in a mutual pair (cycle of two) or in a chain of one or more that ends up looking at a mutual pair. This proves at least one mutual pair has an observer, which proves at least one node is unwatched. I'm slightly unconvinced by the inductive reasoning without the proof that there can be no closed cycles greater than two, but maybe I'm just not clever enough to quite "get it" lol.
@@tonywoodhouse I think it is fairly intuitive.
Any pair watching each other and not watched by anyone else don't affect the answer and can be ignored, so already you only need to look at groups where all nodes are "connected". It's then fairly obvious that the two closest nodes in that group will be watching one another, and since we know that all the nodes are connected we know that at least one of them is also being watched by at least one other criminal. That alone shows that someone is being watched twice, and that proves that someone isn't being watched since each person can only watch one other person.
I'll try and formalise this:
Consider an odd number 2n+1 of criminals, where n is an integer
Identify the pair with the smallest distance between them. They must necessarily be looking at each other.
Since each criminal watches one and only one other criminal, the number of "looks" to go around is exactly 2n+1. Therefore, if there exists a prisoner who is watched by 2 or more others, then there will be ≤2n possible "looks" to be assigned to 2n+1 criminals, for which one must necessarily be unwatched, proving the theorem.
After considering the pair that look at each other, for them to be connected to the rest of the graph would require one them to be watched at least twice (by their partner and the connection), proving the theorem. We must therefore only consider the case where they are disconnected.
If they are disconnected then, from the perspective of the set of remaining prisoners, it is as though they are not present. The case then reduces to the remaining (2n+1)-2 = 2(n-1)+1 criminals.
We have thus demonstrated that if the theorem holds for 2(n-1), then it must necessarily hold for 2n. The theorem trivially holds for n=0 with a single prisoner, therefore it is true by induction. QED
yup i proved it like this too by prove i mean thought of it in my head, you need kind of a induction argument to complete this tho
you've been hit by, you've been watched by C^\infty criminal
OW!
duna duna nuh nuh
duna nuh nuh
duna nuh nuh...
Nuh.
If the distance between any two criminals is always different, then the distances from every criminal to their nearest must also be different. Therefore there must be one criminal whose shortest distance to another criminal, is longer than the shortest distance for any other criminal. Let's call this criminal wallflower. Because wallflower's shortest distance is the longest shortest distance, everyone else's closest distance is smaller, so wallflower goes unwatched.
Two criminals that look at each other have the same distance to their nearest criminal though??
@@nataliakurinnyy6831 but with an odd number the ones looking at each other will never be the ones that share the longest shortest distance. Because at least one of the ones with the longest shortest distance will have a shorter shortest distance to a different one.
@@blakdeth sure, I understand the conclusion, but I was just concerned with how your proof opens with the claim "the distances from every criminal to their nearest must also be different". Just have to bullet proof everything :)
@@blakdeth I arrived at the same proof, but that last bit you claimed is false. Imagine you have 3 criminals close by, and very far away you have a pair watching each other. That pair could have the highest “shortest distance”, in which case the next highest is unwatched.
My version of the proof goes like this:
For each node we define the shortest distance, “D”. This value can only be shared by up to two nodes (3 nodes can’t share a distance). Now, every unpaired node is looking at a node with a lower value of D, otherwise they would be paired. It follows that the unpaired node with the highest value of D is unwatched, QED.
@@Brainth1780 oh wow you're right. Didn't even consider that
Polyamath is criminally underrated. Top tier editing, and his videos are engaging. I wish this guy all the best for the future.
RIGHT??
i love finding those small amazing channels but cant help but feel bad for how under rated they are
this is pure quality
You might even say that he's criminally unwatched
@@sundown456brick I was alerted to Polyamath's content by an IRL associate, and have been watching for a while. The subs are growing quickly and I believe his content won't be underrated for long lol. Keep up the good work PaM😊
hes a genius irl, hes going to have a very bright future.
As a new viewer, I enjoyed the video, but I found the speech audio to be very quiet and poor quality, which tends to be really distracting for me. Somebody get this man a professional mic, stat!
The way I solved it:
Think of the shortest line between two criminals. This will always be a staring contest. Then, think of the second shortest line. If neither are involved in a staring contest, it becomes a staring contest. Otherwise, a criminal watches a staring contest, meaning one criminal is watched twice, and since the amount of watchers is equal to the amount that need to be watched, not everyone can be watched. Since there's an odd number of criminals, you can't pair everyone up, and since all distances are distinct, all distances can be sorted in ascending order without ties.
This is exactly what came to my mind, you kind of exhaust the list 2n + 1 which leads to the conclusion that you can never pair the last criminal
Great proof!
This was my reasoning too. The shortest line in the network necessitates that both criminals watch one another. Since there is no matching shortest line in the network, they cannot watch anyone BUT each other. Assume all other pairs match similarly; because the number of criminals is odd there must be one left over. If not, a criminal watching a matched pair is either unwatched or watched by an unwatched criminal, or watched by a criminal watched by an unwatched criminal, etc
My idea:
One of the distances must be the "shortest" distance. If there's one shortest distance, then the criminals sharing that shortest distance must be watching each other, since there's no way a criminal can be closer to them since they're the shortest distance from each other. Either no one's watching those criminals, in which case they don't affect the results, and repeat until we've eliminated all unwatched pairs, or someone is, in which case, their watching is just wasted. This means that the group of lines of sight that are actually watching someone is LESS than the total number of people, so someone must not be watched.
Proof: Let n be the smallest odd number allowing for all to be watched.
There is a finite number of distances, so there is a smallest one, those two will watch each other. Now if anyone else watches either of them, someone remains unwatched, so no one watches either, thus we could remove those 2, and would now have a working case with n-2 criminals, which by assumption couldn't work
(And n=1 trivially does not work)
I once dealt with this problem as a student at the New York Math Circle. Your solution was mine. :)
😮
An amazing problem with amazing animations to follow it! How is this channel not more popular?
My approach is based upon the generation of edges.
Order the list of distances of criminals from lowest to highest. This can be done because they are all unique.
Now, go through the distances and notice that two situations can happen:
1. Both criminals aren't watching anyone yet. Then they both watch eachother, and we gain 2 new watchers.
2. One criminal already watches anyone, but the other doesn't. Then we gain one new watcher, and this watcher is unwatched because the distance between any other criminal is greater. This may make an unwatched criminal become watched, but will always create an unwatched criminal.
3. Both criminals are watchers. Then nothing happens.
Note that we cannot solely have steps 1 and 3, because then, we'd have an even number of criminals. So there must be a step 2 which creates an unwatched criminal.
2: the watcher is only unwatched so far, but might become watched later
Consider the case of 4 vertices, where the guy in step 2 is the 3rd vertex (after the first two watch each other)
The 4th vertex could be very far away from the first 3 (such that none of them would watch it), but you can easily set things up so that the 3rd vertex is the closest to 4, so that 4 watches 3
Of course, in this example, this means that 4 will be unwatched. But the main point is step 2 doesn’t hold up and need some further details 🙂
@@Muhahahahaz
That's true and maybe I need to nuance it a bit more.
The first time step 2 happens, we gain an unwatched criminal. Every next instance, we either gain net 0 or net 1 unwatched.
Since step 2 must always happen, we always gain at least 1.
Super short proof: while there are two or more people, remove the two people closest to each other (these are uniquely determined). You will be left with one person. By construction, every other person had (at least) someone to look at who was closer to them than the leftover person. So nobody looked at that leftover person in the first place.
EDIT: note that when removing people like this, some criminals may not be looking at anyone at all. This is inconsequential and the key simplification over the proof by induction presented in the video.
Genuinely amazing! It's been ages since I could watch this kinda math content, and i forgot how much i loved the proof by induction method (@ 5:15 in the vid atm)
I dumbed it down to:
As there's an exact number of "watchers" and "watched", any time someone is being watched more than once, there is someone not being watched at all.
There will always be one shortest line, where the 2 criminals will be watching eachother, and that would either have to be far enough away from the remaining criminals to be unwatched by any other person, OR have a third (or more) person spectating, thus forcing there to be one person watched twice, therefore one person unwatched.
If they are disconnected from the rest of the group, then the remaining group will also have one smallest line where 2 are watching eachother, and you come across the same conundrum where this group would also be seperate or watched by a third party.
No matter how high N is, you can either keep breaking off pairs until you get down to only 3 people, where the last person has to be unwatched, OR you will have already found someone being watched by 2+ people, which will inevitably mean someone somewhere down the line is unwatched.
Just found this channel and it's great! Commenting to boost engagement :)
It’s nice, my initial thoughts flitted between the three initial observations: first pigeonhole, then shortest edge, then cycles, but the cycles argument was the one I found easiest to formalise
Nice! It also follows from the argument that if there is more than one criminal (and the number of criminals is odd), then some criminal is watched by at least two others! =D
Just thought of a subtly different way of looking at the problem. In any population of n criminals, if there are no unwatched criminals, then every criminal must be watching one other and watched by one other. Noone can be watched twice because if they are, there must be an unwatched elsewhere to ensure that there are n watchers and n watchees. If everyone has only one watcher, then everyone has to be in a cycle. We know from the proof in the video that no cycle can be greater than two nodes. So if everyone is in a cycle, and all cycles have to be two nodes then n must be even. N being even and all criminals paired in cycles of two is the only possible state that leaves no unwatched criminals. By contradiction, if n is odd, every criminal can't be in a cycle of two, and therefore at least one must be unwatched. I think that works?
Yeah this is just the direct proof tho
Not necessarily a single cycle, but yes. The graph would have to be one or more (non-trivial, disjoint) cycles
Pretty nice I would have never thought about the induction proof, my first direction was excluding pairs (odd) and using the inequality of distances for the polygon cycle (cause all distances the same is the only way to create a cycle longer than 2) so pretty much equivalent to the second option
As in quite a few other cases, the induction here is interesting because it's constructive.
Here's my solution:
1. Since each person can only watch 1 person, if any one person is watched by two people there will be someone who isn't watched.
2. Select the pair of prisoners with the shortest distance between them. Since no prisoners are closer, they will watch each other.
3. Repeat the process, now selecting the second closest prisoners. If one of them is also from the original pair, then you have one person watched by two, and so we know someone will ve unwatched by step 1. If the new pair is unique, repeat the process again, taking the next shortest distance.
4. Eventually, if all pairs are unique, you will have only one prisoner left. Since all other prisoners are watching their pair, no one will watch this final prisoner, once more proving the postulate.
This guy is 16 years old? kudos!!!
This video makes this problem more difficult than it needs to be. The proof by induction can be reworked to avoid thinking about math entirely. If the number of watchers vs. watchees within any loop is uneven, then by definition there must be an unwatched prisoner. This means all prisoners can only be watched if all prisoners are part of closed loops where the number of prisoners being watched matches the number of prisoners doing the watching. At the same time, because all distances between prisoners must be distinct, there must always be a smallest distance that forces two prisoners to watch one another. That means you must have at least one closed loop of two prisoners.
Matching the proof by induction, we can then note any closed loop of two prisoners not watched by a third prisoner has no effect on the system and can be discarded. But if you discard the smallest distance between prisoners, then you necessarily create another smallest distance which in turn will create another closed loop of two prisoners. Because this only removes prisoners in pairs, it cannot change whether the total number is odd or even.
The only way to get a closed loop (the only situation in which all criminals are watched, given an odd number of criminals) without a paradox is in a polygon where all edge lengths are the same, where each node looks at the next node over (technically they could pick which way to look at this point, but details). The issue is that this contradicts the original premise that no two pair distances are the same, so that can't be true in this specific problem. With that one possible scenario removed, the only remaining scenarios all involve a single closest pair of A and B. Each node can only watch exactly one other node. We know that A and B will be watched by each other. If either A or B is watched by any other node, then by the pigeonhole principle that means that at least one node won't have any nodes watching it. If neither of the two are being watched, I.E. both of the nodes are far away from each other, then we simply move over to nodes C and D and do the same thing.
Sidenote, this only holds if the original premise of all distances being different is true. If you let go of that premise, then any regular polygon could potentially result in all nodes being watched.
Strictly speaking the polygon wouldn't even have to be entirely regular. For n≥7, making it concave by "reflecting" the position of one vertex about the line between its neighbours preserves the nearest-neighbour relationships. Other irregular angle selections could also work!The regular polygons are definitely the easiest case to show, though.
I did it in a way where I don't have to have to deal with staring contests :
Let's assume there is a n that satisfy the problem, (i.e there are 2n+1 criminals, all being watched)
There are obviously no solution for n=1
Therefore, there exists n0>=2, the smallest n which satisfies the problem.
Now, if the criminals are split into separate groups, then in every group every criminal must be watched by a member of his group.
Therefore, since an odd number can't be split into even numbers, there must be a group of size 2m+1
my reasonning:
i have an algo to find the one
loop:
take the longest edge
if its a pair, you can remove it without altering the rest
else, break
loop end:
the origin of the longest edge is not seen by anyone
i didn’t formalize my proof, but my version felt like a hybrid. the main idea was that in any cluster you have to point towards a 2-loop, since at each step the distance must become smaller
Before I finish the video, I'll share my solution: for each node, draw a circle that just reaches the closest node. Let's consider the biggest circle. If there is another circle of the same radius, this means that they're watching each other. Let's remove them from our consideration and consider the next biggest circle (there is gonna be at least one since the number is odd). We found the biggest circle for which there is no circle of equal radius. Now, since each node's circle includes just one other node, on the edge (none inside), this means that for the node with the biggest circle there is no such other circle that it includes the current node, which means that there is no other node for which the current one is the closest, which means we've found a criminal who isn't watched by anyone.
For K nodes (pigeonholes), there are K edges (pigeons). Since no cycle can be more than two nodes, if there are an odd number of nodes, there must exist at least one node with two edges pointing at it. Therefore, by the pigeonhole principle, there must be a node without an edge pointing to it.
Here is the most succinct argument I could come up with: suppose by contradiction that every criminal is watched by exactly one other criminal. Then in-degree and out-degree of every node is one. Consider the underlying undirected graph where every node has degree 2. It cannot be bipartite, because the two partitions can't be equal size (since total vertices is odd), so the total edges on left side wouldn't equal total edges on right side. All non-bipartite graphs contain a cycle of odd length, which must be length >= 3 since there are no self-loops. The cycle creates a Euclidean shape with >= 3 sides, which (because all pairs of distances are unique) must have a shortest side. But the two endpoints of that side must be watching each other, so neither of them can be watching any other node, so they can't be in the odd cycle. Contradiction.
So there must be either an unwatched node or a node with >= 2 watchers. If the latter then total in-degree = total out-degree plus the pigeonhole principle gives us an unwatched node.
The longest weight edge must be connected to a node without incoming edges, as outgoing edges cannot be greater than incoming ones.
The shorter distance always ends up in a pair of criminals who watch each other. Since every criminal watches only one other, it's lost if one criminal is watched by multiple ones. So this (and every other pair) can just be put far away from all other criminals, as there cant be any interaction anyways.
This way the problem can be simplified to a group of 3. These remaining 3 need to build a circle to fulfill the task. The problem is that this subgroup also has a shortest distance, which results in a pair. So there is 1 criminal remaining, who watches the pair and is not being watched.
In a random configuration this could also be a chain of criminals. But this chain always has the starting criminal, who is wazching at a different group, and the ending criminal, who isnt being watched.
While I'm writing this I actually noticed a simpler explanation.
There must be 1 or more chains to fulfill the task. But chains are generally impossible as the distance between each 2 of them, must be monotonously increasing/decreasing. So wenend up with chains, where the last (n-th) prisoner watches the (n-1)-th instead of the 1st..
For a even number of prisoners the task is possible by creating only pairs.
Now I feel like I'm being watched by a criminal.
Intuitively, this would always have to be true due to the constraints of unique distances between criminal pairs and the criminals looking at their closest neighbor.
These together ensure that two, and only two, criminals are always looking at each other along the shortest line of sight. This means you necessarily have one less unique line of sight than the number of criminals. Hence, you will always have one unwatched criminal.
Pausing at 1:30
I think I have a solution. You start with the two points ("criminals") closest to each other. They "watch" each other, so we can check them off. Now we look at the remaining points. Again, we take the two closest to each other. They either "watch" each other, or one of the already watched points. So we can check them off as well. We repeat that process, eliminating points in pairs, until a single unwatched point remains. QED
I think I might have an inkling of a slightly different proof, too, looking at the various lengths between all pairs. I think we might be able to use the fact that they are all different length to create a kind of hierarchy between points, but that's probably a false approach. Either way, the thing above should suffice.
You’ve been watched by,
you’ve been seen by,
a smooooth criminal.
My thoughts before seeing your solutions:
The two criminals with the smallest gap between them will watch each other, by definition.
Anyone watching them will create a chain of watchers of increasing distance, guaranteeing such a chain has an unwatched person at the end of it. (A full loop would only be possible if all edges were equidistant.)
There might be multiple starting pairs of cowatchers from local minima, but there being an odd number of criminals guarantees at least one watcher chain.
Another proof: if everyone is watched then the graph must be a collection of cycles. Since cycles must be of length 2, n is even, contradiction.
Another proof that cycles must be of length 2: if we have cycles of length m > 2, the pair of vertices with minimum distance must watch each other, contradiction because theres not enough edges remaining to go around.
I followed the same logic that your friend did, thinking about cycles.
I friggin love graph theory
This was in my Discrete Math textbook as "2 people throw eggs at each other, prove there is at least one person who is not hit by an egg." Fascinating to see it here, and rewritten/better explained.
Thanks, I've also seen the problem as soldiers in a field haha.
@@PolyamathematicsThat may explain why you say “soldier” at 9:43!
I actually thought of the cycle proof rather than the induction proof, but I can't hate a proof by induction. I went to grad school in programming-language theory and induction is everything there!
Hi, great video, really interesting. I just have one issue: the text looks too small to be read for me
My thought was that the vertex that is furthest away from all the others will never be watched, since it's closest partner will be closer to someone else. We don't need to prove how many criminals aren't watched, just that at least one criminal isn't watched.
Since there are the same number of links as there are criminals, it's pretty clear that the only way they could all be watched is if they were arranged into one or more cycles, e.g. A watching B watching C watching A. Also, since there are an odd number of criminals in total, there must be at least one cycle with an odd number of criminals, and thus, at least 3.
Now, consider such a cycles of at least 3 criminals. If we look at the distances between each pair of criminals along the cycle, we will find that one distance is the shortest. Since distance is commutative, the two criminals with the shortest distance must be looking at each other, but this is a contradiction! We claimed that they were looking at each other in a cycle!
Now, to prove that only graphs consisting of only simple cycles can work, we can use a simple method of construction. Notice that since there are N criminals and N links, then each criminal must be watched exactly once, or else some criminal will end up not being watched due to running out of links.
We start by picking an arbitrary criminal, and draw a line to another criminal, who then draws a link to any other unwatched criminal, and so on. If a cycle is formed, we pick one of the remaining criminals and start again. Then, at each step, we have the choice of closing the current cycle and starting a new one, or of adding another criminal to the current cycle, and at the final step, the only option remaining is to close the final cycle, or else with a single isolated criminal.
At the end of the process, we're left with a collection of cycles, with or without a single isolated criminal. We can discard the cases with the isolated criminal; we're only interested in solutions, and in a construction that covers all possibile ways of linking the criminals.
My informal solution:
Consider any criminal in the room. Who are they looking at? By definition of the problem, there exists only one other criminal in the room who is the shortest distance away, so there is only one choice.
Consider the new criminal. Who are they looking at? There are two choices this time.
If the criminal from earlier is mutually the closest to our second criminal, the second criminal looks back, creating a closed loop of n = 2.
The other option is that a new third criminal is closer to our second criminal than the first one, so our second criminal faces them.
In the second case, select the new criminal. As with the previous one, there are two possible options: look back at the criminal watching them, or watch a new criminal.
Note that the first criminal is not an option--if the third criminal watches the first, it implies the first and third criminals are closer together than the first and second. If that were true, the first criminal would watch the third, not the second. This is a contradiction. Since every new link in this chain we are forming has a distance strictly shorter than the previous, this contradiction holds for every criminal in the chain except the one immediately preceding our current criminal.
With these observations, the following fact becomes clear: the only way our growing chain can possibly terminate is if it falls into a n = 2 cycle eventually. Since our number of criminals is finite, all chains must terminate. Therefore, _every_ criminal chain _must_ take the form of a one-way spur of length 0 or more terminating at a n = 2 loop.
The only way for the room to have no spurs of length 1 or greater is for every chain to be the base case of a n = 2 loop. If this is so, there _must_ be an even number of criminals in the room, as every chain has an even number of criminals. This is also a contradiction. This means at least one chain _must_ have at least one spur of length 1 or greater. And every spur, by definition, has a criminal at the end of the spur who is not being watched.
Edit: I did not explicitly check whether it is possible for spurs to coincide and be double-counted. But it doesn't really matter. Once at least one chain with a spur exists, any new criminal added to the problem has the following choices: fall into a new n = 2 loop immediately, become the tip of a spur to a new n = 2 loop, become the tip of a spur to an existing n = 2 loop, become a new spur tip forking off from an existing spur, or become the new tip of an existing spur. There is no case where the number of spur tips in the room decreases, it only grows or stays constant. So branching topologies, whether or not they are even possible, are irrelevant.
There seems to be a problem with the inductive base case. A lonely criminal can't look at the nearest criminal. There is none.
I solved this one pretty quickly. If any prisoner is watched twice, there will be an unwatched prisoner. You can think of this as having ‘chains’ of prisoners. No matter what, the last 2 prisoners in a chain will always be watching each other. If you have a chain larger than 2, this will always cause a prisoner to be watched twice. A chain of one doesn’t work, as it causes a prisoner to not be watched. Because odd numbers are not divisible by 2, it won’t be possible to split the prisoners into chains of 2.
Man this is the quality of 3Blue1Brown how only 5k subs???
Very interesting video. I paused at the start and took a crack at the puzzle, and the thing that felt most natural to me was a proof by contradiction that is very similar to your proof by induction, with a hint of the pigeon whole principle from the pinned comment.
This is verbatim what I wrote in a notepad trying to figure it out (it could be refined, but I thought it would be more interesting to show my entire thought process from start to finish):
Each criminal watches exactly one other criminal
There are 2n+1 criminals
Therefore, there are 2n+1 criminals being watched
Suppose all criminals are being watched
It follows that no criminal is watched by 2 criminals
There is a unique distance d1 that is the shortest distance between any 2 criminals
These 2 criminals watch each other
Therefore, none of the other criminals watch one of these 2 criminals with the shortest distance between them
Among the remaining criminals, there is a unique distance d2 that is the shortest between them, and this distance is less than the distance between those criminals and our original pair of 2 criminals, otherwise one or both of our original criminals would be watched twice.
This second pair of criminals also watches each other.
This logic follows until n pairs of criminals all must be watching each other.
The remaining criminal is not being watched by any of the other 2n criminals, as they are all watching each other in pairs.
This is a contradiction.
I tried a different approach.
Let X1,X2....Xn be the prisioners
And for each prisioner i let Wi1,Wi2.....Wi(n-1) be the distances between him and the other prisioners.
Lets order the prisioners by min(Wi) and look at the prisioners at the end with the highest minimal distance.
If there are any 2 prisioners with the a
same number on that end we can eliminate them since they look at each other and look for the first one who does not have a pair. There has to be one since the number of prisoners is odd.
We know for certain that no one looks at him!
Because if someone looked at him he must have a lower distance to him than the minimum distance he has from the other prisioners.
This is because we 'eliminated' all the higher minimal distance prisioners if there were any.
And we know for certain that he doesnt have any other prisioner that has the same minimal distance as his because he is not in a 'pair'.
This is a contradiction to his minimal distance being maximal.
Before watching the video here is how i would handle it: prove by induction. For n=3, there is a pair with the shortest distance, they watch each other and the third is not watched.
For higher n: there is again a pair with shortest distance that must watch each other. If one of them is watched by another, we can use pidgin hole principle to see that there must be one left unwatched. If the pair is not watched by another, then we can disregard the pair and refer to the n-2 case by induction.
I can def see a new leetcode problem here
This problem looks like it generalizes to some sort of upper bound for information loss in KNN clustering, neat 😂.
Suppose every criminal were watched by at most one other criminal. The pair with the shortest distance must be watching each other, and by this assumption, neither of them are being watched by anyone else. So we can remove them without affecting the rest of the setup. Now repeat, until there is one criminal left with no one to watch. Contradiction! Thus, some criminal is watched by more than one criminal, which necessitates some other criminal being unwatched. q.e.d.
Id have said that there's always going to be, in n≥2, a two cycle that is guaranteed to be mutually watched (every chain ends in a two cycle). by recursively removing pairs of criminals who are watching each other (because they can no longer impact the rest of the world), we end up at a point with 1 solo unwatched criminal
alternatively, just the arguments "the only cycle is a two cycle, all the rest of the points can draw only directed graphs to a terminus" should do it. "a mutually watched pair means there is one less set of free eyes and therefore not everyone can be watched, and also there's always going to be at least one pair" also
I've come up with a very short and simple proof and since i dont see a similar one in the comments here we go:
1) Take a weighted directed graph representing the problem
2) remove all pairs of prisoners watching each other
3) there must be an edge with a max length
4) if all prisoners are watched, the source of the max length edge must be viewed by a shorter edge (thanks to step 2)
5) he should have watched this shorter edge (closer prisoner) so we reached a contradiction and proved that it's impossible for all prisoners to be watched.
My solution for this is, for n criminals: n=1 is trivial; n>1: the two criminals separated by the shortest distance will stare at each other; the remaining n-2 criminals form a set that are staring at n-2 criminals, if any stares at one of the first two that leaves 1 less 'stare' than there are criminals in the n-2 set so one must be unseen; if none of the n-2 set stare at the original pair then this becomes an independent set - and use 'reductio ad absurdum' to complete proof.
My proof: consider the longest edge in the graph, A -> B. Let's say C -> A is also an edge. Since AB is the longest edge, AB > AC. Since A is watching B and not C, AB < AC. Contradiction, which means no one can be watching A.
If there is such a room, each criminal must be looked at by exactly one other criminal. There cannot be a triangle or any other shape made of distinctly sized lines where there is no shortest length of line. Any shortest length of line produces two criminals that look at each other. To prevent any other criminal looking at these criminals looking at one another, we can remove any two criminals that are looking at one another from the room. There will still be a shortest length of line as long as there is more than one criminal. Repeat process until there is no such distance. There will be either 0 or 1 criminal left in the room.
There is one guy furthest away, and he's looking at someone who is looking at somebody else who's closer. Qed
Hello, can I ask how you make your videos? I have no idea with what software could you make these videos.
Everything is made with Davinci Resolve - free version (using the Fusion page)
Since the distances are distinct, you can at most have cycles of size 2, in other words two criminals watching each other. For example, it's impossible to have a cycle of size 3 where criminal A watches, B who watches C, who watches A. When all distances are distinct, there is always one smallest distance. This means there is at least one pair of criminals who watch each other. If there are 2n+1, then you know that at least 2 of those form a cycle size 2. Every criminal can only watch only one other criminal, so at most 2n-1 criminals can be watched by the remaining 2n-1 criminals. 1) If one of those criminals watches the pair of criminals that watch each other, then you are left with 2n-2 that can be watched, while there are stil 2n-1 criminals for which you have not determined yet if they are being watched or not. This means that at least 1 criminal is not being watched. 2) However, it's possible that no criminal watches the pair of criminals that watch each other. If that's the case, then you can remove the pair from the problem instance since it makes no difference having them present or not. This means you have 2n-1 criminals remaining. 3) If n=2, then we know it's impossible that they are all being watched, because the only would be a cycle of size 3, which is impossible. 4) Suppose we know it's impossible for n-1>=2 that everyone is being watched, then we know it's impossible for n as well. We either have case 1, which means we can say right away that at least one of them will be watched. Or we have case 2, which means we can reduce 2n+1 criminals to 2n-1=2(n-1)+1. And we know that for n-1 it's impossible. 5) From 3) and 4) we can proof through induction that there is always at least one criminal not being watched.
Another proof (the one I came up with):
First, find the longest edge, let's call it AB, as in A looking at B.
Now let's see what B is looking at, there are two options "A" and "not A".
If B is NOT looking at A the we know nobody is looking at A, because if there was someone looking at A then either there is an edge longer than AB (which is impossible as AB is, by definition the longest edge) or that vertex would be closer to A than A is to B, in which case AB would not exist.
If B IS looking at A then we know no other vertex is looking at either of them, using the same logic as above (but applying it to both A and B). In that case we can remove both A and B without effecting the other Vertices.
Repeat with A and B removed until either: option 1 occurs, or you are reduced to 1 vertex (technically the loop always terminates at 3 if it gets there, as the third vertex must be looking at someone, which requires it to be close enough to force B to also look at them)
Kinda surprise so many proofs in the comments rely on considering the min of the distances. Which often lead to an induction proof. While considering the max of distances gets you to a direct proof.
Yeah. Criminal with the longest watching distance among those not involved in a pair ("staring contest") cannot be watched by anybody else.
For every node, assign it a number corresponding to the distance to its closest neighbor.
Now, look at the criminals with the largest such number. If there's only one such criminal then he couldn't be watched by anyone and is the unwatched criminal.
If there's more than one, then since the distance to any two criminals is unique that biggest number must've been achieved using the distance between two particular criminals, meaning we have exactly two criminals with a biggest number.
Since they have the biggest numbers, no criminals are watching them, and they're simply watching each other, so what we have is a completely isolated staring contest. Remove those two criminals from the graph and repeat the proof for N reduced by 2. Eventually you hit the base case of 1 criminal and that's an unwatched criminal.
Before watching the rest of the video (just watched the premise) i think i have a valid proof. You can consider all the lengths, and since all 9f them are unique, one of them will be the minimum. And so the 2 prisoners on that length will be looking at each other. Now there are 2 cases after that, either no one else is looking at them, ir someone is looking at them. If someone else is looking at them, then the prisoner being watched will have 2 ppl watching him, hence theres a prisoner thats not being watched (im not gonna proof why this works, its pretty intuitive anyways). Now in the case that no one else is eathcing the 2, we look at the next minimum length, and we know 2 things about it. 1st it is not gonna be connected to the first pair, as if it were, there would be someone watching the first pair. 2nd since it is the shortest, the 2 ppl connected to it will be watching each other. And so we keep repeating. If someone is watching them then theres someone not being watched, if no one is wathcing them theres another shortest length not including the first two, which makes a pair. We keep repeating this until either of 2 things happen. 1 - someone is watching one of the pairs, in which case, someone is not being watched. 2 - we run out of prisoners (there are odd number of prisoners) and if we run out of pairs theres one prisoner left. And by necessity, that last prisoner must be looking at one of the pairs. And since that person will have 2 ppl looking at him, there will be a prisoner which is not being watched by anyone.
Everyone would have to be a part of a cycle, but all cycles are two-cycles, otherwise the lengths would always get smaller as you go through the cycle, which is impossible. That's why it doesn't work for odd numbers.
I think it's just intuitive, there will be a pair of criminals with the longest distance between each other, and one of them would have to be pointing at a criminal with the second longest distance instead of the first one.
A criminal can both be in the pair with the maximal distance and minimal distance simultaneously. It's not so simple.
Interesting… My proof uses the same minimal edge idea, but I ended up with a somewhat more constructive induction, rather than a recursive one
Basically, I can take any graph and show that it must have an unwatched vertex from scratch, without relying on assumptions for graphs of smaller sizes
In particular, after A and B are paired, we can consider the next minimal edge. If this edge connects some vertex C to either A or B, then we are already done (the final graph has |E| = |V|, so if any vertex is double watched, there must be an unwatched vertex by the pigeon hole principle)
Thus we can assume the second smallest edge connects two new vertices, say C and D, which also watch each other
The only other complication is that sometimes, the next minimal edge might connect 2 vertices we have already considered (for example, A and C). Essentially speaking, we can just remove the complete subgraph on A, B, C, D from further consideration, since all 4 of these vertices are already watching someone
Anyway, point being that either you reach a minimal edge that connects an “outsider” to an “insider” (a new vertex to one that has already been considered), which results in someone being double watched; or, everyone gets paired up in 2-cycles until only one vertex remains, which becomes our unwatched man
(It looks like there’s at least a couple other comments that went for this same idea, though not as thoroughly explained. Mine still isn’t particularly formal as a proof, but hopefully it’s a clear enough sketch - one interesting thing to note is there’s sort of two different graphs potentially involved if one wanted to write the above up formally: an undirected, weighted graph representing the distances, which edges get removed from; and a directed watcher graph, which edges get added to)
Propf per contradiction in the opposite:
If every criminal is watched by sb and there are not only 2 people loops, since there is an odd number, every criminal has a shirtest Distance to the criminal closest to him, which he is therefore watching. Because We suppose that every criminal is watched, there needs to be one criminal whose shortest distance is larger than the first criminals distance. But then the 2nd needs to be watched by one of an even longer shortest distance. thus needing A) an infinite number of criminals and B) a shortest distance that goes towards infinity
Both A and B are a contradiction to the theorem, that everyone is watched. So we have proven that at least one is unwatched
I have a question for clarification on the problem. If there are 3 points, that are all equally distant from one another, lets say in a triangle pattern. Is none of them watched? Because all points do not have a closest point to them?
"such that no 2 pairs of criminals have the same distance between each other"
I paused at the beginning and came up with a proof.
Sort all criminals by the shortest distance to another criminal.
Case 1: The last criminal has a distinct shortest distance from the next to last. This means every other criminal has a shortest distance less than the last criminal and so none of them can be watching the last criminal.
Case 1: The last two in the list have the same shortest distance. Since distances are distinct, they must be watching each other. And because they have the greatest shortest distance, no other criminal is watching either of them. This they can be removed from the list. Since the number of criminals is odd this can be repeated until we hit case 1 or there is only 1 criminal left
QED
Since the dimension of the problem does not matter there may be some insight by going through the conjectures and proofs in a one dimensional world.
My thoughts on the proof would've been to think of it with the pigeonhole theorem. Using the fact that there are n criminals and n edges, so if one criminal is viewed by more than one other criminal, then there must be a criminal who is not being looked at.
Then, because there in any chain of criminals there must be an end that cycles back on itself (theorem that is reasonably easily provable), if a chain of length at least 3 exists, the second to last person in the chain is viewed by the last person and the person 2 before the end.
(Prove trivial 1 case first then:)
Finally because the number of people is odd, and there are at least two people, a chain of one cannot exist, and they cannot all be directly paired (very trivial proof), there must exist a chain greater than or equal to 3.
Therefore by 2 and 3, there is a criminal being looked at by 2 criminals.
By 1 this implies that at least one criminal is not being looked at!
Nice
Note that the induction proof does NOT work by taking a set with an unwatched criminal and constructing a new bigger set also with an unwatched criminal. I think the video didn’t make this super clear. What’s happening is that outside of the trivial case we can always take a set and construct a smaller set in a certain special way and if that smaller set contains an unwatched criminal so also must the set we started with.
Correct, but I thought the video makes that fairly clear.
1000pi subscribers?
Haha, I noticed it too!
If every criminal is watched, every criminal is part of a cycle. At least one has length greater than 2, a contradiction. (this was before watching)
A proof I figured in about 10 secs. Let's prove somebody would be watched by at least two others - that would automatically imply that somebody else is unwatched, since everybody can only watch one. Take your A and B, the two with smallest distance. They watch each other. If somebody else watches one of them, we're done. If not, remove them, and nothing changes; everybody still watches the same others as before. Rinse and repeat.
Let's look at the longest watching edge and call its length d. This is either unique or a 2-cycle by the different distances condition. If it's unique, the criminal doing the watching is being unwatched, as there are no other criminals within distance d of them and there are no watching edges longer than d. If it's a 2-cycle, no one else is watching that pair of criminals by the same argument, and so we can just ignore them and reduce the problem to one 2 criminals smaller, solving the problem by induction.
That was exactly my solution too 🙂
@@piotr.ziolo.I love this reasoning, but believe it can go simpler still. Everyone else, myself included tended to start at the shortest connection, but starting at the longest is genius. Argument: consider the longest edge between two nodes. One of those criminals must be looking at the other, and the other must be looking at someone else who is closer (they are the longest edge after all). No-one can be looking at the first criminal (they're all by definition closer to someone else than to her). She is unwatched. Or more simply still: trivially, one node on the longest connected edge must be unwatched unless that edge is a cycle of two (which can only possibly happen when there are only two nodes). I think that might be proof enough without anything further?
@@tonywoodhouse But you wrote exactly what galoomba wrote. I don't think you made it shorter. I believe this is the easiest proof out there.
Before watching the solution:
Among the criminals who are not paired up, the criminal with the longest watching distance cannot have anyone else watching him.
That's what I got too! Guess our thought process was a bit rare looking at the rest of the comments
Assume all criminals are watched. This means the graph must contain some number of odd cyclic subgraphs and some number of pairs of double-watchers. We can ignore the pairs of watchers and instead focus on a single cyclic subgraph. (this subgraph necessarily exists, because if you remove some even number of criminals who are watching each other, than a cycle of 3 or more must exist to satisfy the problem). If you investigate any odd directed cyclical graph, you find that the longest edge of the graph violates the rules of the problem. The node watching along the longest edge will instead watch along another edge which is shorter and guaranteed to exist, breaking the cycle and leaving an unwatched criminal. By contradiction, it is impossible for every criminal to be watched.
Edit: forgot to add that trivially if all but one criminal is engaged in a staredown, then obviously the remaining one is unwatched.
Wow, I have solved it in 2 seconds. This is first time happened to me. And I don't even know graphs too well
The proof I came up with after pausing the video: I have N=2n+1 dots (people), and each person watches one other, meaning I also have N arrows, one coming out of every dot ("outgoing arrow"). Assume for sake of contradiction that everyone is watched, so everyone has at least one "incoming arrow". It can't be that a dot has 2 incoming arrows, since that leaves too few incoming arrows for everyone else.
So, we have a graph where each vertex has exactly one outgoing and incoming arrow. The graph must therefore look like a bunch of disjoint cycles (start at any vertex --- the "head", keep traveling along outgoing arrows, must eventually run into a vertex I've seen before because only finitely many dots, and the first such vertex I run into again must be the "head", since otherwise if it was an intermediate vertex, there would be 2 incoming arrows).
I claim any cycle of length > 2 can't exist: suppose we go A to B to C ... to Z to A (where Z could be C, but A,B,C are distinct). By the rule of the outgoing arrow going to the closest person to you, d(A,B) > d(B,C) > ... > d(Z,A). But then Z is closer to A than B, so in fact the outgoing arrow from A would have gone to Z, not B.
(The reason this proof fails for length 2 is because I should say: d(A,B) >= d(B,C), and because C is not A, in fact the inequality is strict. This last part is not true if C=A, i.e. length 2)
But if the graph is made of a bunch of cycles of lengths 2, then there must be even number of dots; contradiction.
> So exactly your friend's proof. I like your proof by induction!
I mean the proof is in the description. They're all different distances apart and watching the criminal closest to them. That means one criminal will always be the furstest from any other criminal and thus unwatched.
I don't think it's quite so simple because that doesn't explain why the result fails with an even number of criminals. Oddness is very important.
Donkeys, Donkeys. Please reflect the real world. This set includes you Donkeys.
Great problem.
Since I am a researcher in graph theory and combinatorics, one may consider that I am cheating.
Consider the directed graph G whose edges u->v mean that u watches v.
1. Along a path u->v->w…, the distance decreases because if v does not watch u, it is because w is closer.
2. Apart from 2-cycles u->v->u, there are no cycles. By contradiction, if u1->u2->…->up->u1 is a cycle, by 1. d(u1, u2)>d(up, u1). But distances are symmetric and thus u1 would watch up and not u2.
3. If we remove all nodes involved in a 2-cycle, since the number of nodes is odd, we obtain a nonempty graph G'.
4. Let u1->u2->…->up be a simple path of maximum length in G'. Since G' contains no 2-cycle, up watches nobody and thus nobody watched u1 (in G, we could have p=2 and u2 watches u1).
Another proof.
Label each node with the distance of the closer neighbor.
1. Since all distances are distinct, we can have that u and v have the same label but no 3 nodes u, v, w can.
2. If 2 nodes have the same label, then they stare at each other. Mark the nodes of all such pairs as dead. Only living nodes can stare at livin nodes.
3. Since the number of nodes is odd, there is at least one living node.
4. Since distance are symmetric, nobody watches the node with highest label.
My question is why they are specifically criminals and not just people standing in a room
Provides motivation for making sure everyone is "watched" :D
Strange wording, it was presented as astronomers on different planets for me. It's a middle school level problem.
Great problem, very good quality. Found this channel today with the help of the mighty UA-cam Algorithmo, hope many others will do as well!
Some constructive (hopefully) criticism, at least for my personal taste: you might have to talk a little bit faster (now it's hard for our adhd brains to not get distracted), and somehow make the sound of your voice clearer (either by editing or buying new mic) - now it's kinda... muffled
I really enjoyed content and dont think that everything must be shaped as I like ^^ however I do believe some feedback may help you, especially if someone else will also express their opinions. Keep it going anyway, best of luck!
My approach: There is always a shortest edge, therefore every graph will have at least 1 pair of prisoners watching each other. Every prisoner needs to be watching an unwatched prisoner. Since couples are watching each other, they would have to be isolated from the rest of the graph. This would create a domino effect of pairing until there is only 1 prisoner left. 1 prisoner cannot watch themself, therefore there will always be at least 1 unwatched prisoner.
That would require two proofs, first needing to prove that in any case if there is a character not watching someone in the group, then there is always an unwatched person.
Then your proof, but you want to start the opposite way, via induction with Base case 1 person. Obviously unwatched.
Then for each 1+2n case, consider the shortest distance between any two members. They are watching each other, so they are both being watched.
For the remaining 2n-1 people, if anyone is watching the two self centered people, then we know from Proof 1 there is an unwatched person in this group.
Otherwise, induction applies for this smaller group, and eventually we will have a base case 1 unwatched person.
*My own nuanced proof:*
Let's construct the graph one step at a time, looking at each pair of criminals from closest to most distant and having each criminal who isn't already looking at someone else look at the other since they're the closest to them. When we look at a pair where exactly one criminal is already watching someone else, the other criminal starts watching them, yet remains unwatched since if they were being watched then they would be watching the criminal watching them too. If and when someone starts watching this unwatched criminal, that person then remains unwatched. When there are an odd number of criminals, at least one such pairing must happen because the criminals can't all be in pairs watching each other, therefore there must be at least one unwatched criminal.
What will be if criminals make equal sided polygon?
"no two pairs of criminals have the same distance between each other"
Is there a precondition that A1A2 != A2A3?
k > 2
@@TheArizus yes, but why can't three criminals stand on the equal distance from each other?
@@user-tk2jy8xr8b the definition of the problem says all the distances are distinct
Instead of looking at the shortest relationships, couldn't a simpler approach be to look at the longest relationships? If you can rank each criminal's closest distance to another criminal, then the "longest closest distance" will always be looking at someone else with another criminal who is closer.
A criminal can both be at the longest distance and shortest distance simultaneously.
Consider the following example. Suppose A and B have the longest distance, but A and C have the shortest distance and B and D have the 2nd shortest distance. Then it may be the case (of course not always but it may be) that A, C and B, D are in starring contests.
Unfortunately i don't think the longest distance argument works because of cases like this.
Why can't you make a cycle more than 2? If you have 6 prisoners in perfect circle, every neighbour is on the same distance so they have no reason to look not in the same direction because no neighbour is closer, this they can make a loop
In the problem it says that all the distances between criminals are different (to avoid exactly this problem probably, haha)
The induction proof in the video does not seem to be rigorous, would be my hunch.
4:50 - Doesn't the fact the directed edges change when you remove A&B make recursion invalid? Or at least requires a proof that the directed edge change can't result in X receiving a directed edge.
I think your proof is incomplete.
The details of the proof are at the end of the video but essentially it comes down to AB being minimal (which is why the video says "I will formalize this induction argument shortly")