How Many Guards are Enough?

[@MikusBBS]

Very useful for game developers.

[@MikusBBS]

+Gaeuvyen that's what I ment by useful. Plus if you use cctv in a game knowing this might come in handy in order to make the game harder.

[@NemosChannel]

+Gaeuvyen exactly! So you would know to choose a lower number.

[@bernardeisberg9250]

+Jakub Mikowicz Hate those levels.

[@zorm_]

but if the guards cannot move then you can just walk in, no problem

[@M4niacks2]

if in the step of coloring triangles you pick the same color for the smallest angle in every triangle your guards dont need more than 120 degree of vision

[@RelativelyBest]

If the guards can all see in every direction, why would you put them in the corners? Wouldn't it make more sense to put them at middle points that overlook as much of the museum as possible in every given direction?

[@TippingPointMath]

+RelativelyBest That's a great question. However, analysis becomes much more difficult. Can you give an example of museum where fewer guards in the middle protects a museum than any configuration with guards at the corners?

[@RelativelyBest]

+Tipping Point Math Well, I'm actually horribly bad a math - we are more or less talking dyscalculia here. That's kinda why I watch math videos, to see how much of it I can absorb before my brain just shuts down. So it's possible I'm about to embarrass myself now, but here goes. You said that if you can see a corner, a guard standing at the corner can also see you. Since this works both ways, the optimal position for a guard would be where he can see as many corners as possible as well as anything from one corner to another - keeping in mind his field of vision is a complete circle around him. If we take that first red museum outline of yours, I would put Guard 1 in the lower left room on the right side where the horizontal center line intersects with the vertical center line of the corridor going up. Then I move him slightly to the left so that the vertical line falls within the topmost alcove in the large room above. He can now see all of the room he's in, and all the way up the corridor to the alcove. In the upper left room, I don't think it matters much exactly where I place the guard as long as he can see the whole room. Let's say I want to try your Lonely Guard challenge, though. In that case I draw a line diagonally from the right corner of the upwards corridor to the upper right corner of the room and place Guard 2 on that line about one third of the way from the upper end. He can now see the entire room except a blind spot in the top alcove which is covered by Guard 1. The two of them can't see each other because a corner is in the way. I then place Guard 3 in the middle of the T-section to the right, giving him a clear view of all three corridors. He can't see 1 and 2 due to corners. Guard 4 simply goes into the center of the bottom rectangular room around the bend. He can watch his room and the horizontal corridor, and obviously non of the other guards can see him or vice versa. The tricky part is the alcove on the left side of the first corridor, which always seems to be a blind spot for Guards 1 and 2. So to keep it simple I just put Guard 5 inside the alcove. By placing him in the upper left corner, he remains hidden from Guard 1 and 2. (This breaks the "no guards in the corners" thing I've had going so far, but that wasn't part of the problem anyway so I don't really care.) So, I got it to a minimum of 5 guards to watch that particular museum, non of whom can see each other. I don't know if this is fewer than ANY configuration with guards in the corners, but it was the simplest way I found to do it. (And, again, I'm awful at math.)

[@TippingPointMath]

+RelativelyBest Not bad. As you note at the end of the video, I can do it with 5 guards as well. I think one can argue that you can't do any better.

[@ablejack3]

+Tipping Point Math: "Can you give an example of museum where fewer guards in the middle protects a museum than any configuration with guards at the corners?" Yes. A floor plan in the shape of a star (at least five points) could be entirely seen by one guard in the middle. If the guards were only to be at a corner then the star shaped floor would require at least two guards.

[@TippingPointMath]

+Ablejack Courtney Very good. Unfortunately, there does not seem to be any way to find minimum number of guards needed for a general museum. The Art Gallery Theorem at least gives a start.

[@Legalcat1]

minute physics brought me here

[@zionj104]

You sure about that?

[@kkoranges]

I think the lonely guard theorem is true. Suppose you have already placed some guards that cannot see each other, but there is some part of the gallery unguarded. Put a guard in that region, it can't see any of the other guards, but that area is now watched by a guard. Repeat until all the unseen areas are covered.

[@Devilyaki]

The less guards you have the less guards catwoman has to deal with to steal your stuff :3

[@milkYw4iMC]

Using 3-colorability of maximal outerplanar graphs, did not see that coming.

[@groverwatch2171]

"How many guards are enough?" If you pick the right person, one.

[@reda29100]

