11 ms·
The “Windmill” Problem on the 2011 International Mathematical Olympiad [video]
- AlexCoventry 7y agoI'm going to have to watch this later, because the cat I've got on my lap appears to be deeply alarmed by the blinking eyes of the "pi" avatar.
- x3n0ph3n3 7y agoThis guy makes excellent math visualization videos -- some of the best I've ever seen.
- quickthrower2 7y agoI recommend watching the "But what is the Fourier Transform? A visual introduction." https://www.youtube.com/watch?v=spUNpyF58BY https://www.youtube.com/watch?v=spUNpyF58BY. Beautiful.
- ranie93 7y agoYes! I really enjoy them as well-- and he has his animation software on github: https://github.com/3b1b/manim https://github.com/3b1b/manim
- Chris2048 7y agoWould be interested in how this stacks against mathbox2* * https://acko.net/blog/mathbox2/ https://acko.net/blog/mathbox2/
- fspeech 7y agoThe video gives excellent intuitions. But do try writing down a rigorous argument after watching it!
- _Microft 7y agoSince this is a puzzle that will certainly nerd-snipe a number of us, could someone who already watched the video tell us if there is a "spoiler" moment in it or if we could watch it bit by bit in case that we get stuck?
- jerf 7y agoThere's maybe a step or two's worth of that, then the answer. The video is not explicitly structured as a set of clues, it only accidentally half-does that because it builds up to the answer mathematically, but I would not say the steps are "even" in size.
- Tallasatree 7y agois this in essence a convex-hull problem, except instead of closing, we continue?
- AnimalMuppet 7y agoI don't think so. In a convex hull, you only visit points on the hull of the set, not in the interior. In this problem, you visit points in the interior too (if I understand correctly).
- saagarjha 7y agoYou get to choose the line so that this circuit is possible. If you didn’t, you’d essentially be able to form a convex hull and thus not visit all the points.
- bcyn 7y agoI think he presents a line of reasoning that also helps to formalize why finding a convex hull works.
- utopcell 7y agoNo. In fact, in the end he shows a list of approaches one might think are related but turn out not to be, and computing convex hulls is one of them.
- deleted 7y ago[deleted]
- lelf 7y agoThe problem: Let S be a finite set of at least two points in the plane. Assume that no three points of S are collinear. By a windmill we mean a process as follows. Start with a line l going through a point P ∈ S. Rotate l clockwise around the pivot P until the line contains another point Q of S. The point Q now takes over as the new pivot. This process continues indefinitely, with the pivot always being a point from S. Show that for a suitable P ∈ S and a suitable starting line l containing P, the resulting windmill will visit each point of S as a pivot infinitely often.
- eruci 7y agoThis can be formally solved by constructing the arrangement of lines passing through each set of two points, then computing the dual of the arrangement. The cell with the maximum depth on the arrangement contains the points in the "middle", meaning they have as many points on one side, as they have on the other. Then you can prove that a line starting on any such point will visit every other point an infinite number of times.
- boyobo 7y agoJust pick a point and rotate a line around that point continuously. Keep track of the number of points on the left. Since this count is essentially continuous (the jumps are of size 1), at some point during this rotation you will have an almost-balanced configuration (same number of points on left and right, up to parity error).
- eruci 7y agoYes, but it must be a point with certain properties, such that the same number of points are on either side of the line initially, otherwise, it would not work.
- boyobo 7y agoI am giving an alternate proof of your implicit statement "There exists a line which has the same number of points on each side". You did this by computing duals of cell arrangements. I am arguing that you don't need to do that. The proof I outlined will work for any point. Initially it might have the wrong number of points on both sides but for some rotation it will have the correct number of points on both sides.
- rvz 7y agoThe approach to solving this problem looks very elegant to viewers with/without a mathematical background and the author's use of visual explanations towards solving it step-by-step helps untangle the ambiguities in this puzzle. Correctly proving this without assistance is one thing, but explaining it to non-mathematicians via a YouTube video sounds so difficult that some I.M.O candidates may struggle with this. Even so, I think the author is perhaps a professional/skilled mathematician or both which greatly helps explain this proof in a concise fashion. On the other hand, I find that problems like this may be (ab)used in the future for technical interviews at financial/asset/investment management institutions for software engineering roles. Over the top indeed, but I think it would very difficult to justify using mathematical proof questions in interviews.
- Analemma_ 7y ago> On the other hand, I find that problems like this may be (ab)used in the future for technical interviews at financial/asset/investment management institutions for software engineering roles I'm not really worried. In general, the trend for hiring software engineers has been away from silly puzzles, not towards. Microsoft and Google both used to use them and now they don't, and other companies have been following along. In general, hiring fads and follow-the-leader are not great, but in this case it's for the best that other companies have taken their lead. To be sure, there are still lots of other problems with how developers are hired, but the stupid puzzles at least have mostly faded away.
- codingslave 7y agoReally? If anything I thought that the use of puzzle/algorithms questions is only accelerating. Microsoft asks leetcode, as does google.
- Analemma_ 7y agoI don't like leetcode, but at least leetcode problems are actual algorithmic/programming questions. What I was talking about in my comment is the "Why are manhole covers round"-type questions that used to be endemic but have fortunately mostly vanished. A pure mathematics question like in the linked video, with no connection to algorithms/CS, would fall under that definition to me.
- gambiting 7y agoNow I really want to know what question 6 was and an equally informative explanation what made it so hard!
- mrosett 7y agoIt looks like a pure geometry problem: https://artofproblemsolving.com/community/c6h418983p2365045 https://artofproblemsolving.com/community/c6h418983p2365045
- authoritarian 7y agoNumberphile has a couple videos about it https://www.youtube.com/watch?v=Y30VF3cSIYQ https://www.youtube.com/watch?v=Y30VF3cSIYQ https://www.youtube.com/watch?v=L0Vj_7Y2-xY https://www.youtube.com/watch?v=L0Vj_7Y2-xY
- AlexCoventry 7y agoThe actual question is at https://www.youtube.com/watch?v=Y30VF3cSIYQ#t=5m31s https://www.youtube.com/watch?v=Y30VF3cSIYQ#t=5m31s , if you don't want to hear a 5 minute rant about how hard it is.
- d--b 7y agoMmh intuitively, I would have thought that the proof would involve the enveloppe of points. If the line starts with a section that crosses inside the enveloppe of the set of points then it remains so, and hits all points, while a line that starts outside remains outside and so can avoid some points. Any formal proof along those lines?
- ghusbands 7y agoBy envelope, you likely mean the convex hull. By "crosses inside the envelope", you probably mean it intersects the hull. That does not work. If you have a triangle inside a triangle and a central point inside that, that gives you seven points. If you start on the inner triangle, intersecting the outer triangle (convex hull), you can repeatedly visit the points of the triangles without touching the central point.
- chongli 7y agoThis phenomenon, whereby a person who knows the "trick" to solve a puzzle cannot accurate gauge its difficulty, seems to extend beyond mathematics. Adventure games (including text-based, parser-driven, and point-and-click) suffer badly from this problem. They are chock-full of puzzles that only make sense in hindsight (if at all). They can be really fun though!
- OscarCunningham 7y agoTanya Khovanova has a paper https://arxiv.org/abs/1110.1556 https://arxiv.org/abs/1110.1556 with a list of some more of these problems with easy solutions that are hard to find. She calls them "Jewish Problems" because they were used by USSR universities to discriminate against Jewish applicants. The applicants would fail to solve them but the university would justifiably be able to claim they were easy.
- dxbydt 7y agoHey, thank you so much for posting this! I picked a random problem ( the one on logs) in that paper and solved it under 1 minute. I feel like a million bucks now!
- baddox 7y agoBecause of this fact, I can only imagine how difficult game design must be (particularly puzzle games). The "perfect" experience is for the player to have just enough difficult figuring out a solution that they feel clever when they succeed. I remember feeling this way several times in my first play-through of Portal, but then I remember Portal 2 feeling way too "guided" (sometimes even easy), as if they had play-tested it to death.
- gorgoiler 7y agoThis is great, the visualization is so helpful. Even better I think would be if the point field was counter rotating and scrolling such that the windmill was constantly falling forwards and backwards either side of being vertical, keeping the two sets of points bisected and on either side of the screen.
- tromp 7y agoI enjoyed watching this similarly insightful video [1] on "The hardest problem on the hardest test" of the Putnam Competition. [1] https://www.youtube.com/watch?v=OkmNXy7er84 https://www.youtube.com/watch?v=OkmNXy7er84
- deleted 7y ago[deleted]
- carapace 7y agoThis is hella cool. "Knowing when the math is hard is way harder than the math itself" But then maybe the math is hard only because it's not being explained well? (I hope it's uncontroversial to suggest that our current methods of teaching math are not the best of all possible worlds.) I get that this problem came up in the context of of a math puzzle contest, and that some people enjoy solving puzzles. I am questioning their utility as an educational device. I kinda think that we should teach math as fast as we can so that we can concentrate on the stuff that's really hard, not just apparently hard because someone is being coy with the easy routes.
- boyobo 7y agoAre you trying to say that math is hard because the teachers are withholding all the tricks? > I am questioning their utility as an educational device. Puzzles like this aren't found in mainstream math education contexts. As you acknowledged in your post, they are only found in math competitions. What do you mean?
- carapace 7y ago> Are you trying to say that math is hard because the teachers are withholding all the tricks? Kind of, although I don't think they do it deliberately. Things like teaching logarithms without a slide rule. > Puzzles like this aren't found in mainstream math education contexts. As you acknowledged in your post, they are only found in math competitions. What do you mean? You're right. Let me try again. Check out William Bricken's "Iconic Math" http://iconicmath.com/ http://iconicmath.com/ or "Proofs without Words" https://en.wikipedia.org/wiki/Proof_without_words https://en.wikipedia.org/wiki/Proof_without_words or the other 3Blue1Brown videos for that matter. I think that most math seems hard to most people only because we are not creative in the ways that it is presented. We should use science to figure out how to present math so that people get it as fast as they can, in part so that we can find and concentrate on the actually hard math problems. E.g. Alan Kay using Smalltalk to teach calculus to little kids in the context of modelling falling objects, to me kinda proves that it shouldn't take a whole semester to teach calculus to teenagers.
- prvc 7y agoGreat presentation. I wonder whether all correct solutions submitted on the contest day had the same solution.
- sAbakumoff 7y agoFrom the same channel : https://www.youtube.com/watch?v=jsYwFizhncE https://www.youtube.com/watch?v=jsYwFizhncE overview of very elegant connection between blocks collision and PI.