The question then becomes "How many lazy guards are enough?"

[@christopherosborne4381]

"Is it always possible to place the guards at corners to see the whole museum, but no guard sees another?" I'm almost certain. I'll try to explain, though I don't normally do geometry proofs, so this might be a tad rough. Before I begin, I'm going to define the "Corner-Point Test" such that, for a specific corner *C*, given any point _p_ contained either inside or on the boundary of a polygon, if there exists a line segment that either does not intersect with the boundary of the polygon connecting these two points, or intersects with the boundary infinitely many times (retraces it), then it passes the "Corner-Point Test". Otherwise, it fails. Also, I'll define the "Grey Boundary" as a line segment that separates a region of points that pass the "Corner-Point Test" from the region of points that fail it. Any point _p_ on this line then by definition passes the Corner-Point test, but for any disk around _p_ with radius *r*>0, there exists a point _q_ such that _q_ fails the Corner-Point test. We have two possibilities: The polygon is convex or the polygon is concave. If the polygon is convex, then for every corner *C*(n), given any point _p_ contained in the polygon, the corner passes the "Corner-Point Test". So for any convex polygon, you need only one guard, and the lone guard conjecture holds. If the polygon is concave, then by definition it has an internal angle larger than 180 degrees. Because of this, there exist corners that fail the Corner-Point Test. Now, if at least one corner passes the Corner-Point Test, then the concave polygon requires only one guard, and the lone guard conjecture holds. If there exists no corner that passes the Corner-Point Test, then choose a corner *C*(1). For any point _p_ that doesn't satisfy the Corner-Point test, there exists a disk with radius *r*

[@sierra5065]

God dam that's a full theory for a proof and in a KZbin comment no less I salute you good sir

[@adamtasma13]

+Christopher Osborne Second Salute

[@JuanPetter]

+Christopher Osborne goddamn a waz lazy to read all u should do a video

[@christopherosborne4381]

Gaeuvyen As long as it is a _convex_ polygon (a stop sign), 1 guard is all that is necessary. Think about it. A convex polygon means all the angles are less than 180 degrees, meaning that there are no corners that stick inward. You can pick any corner of the polygon, and given any point belonging to the polygon, there exists a line connecting the two points such that it does not intersect with the boundary. Now, if it is a _concave_ polygon, a single guard doesn't hold for every corner, and sometimes you must have more than one for that case.

[@tuerda]

+Christopher Osborne That certainly works, but there is a MUCH easier solution (which I added as a separate comment . . . I shouldn't have done that but I hadn't read through the comments section yet): Note that following the rules assigned, if a guard at A sees a guard at B, then the guard at B also sees the guard at A. Now for any museum, place the guards Using the following algorithm: 1) Place the first guard anywhere. 2) If the guards which have already been placed see the entire museum, you are done, otherwise: 3) There is a part of the museum that is not seen by at least one guard; place a new guard anywhere in this area. 4) Back to 2. All guards are lonely by construction. Since each guard goes where no previous guard can see him, then he cannot see any of them either. If the area is restricted to a polygon it is fairly evident that this procedure will eventually end, because each guard sees all of the convex section he is in, and there are finitely many of those. Your construction is likely to be a good bit more efficient than mine though (probably uses fewer guards)

[@RedsBoneStuff]

But who will guard the guards? :)

[@Redreu32]

+RedsBoneStuff CCTV

[@fibonacci112358s]

A Good Guy with an AR15. Too soon? :D

[@antonioarcudi1897]

Your mother

[@RedsBoneStuff]

Antonio Arcudi I'll tell you who. JOHN CENA!!!!

[@antonioarcudi1897]

RedsBoneStuff However, I was just joking bro ;) #JOHNCENA FORGUARDINGGUARDS!

[@kikithatsit2532]

OH MY GOD THIS IS INTERESTING I NEED 24 MORE HOURS OF THIS CONTENT!!!

[@adakarga]

I think I have a counterexample to your conjecture: The region between two concentric similar triangles (with parallel sides of course), which might be called a "triangular annulus". Any corner would see all other corners, but would miss some area. So you might need to limit the conjecture to "simply connected" galleries.

[@TippingPointMath]

+adakarga Your example is legit. In the video, I only discussed simply-connected galleries, so that situation is still unresolved.

[@southpoleelf5650]

+adakarga I mean his proof was only for polygons and dat ain't no polygon

[@cd-ux9ot]

I thought of the concentric triangles too. Then I looked up the definition of a polygon and it says the sides must form a path. (Wikipedia)

[@adakarga]

yeah, you're all definitely right. i mistook the definition of a polygon far too wide.

[@alexnobody1]

But why would you want the guards to be lonely? : (

[@bilib1891]

Because capitalism

[@reda29100]

if no one guard sees the other then how can we be sure that no guard steals the monuments while no other one witnesses?

[@kubokubo722]

If no one guard sees the other then how can they help if the other gets idk STABBED?

[@ErnestJay88]

Actually, "3 Guards max" principle is simple : 2 guards on museum, one on the entrance and other on the exit. put CCTV on every corner at that museum 1 guard on security room where he/she can watch every corner from CCTV display simple and efficient !

[@Trinexx42]

After playing Payday 2, I know that this is incorrect. Sneak into security room, kill guard, all cameras are down.

[@TheRomanRuler]

Nevan Lowe Haha, true. I suggest Guard of 100 men armed with Rifles, bayonets and Trench coats. Why? People go to Britain to watch British Guards, they WOULD come to X country to watch 100 men in cool trench coats guarding tiny museum with 3 or so items.

[@NoActuallyGo-KCUF-Yourself]

TheRomanRuler I like it. The guards *are* the exhibit.

[@jesseli9868]

Nevan Lowe New strategy: one guard watching the CCTV display, the two guards at entrance and exit, and one guard watching the security room door.

[@Trinexx42]

jesse li Well use a silenced sniper rifle and shoot through the wall and kill the camera guard.

[@osricthebrash6995]

You can just use 1 guard and have the entire wall become a gigantic mirror

[@TippingPointMath]

+Osric the Brash This raises another question: if the wall is a mirror, is every point visible from every other point? Is there at least one point that sees every other point? This will be the topic for another video!

[@mygiantinvisibleyeah]

The mirror themselves and how they reflect the room itself IS the art.

[@kubokubo722]

Hanging anything on such wall would obstruct the view of some parts behind the corner.

[@elibaum6648]

For the "Lonely Guard Conjecture": I was going to say it wasn't possible based on Chvatal's Comb, at 1:08. But you could put a guard in the lower-left corner, then each of the remaining five guards in the "teeth" of the comb. So maybe it is always true?

[@learningsuper6785]

Interesting video. Thanks Tipping Point Math.

[@deltaxcd]

obviouosly this is possible to place guards in the corners where they dont see each other but this may require more guards than minimum for that room

[@TheTexastim]

8 cameras , 1 operator , 2 guards on the floor .boom

[@theprofessionalfence-sitter]

A stronger version of the "Lonely Guard Conjecture" is not true (even for simply connected rooms): It is not always possible to guard the room with the smallest possible number of guards in such a way that no guard sees any other. Counterexample: ________ | | |/| |\| | | |\| |/| | | ----------- It can be guarded by two guards, but not in such a way that no guard sees the other one. Though that is possible with more guards.

[@InfiniteLaundry]

How many guards are enough if every guard needs to be seen by at least one other guard? (maybe because the museum has found out that a famous art thief has managed to infiltrate the museum by getting hired as a guard himself, but the museum doesn't know which guard is the art thief.)

[@tuerda]

Lonely guard conjecture is true, and there is a pretty easy proof: Note that following the rules assigned, if a guard at A sees a guard at B, then the guard at B also sees the guard at A. Now for any museum, place the guards Using the following algorithm: 1) Place the first guard anywhere. 2) If the guards which have already been placed see the entire museum, you are done, otherwise: 3) There is a part of the museum that is not seen by at least one guard, place a new guard anywhere in this area. 4) Back to 2. Now this is likely to end up with a lot more guards than are actually necessary, but they will all be lonely by construction. Since each guard goes where no previous guard can see him, then he cannot see any of them either. If the area is restricted to a polygon it is fairly evident that this procedure will eventually end, because each guard sees all of the convex section he is in, and there are finitely many of those. This procedure will not necessarily terminate if you allow for weird enough shapes. A more interesting question might be to ask if there is a placement of guards which is optimal (no placement of guards that sees the whole museum and has fewer guards) and where all guards are lonely. This is a harder question and I am not sure if it is true or not.

[@jancanda2591]

According to the Lonely guard conjecture, the guards have to be in the corners, while your proof uses also guards in the middle of a room. The conjecture can still be true, but that does not prove it.

[@deltaxcd]

You made me think If guards placed on the corners connected by same line can see each other ir not in this puzzle?

[@tuerda]

Yes. I misheard the conditions of the puzzle. The conjecture is still true though, and a correct solution was posted by Christopher Osborne.

[@richardsutcliffe8002]

assuming the walls are straight then yes after the first guard is placed any areas he can't see can be sealed off with a line from a corner to either another corner or a midpoint in an edge creating an area with at least one other corner (two or fewer corners are not an area) placing a guard in one of the other corner hides him from view repeat until all areas are covered

[@TheBreezus]

Now I can see this theorem being applied when we have robotic guards, and museum curators need to find out the lowest amount of guards to cover the entire space(2014).

[@satibel]

+Clarence Brown (“Breeze”) I think they are called cameras :p

[@MikeS7]

If someone bribed the guards wouldn't you need at least 2 on every corner to make sure all the art was safe?

[@MrBitviper]

excellent!! and now to find guards with eyes on the back of their heads :p

[@NoActuallyGo-KCUF-Yourself]

Or ones with necks so they can rotate their heads. And, if you want to get really fancy, feet to turn around. Heck, give them a stool that rotates to sit on . .

[@RonJohn63]

mdiem Keep rotating your head for 4 hours, and then tell us if that's a practical solution.

[@pantsik2]

I think that the "lonely guard conjecture" is true for the least number of guards required to watch the museum, for the following reason: If we had two guards at points A and B watching each other, then the line AB and some area between the two points would have been watched by both of the guards. That would be a waste of space and guard B for example could have moved further away to cover some more space that is not covered by guard A.

[@TimJSwan]

This video was so damn good that I subscribed.

[@cocasorigin]

I think the lonely guard conjecture is always possible

[@boberjackie]

omg a simple practical application of chromatic coloring? I shouldn't have skipped that class Q_Q

[@gottiku]

I love learning and all but my brain just got fucked.

[@GrEEnEyE089]

What do you think about my solution: First mark all corners like you did and place your first guard at a blue corner. If there is a blue corner that can not be seen by any guards place a guard there and repeat this step until the condition is not met anymore. Then check if there is a corner which can not be seen and place a guard there until there isn't and you are done.

[@WillHandwilljan]

My brain blue screened.

[@TippingPointMath]

To read a LOT more about this stuff, see the book by Joseph O'Rourke, "Art Gallery Theorems and Algorithms". It is online for free: cs.smith.edu/~orourke/books/ArtGalleryTheorems/art.html

[@pyramida2763]

i can make you a set up for this problem with only 4 guards needed, if i dont place them in corners. Guards will be named 1-4 from left to right, leaving out the second guard from the left (the one located in the in the only corner that isnt 90 degrees). Guard 1 will be put in a place where he can see the room in the left bottom, but also has view of the small hole in the the complete top of the gallery. Guard 2 stays in position, looking over most of the main hall. Guard 3 gets moved down a bit, to the down left corner of the room he was already in. Guard 4 gets moved up from where he was, to a position where he can see the old position of the fired guard (the not 90 degrees corner). But he also keeps watching over his own corridor.

[@dragmasanimation]

Me: (Reads title) (Hears him say to guard a museum) Me: All of them.

[@_bender4143]

You didn't explain about the sight of the guards.. I guessed they can see 90 degrees..

[@DisHonestGaming]

he said assuming the could see 360 degrees

[@haakonlo]

Since there are only triangles in the proof, it would also apply if the guards could only see 60 degrees (min-max of angle in triangle)?

[@haakonlo]

Haakon Nore Nevermind, does not work with 60 degrees.

[@ZmakiZ]

The guards can turn around and see in 360 degrees, but they cannot move from their position.

[@ahmadjaber3611]

this video is BEAUTIFUL!!!

[@kedwardsTWO]

Heh. Fantastic video for the thinking mind!

[@leoyang1.618]

Love this stuff

[@c-5921]

Now I know how to guard my lair.

[@satyakimukherjee8264]

is your conjecture an open problem or has it been solved

[@TippingPointMath]

As far as I know, it's new. And unresolved.

[@accursedcursive4935]

If it is assumed that two guards on corners of the same edge can see each other, then the answer is that it is not always possible to have the guards unable to see each other. The proof is a triangular room with a triangular pillar in the middle: All corners are visible from all corners, meaning only one guard can be placed, but the pillar prevents that one guard from seeing the whole room.

[@tradetor]

So,if I place a motion detector （supposedly can watch 270 degree ）on each corner, will that be perfect security ?

[@TippingPointMath]

Yes, for an orthogonal art gallery. But wouldn't it better to reduce the amount of equipment needed?

[@wilsonofcanada]

Tipping Point Math So only one guard using x camera on each corner

[@I0lcatz]

This is assuming a motion detector makes you safe. Just being alarmed that some one is there isn't always enough. I'd recommend a .45

[@tradetor]

Well, I never seen a guard working at night so I can't judge, but in the movie , they seems really ineffective in protecting valuables

[@Zorro9129]

"In the movie" Movies are unrealistic.

[@pwuhl]

Awesome video ! I love your work dude !

[@asdfghyter]

What is the theorem that says that such coloring is always possible?

[@TippingPointMath]

I don't know of a name. Once you color two adjacent corners with two different colors, the third color is uniquely determined. This in turn forces the color of another vertex to be uniquely determined, etc. One goes on in this manner to color the whole triangulation. The book cs.smith.edu/~orourke/books/ArtGalleryTheorems/art.html must have more details.

[@Shooterpirat]

you're a funny guy :D I like your videos! don't like math, but you make it entertaining ;)

[@BigDBrian]

To the open question, I'm gonna say yes. Because, say you have a guard, or any amount of guards in fact. There's two scenarios possible. 1. He, or they, can see every bit of the museum. In this case, there's no need to place another guard, and there's no problem. 2. He, or they, cannot see every bit of the museum. In this case, you can simply place another guard where they cannot see, and therefore you can place a lonely guard. Since at the start, condition 2 is met, you can extrapolate this from a shape where 1 guard is necessary up to infinity, meaning that this holds for any area, with any amount of guards required. It seems incredibly simple, so I'm wondering if I've got a detail wrong.

[@abanjoplayer]

+mrBorkD I'm no expert by any means, but that is precisely what I considered before reading the comments. I'm sure there must be something wrong with our reasoning or somebody would have though of the solution before us, but I would love to see a follow-up!

[@abanjoplayer]

+mrBorkD oh I see. Except this says nothing at all about the actual number of guards ( < n/3 ), only that there is a finite number of guards that makes this possible. Oops!!

[@BigDBrian]

chris musson Yes. Was that a part of the open question? that it had to be less than n/3 guards?

[@TheCandyDick]

+mrBorkD For your proof to work you would need to show that in condition 2 the part of the museum that the guards cannot see contains an edge. This is not true for every case i.e. there are constellations where the guards can see every edge of the museum but not the whole museum.

[@BigDBrian]

+TheCandyDick I was having a hard time imagining what you meant, but I believe I understand now. The reason my "proof" is incomplete is that you have to place a guard on an edge, yes? so if there's an unguarded spot which is away from all walls(an unlikely but possible scenario), then my method won't work. I feel like you could work around this problem using a method that could be applied to any case, a 'solution' to this subproblem, if you will, but I'm afraid it's beyond me.

[@adastras3]

Really cool!

[@clancyoshannessy9623]

Answer to the lonely guard conjecture; Yes, it is possible. Any position that is not currently guarded is a legitimate placement for a new guard. so one may place guards into the structure one by one. each time ensuring that the new guard is not in sight of any of the previous guards until there is no where left to guard.

[@zorm_]

If the guard are on the corners, then they couldn't survey a circular museum ^^

[@israelRaizer]

+Gaeuvyen no, a circle has no corners

[@israelRaizer]

Oh well, I thought a circle had, by definition, 0 corners...

[@israelRaizer]

+Gaeuvyen oh yeah, I must have confused the two

[@jancanda2591]

How exactly do you define the term "corner" in this statement? The usual definition of a corner as "a vertex of a polytope" does not make sense for a circle, since it is not a polytope. You could use the definition of a vertex of a curve ("a point with derivative 0") , but according to that definition even a triangle would have infinitely many "corners".

[@cd-ux9ot]

True but a polygon must have straight sides only and at least three sides. A circle has no corners. How about this question: How many edges does a cylinder have?

[@PrinsMaandag]

I would put half of the gaurds on patrol and let the other half be stationary.

[@vonniedobbs2626]

Must a polygon be topologically equivalent to a circle? In other words, is a polygon with a polygonal hole still be a valid polygon, even though it sort of divides the plane into three regions instead of the usual two? (If the answer to the first question is no, then I have found a counterexample to the Lonely Guard Conjecture)

[@TippingPointMath]

In the book by O'Rourke, "Art Gallery Theorems and Algorithms", cs.smith.edu/~orourke/books/ArtGalleryTheorems/art.html, he discusses art gallery theorems with holes. In Figure 5.2, p.128, all three galleries have one hole and require 3 guards. All of these are counter-examples to the Lonely Guard Conjecture. The video only posed the problem for polygons (no holes).

[@only2ndplace]

If I'm not mistaken, I have found a counterproof for the "Lonely Guard Conjecture" Think about a (equilateral) triangle which has an area in the shape of a smaller, similar triangle cut out from it's middle like this: / \ / \ / /\ \ / / \ \ / / \ \ / / \ \ / / \ \ / / hole \ \ / / \ \ / /_ _ _ _ _ \ \ / _ _ _ _ _ _ _ \ In this polygon, every corner can see every other corner, but there is no corner, that can see the whole museum (Assuming, that the guards can look alongside the walls) Of course, this counterproof only works if there's a hole in the polygon, so it would still be interesting to see, if the "Lonely Guard Conjecture" holds true for polygons without holes.

[@TippingPointMath]

Nice. I had made an earlier comment that the Lonely Guard Conjecture does not work when holes are allowed. But the conjecture is still unresolved for polygons without holes (as proposed in the video). It will be interesting to see what turns up.

[@only2ndplace]

Tipping Point Math Heh, sorry, I guess I didn't see that ^^'

[@TheMaplestrip]

It must be, right? I tried to think of a way for it to not be possible, but the whole point of a guard is to look at a point that no other guard can see. Put the guard inside of that point and he will do his job fine. I have a question: Is possible to make the Lonely Guard Conjecture not work with any specific room lay-out and maximum number of guards? Can you think up a room shape, say "you can only place two guards, no more" and make it impossible for the conjecture to work?

[@BloodshotEyeTinerary]

The perfect defense for the first map uses 4 guards, the second 3.

[@lokynokey4822]

Use cameras.

[@brandonperalta409]

Then you'd have the same problem, but with cameras.

[@RogerGarrett]

Brandon Peralta Nope. You need only one guard to watch the entire set of monitors from all of the cameras. :)

[@djchristo07]

Roger Garrett agreed

[@Takashiy]

The problem with cameras I think is that you lose the assumption that all of them can see 360 degrees around them. Perhaps it's kind of a stretch, but humans have pretty good spatial awareness in the sense that they can move their vision quickly. The problem with cameras is that most cameras used today have a moderately slow speed of rotation, so I wouldn't think it's reasonable enough (compared to human guards) to say that they have 360 degree vision.

[@ZiulzP]

Roger Garrett If someone gets into the control room then the other guards go blind.

[@N0S0L]

Why not just use security cameras, what do you think this is the 19 century

[@cannae920]

It's just an interesting geometry problem bro

[@N0S0L]

Seita Tsutsumi I know thats why i put a stupid comment on it XD

[@cachotognax3600]

mgs teaches that no matter the security cameras, there's always a way to bypass them, so nope.

[@oussamaoussama6364]

Same problem, what is the optimal number of cameras you need to cover all the musem, and where are you going to place them?

[@cannae920]

Oussama Oussama I realized that after I replied to Vixen XD

[@huh9170]

No they cant see except if there is a mirre somewhere

[@rickrickston3202]

I think I have a proof for the conjuncture: Divide the polygon into triangles. Take one of the triangles (call it ABC), and put a guard in one of the corners, say A. Clearly, the area of this triangle can be seen by this guard. Now, take the the triangle adjacent to ABC. Let the new point be D. If point D can be seen by the guard at A, then ABCD can be seen by the guard. The only way this is possible is if D is bounded (or subtended, or something, not sure of the exact term) by the lines AB and AC. Now, add another triangle, with new point E. Again, if E is bounded by AB and AC, it can be seen by the guard at A. Otherwise, place a guard at D. Add new triangle with new point E. Repeat until all triangles are covered.

[@themanwhocrys2705]

But what about the fact that the guards can only look at a limited field of area at one time?

[@garkeinen7034]

They can turn around!?

[@xHappygolucky724]

If the room is a circle do we need no guards then?

[@madelinescyphers5413]

+Kevin S. A circle is not a polygon, so the theory doesn't apply.

[@nightangel7239]

For the last question of guards not seeing each other, but having them see the entire museum, isn't that easy and intuitive? Simplify the problem to just seeing corners, and having obstacles that prevent you from seeing further. Place a guard any corner. If there is a corner they can't see, place another guard there. If the walls/obstacles are straight, you'd always, often inefficiently, get a solution where all of the corners are seen (Either by a guard viewing it, or being there). If every obstacle is straight, then with how every corner is visible, every obstacle is also fully visible to the guard hive-mind. If every corner is visible and every obstacle is fully visible, then wouldn't the entire museum be visible, if there's no obstacles in the centre, such as a large pole? Certainly not a proof by any means, but I'm a (hobbyist) programmer and we aren't smart enough to care about proofs, just step-by-steps to solve problems. (Efficiency can come when your boss complains that it's eating resources).

[@laguna84]

if hitman, assassin's creed, pay day 2 or thief enemies knew this we would have lots of problems

[@bobbishmax62]

Wouldn't any place that isn't seen by one guard just be seen by another?

[@shadowingyou]

For the last puzzle set where TPM is talking about the lonely guard theory... Do the guards HAVE to be in corners..? I got it down to four guards needed to guard that last museum and not five. However, I am imagining people behaving properly and the museum is not extremely heavy traffic. Honestly, I would not even know if I would trust doing this method anyways. Guess museum guards are different. Right hand side of the museum on the most southern wall, place a guard almost center, standing across from the corner which angles 270 degrees. That guard (going by the rule-set that they can see very damn well and perceive what's happening even better) will be able to see the approximately 95% of the dead end and 100% and the hallway heading North. So unless there is some small art piece which hides in the 5% corner and can be stolen easily, the guard should have no problem doing his job. Again, assuming that these guards are superb at their duties. Going off of just five guards, one of them is pulling basically 270 degrees overwatch. I hate the Western part of the museum with a small room gap. Whoever designs it like that should hire their own personal frelling guard.

[@lucashoffses9019]

Yes,it is possible. Place the guards at corners they can't see.

[@Y10Q]

What if they used cameras or mirrors?

[@Shiegao]

why now just have a circle and one guard in the middle

[@gerry7man555]

I have a solution, it's called sentry turrets.

[@RogerGarrett]

Hmmm, how about a museum with curved walls so that there are no corners?

[@burnall13]

For the "Lonely Guard Conjecture": Its true. Just follow these simple steps: Is there a place in your floor that isnt watched by a guard? yes: place a guard there. repeat the question. no: this means the whole floor is beeing watched, but we never placed a guard where he could be seen, so no guard can see another guard.

[@vonniedobbs2626]

The guards have to be in corners, sorry! But your proof does hold when they don't.

[@ObrnenaAndulka]

Veronica Dobbs Doesn't it also hold for when they do have to be ? Suppose there is an area that isn't watched by a guard - this area must always be a polygon, with two of it's corners being seen by other guard (guards) - these are the cornes at the edge incident to the watched area. Since 2d polygons have at least three corners , there must be a corner which is not watched by a guard.

[@burnall13]

ah, thanks. rewatched the video. Missed the part about the corners the last time.

[@burnall13]

ObrnenaAndulka thats true but not all sides of this polygon must be sides of the room and therefore not all corners of this polygon must be corners of the room.

[@ObrnenaAndulka]

Josef Tiefenbacher You're right , thanks ... I still believe the conjecture is true, but can't think of a proof for now, will have to think about it some more

[@jehutyps2]

My head hurts

[@DAR10162]

Yes it is possible in fact the last figure to showed was indeed the answer to your own question

[@sammiddleton7663]

It is possible IN THAT CASE. he asked if it was ALWAYS possible.

[@roygbiv176]

Sam Middleton it is always possible

[@DAR10162]

Sam Middleton ah i see i miss the wording sorry

[@SKEL45]

1) just one guard on a a watch tower that is overseeing the whole perimeter with a assault rifle 2) replace art with fakes (no guards) 3) heavily fortified museum walls that even Hitler would say WTF (no guards) if doors are sealed preventing a inside job would be the hardest part

[@mattroh7248]

Simple. MAKE THE WALLS A MIRROR

[@SeisoYabai]

Holy shit with this music in the background I thoguht I was watching the Dumbshit's Guide to Dark Souls by Wildpie101...

[@dermax4174]

The proof for this n/3 Guards thing is much simpler than shown: You will ALLWAYS see at least 3 corners since the only shape that is possible with 2 corners is a line and you cant stand "in" a line.

[@MatthiasUrlichs]

+Der Max This proves that you need ⌈n/3⌉ guards to see all the walls. However, since you only need two new corners to create a nook which no existing guard can look into, your result doesn't say anything about the area enclosed by the graph. Also, the video showed that the actual number is ⌊n/3⌋.

[@jkid1134]

Except you skipped like half of the proof, the parts about dissecting into triangles and coloring them. You can't just say "this is always true"

[@aby0ni]

my theorem is that you won't need more than n guards for a n sided polygon.

[@hrckhm]

Using this for camera

[@nuclearnyanboi]

Lonely guards? Oh no! Please, mathematicians. Human people don't like being lonely

[@Richard_is_cool]

Chvatal is not pronounced Chuatal. The v is a v and ch is like x in IPA.

[@richoz27]

Maths over complicating things... You only need 1 guard per entry/exit regardless of the corners as long as the guard can check every person going through.

[@ironcito1101]

+richoz27 That arrangement wouldn't help with things like people touching or vandalizing the exhibits, pickpockets stealing from other visitors, and so on.

[@richoz27]

Diego C. Cameras...

[@ironcito1101]

+richoz27 Cameras would see something going on but wouldn't be able to do anything about it.

[@richoz27]

Diego C. The guard will.

[@ironcito1101]

+richoz27 If you only have 1 guard per door, then something happens and one of those guards goes to check it out, then one door will be unguarded. Plus you'll need guards to watch the screens. It's not math that's complicating things, it's you :P

[@ThisUserHasBeenCanceled]

How does the triangulation work exactly? seems like arbitrarily drawn lines to me.

[@Namezzzzzzz]

+ThatGuyWhoDidThatThing it kinda is. you just keep drawing in lines between corner until you have all the floor seperatet into triangles. The video says it's always possible and it implicates that the solution always fits the following statements, but i can't prove that here. It is a little bit similar to integer factorization, which is proven to be always possible, but the actual calculation is not nesessary easy and is not following a strict set of rules.

[@mihirm3632]

there's another proof that it works!

[@kingquis3118]

it isn't always possible

[@middleclassseabass7178]

great video, and only 4k subs!

[@JerryFungNYC]

simple you buy a dozen of security camera and hire one guard and there it is....

[@dewinmoonl]

s l i c k p r o o f ! ! !

[@trombonista92]

subscribed

[@keskursay]

But what about Ben Stiller?

[@nuzod]

regarding this thing we need to take into account of a human vision range too. You said they were supposed to be stationary. So for the last question, NO. I am asian. Nuff said

[@kuncara]

in real life, its not as simple as that, by adding visitors there will be some blindspot and causing the need of more guards. but still nice theory and video.

[@CasimirdeHauteclocque]

That's why I prefer the version with movement detector: You want to detect moves at night, when the room is empty (or supposed to be empty), and try to buy the least amount of devices. Thats explain how they can look at 260 degrees and are not bothered with spectators

[@yoppindia]

If people are honest no guards are required!

[@Haseeebo]

LOL people are honest...that's funny

[@Nulono]

*fewer than one third

[@711lila]

what does n/3 mean?

[@pablogriswold421]

n is a natural number. /3 means you divide by three.

[@chrism6904]

Who watches the watchman?

[@yacabo111]

+Chris M The watchman watches himself

[@cerebroassasin24]

and touches himself

[@mohamedabd8285]

skill is more important

[@SoapyBubbles]

I have an answer. Security cameras.

[@BoberSmink64]

And 1 gaurd to watch them

[@njnonips5261]

yes

[@ikesteroma]

I expected this video to be a hit job on the NSA or something... Alas, it's just an math video devoid of politics. :)

[@huh9170]

Mirror*

[@austinrobinson4341]

or we could just design buildings in a more simple way so that no formula is necessary

[@thesteaksaignant]

Your algorithm will result having all the buildings convex and with only one room per floor ^^ Unless you specify a minimun surface of walls available to put all the paintings ? It would be interesting then ! (but then you'd probably get star-shaped buildings that can be entirely watched by one guard in the midle ?)