100

Building Houses Solution


Hello again, everyone! Last time, I set you a challenge– a challenge to write a sequence of numbers using numbers from 0 to 1, so that the first two numbers occupy different halves, and the first three numbers then occupy different thirds, and the first four numbers occupy different fourths, and so on. I set it up as a puzzle, building houses on a strip of land, so that every time a new person comes along, you have to re-share the land, so that everyone gets a plot of equal length. And I asked you, how many houses can you build? Can you do this indefinitely, or is there some sort of limit to it? Now, if you haven’t tried this already, please do! You can do this with a pen and paper, or if you haven’t seen this, we did make a computer game out of it. There’s a link in the description to this. So you just sort of point and click and build your houses as you go along. Do try this out now if you haven’t already, because I am going to give the solution. You see, you can’t do this indefinitely. There is a limit to how many houses you can build. And that limit is 17. Now, that’s really odd! 17 houses! So, for a start, it’s weird that you can’t do it indefinitely. That’s not obvious. There is a limit. The limit is 17, though. Why 17? Why not 18, or something else? Now, I am going to show you a solution, with 17 houses on it, which I’m going to do later. But first, I want to show you a proof– a proof that it’s not 18 houses. Now, to do that, we’re going to have to consider a number of steps with the land split up into different sized plots. I’m going to start by splitting the land into 9 equally-sized plots, and then I’m going to consider the tenths and the elevenths and the twelfths, and so on. And first, I’m going to consider the point that occupies the fifth plot after division by 9. Let’s call that ‘x.’ So x is somewhere between 4/9 and 5/9. But let’s say x is equal to 0.46. But if x is 0.46, then I know that 0.46 occupies the fifth plot after division by 10. And it also occupies the sixth plot after division by 11. And the sixth plot after division by 12. That’s all automatic. Now let’s consider the point that occupies the fourth plot after division by 9. Let’s call that ‘y,’ and we’ll try and work out the value of y. Now, y might occupy the fourth or fifth plot after division by 10. But it can’t occupy the fifth plot because that belongs to x, So y must occupy the fourth plot. That means y must be less than 4/10, or 0.4. Looking at division by 11, y crosses a border again, so it might occupy the fourth plot, or the fifth plot. If y occupies the fourth plot, that means the fifth plot is empty. That’s OK. That just means the empty plot must be occupied by the 11th point. But that’s a problem when you look at division by 12, because the eleventh point must either share a plot with either x or y, and that’s not allowed. So y cannot occupy the fourth plot after division by 11. It must occupy the fifth plot after division by 11. And that means we’ve worked out that y must be between 4/11 and 4/10. In other words, y is between 0.364 and 0.4. Now let’s add a new point. We’ll call that zed, and that occupies the fourth plot after division by 12. And we’re now going to go through the same process considering what happens after division by 13, 14 and 15. And we’ll discover that y occupies the sixth plot after division by 15, and zed occupies the fifth plot after division by 15. Continuing on again, we now see that y occupies the seventh plot after division by 16, and zed will occupy the fifth plot. But that means the sixth plot is going to be empty. So that must be filled with the 16th point. Now consider the next division. So y would occupy the seventh plot, after division by 17, and zed will occupy the fifth plot, and the new point occupies the sixth plot. But like before, this is a problem, this means the 16th point will share a plot with either zed or y, when we divide by 18, and that can’t happen. So we’ve found that we have failed at division by 18. But this was all working perfectly fine up to and including division by 17. This is what happens when I choose x to be 0.46. But what if I chose a different point? Well, the full proof shows that you will always get stuck for any value of x. And remember, x was defined to be the point in the fifth plot after division by 9. In fact, I chose this value of x because we could get as far as division by 17. Other choices for x actually fail a lot sooner. So the proof shows that it fails at division by 18. So a sequence of 18 points does not exist. That’s impossible. But the same method may also be applied to construct solutions, including solutions up to and including 17 points. For example, here is one solution where the sixth point is 0.46– that was x in my proof. And zed and y are exactly where I predicted they would be. The thing to remember is it’s not just the values of the solution that are important, but it’s the order, as well. For example, we can’t just divide the line into, say, 100 equal parts, and then put a point in each part. No–the first two points have to be in different halves. The first three points have to be in different thirds, and so on. And it’s this restriction that gives us this limit. The problem is related to the Farey sequence of order 18. That’s the ordered sequence of all fractions with denominators less than, or equal to, 18. And the problem is actually called “The Irregularity of Distributions,” or “The 18 Point Problem.” Now, this proof actually goes back to the 1960’s. It’s very functional, though. It does show that you can’t construct an 18th point, and that you can construct a 17th point. So there are solutions with 17. But on a deeper level, it doesn’t really tell you why it’s that number. And if you’re thinking that, I agree. It’s really curious; it’s really odd. I don’t think it’s a very well-known fact, which is why I wanted to share it with you. Finally, I just want to give some thanks to Christian Perfect for making the game for us to use. And, well–if you have been, thanks for watching!

Bernard Jenkins

100 Comments

  1. Loved this problem only got 10 by trial and error.
    Singing banana is there any chance you could do a video about the (near) impossible to find prime numbers function/sequence anytime soon? I hear it has enourmous consequences in today's world and i'd like to hear your word on it 🙂

  2. I love watching your videos, be they here or over on Brady's channel. So much information and knowledge. <3

  3. These phenomena should be known by more than just experts. Thanks for sharing. They are an element of the beauty of nature.

  4. All right, sorry, I'll kind of repost it here.
    I spent hours thinking about it and I surprisingly had an intuition that led me to basically every information in this video, but, as you said, I don't really understand. Is there seriously not a deeper explaination as to why is 17 the limit?

  5. These problems always seem innocuous, but after you post the solution I realize I had no hope of solving it.

  6. Can anyone shed light on a proof #2 question. Does Case A contradiction demonstrate that x sup 5 sub 9 cannot be < 5/11 and _> 4/9 FOR ALL N (not just N=18)?

  7. 4:07 Why do you have to fill an empty plot? You might place the 16th number in an already occupied plot that becomes empty when you divide the whole thing by 17.

  8. Hmm, I was getting closer when I took someones 17 point solution and traced it back to note that the points couldnt wiggle from side to side enough to get to 18.
    but I ended up stumped by the fact that I was only really proving that one sequence of 17 points couldnt be modified to 18 rather than all of them.

    Also, I knew a prime was going to stick its oar in somewhere ¬.¬

  9. I wonder if the limit would still be 17 if you were allocating points to rings of equal area within a circle.

  10. Aww, my gut told me it was infinite. I guess I was close, seventeen is more than I can count on my fingers. So for all intents and purposes, it is infinite 😛

  11. At 2:00 when you say "let's say that x=0.46" I kind of disagree that it's a proof anymore. There's no reason to fix a single value for x, there is infinetely many possibilities and you can't treat all cases without grouping them.

    The case you actually treated in the video is x∈[5/11 ; 6/13[, but even that is only one case out of the 6 necessary to actualy prove the theorem.
    I'm confident you know all of that of course and that you did only one case because it makes a much more simpler explanation but in you presentation you make it sounds like it's a proof and as is, it doesn't quite prove anything.

    P.S : Sorry for my awful english.

  12. So my question is how many solutions are there because you hinted a the fact that there are multiple and on a number line it makes sense that there would be infinite but to only is there any numbers which have to occupy exactly one point (due to the rounding) or do the numbers within the ranges always have to be in the same order?

  13. I managed to get 11 houses built. I appreciate this solution a lot more since I already bashed my head against it for a day.

  14. Yay, I got 17 points when I did it the other day. Although all I did was copy someones 16 list and add one more point that they forgot to add themselves.

  15. That was a very smooth way to find the maximum amount of homes allowed.

  16. There seems to be a potential for a graph like (Size of plots at each point, Function of the necessary distance between points), perhaps average distance.

  17. This was some impressively effective nerd sniping: https://xkcd.com/356/
    I was completely wrong with my guess, and it hurts that the proof doesn't provide more intuition. Great video; I'll probably end up reading about this more over the weekend.

  18. Turns out whoever guessed 24 in the frist video was actually pretty close (especially given the fact that there infinitely many integers).

  19. James, what if every time we split the land we added that size division to the end of the plot? how would that effect the equation? 

  20. I'm sorry — I love your videos, but "if you have been"… Anyone you say that to will have been watching, else they'll never get that far.  I don't think there are many people who run around YouTube jumping to the ends of videos just to hear people go "thanks for watching"

  21. Read the proof. You weren't kidding. Its very unsatisfying. Its literally only proving 17 is the highest you can go, and really lacks an explanation, however does a pretty good job in proving 17. It does seem to be hinting that this has a use in other fields of mathematics, or at least it gives me that feeling. Does it have any other uses, and if so what are they?

  22. James, what if you had a cyclic number line that wraps around and there are not border constraints on 0 and 1? What would happen to the limit? Have they tried/published anything on that? Or is it too obvious that there won't be a limit?

  23. I don't get this.. the proof in this video was viable for x=0.46 and you said it can be generalized for any value of x.. but.. how?.. from my point of view, the proof in this video started from a particular premise and then drew a general answer..

  24. Drat.  I never got past 12; although, I'm now wondering if the reason my method stopped at 12 is related to the impossibility of 18.  I got that far by, at each stage, bisecting the empty plot.  So, .5 .25. .834 .125 etc.

  25. hi Jim, I recently heard of the Fast inverse square root magic number, the 0x5f3759df consant. have you ever heard of that? seems no one knows how it was "discovered".

  26. I totally knew this…yup…completely….okay, I didn't get anywhere, but I DID write out the problem symbolically before I got stuck, so yay for me! XD

  27. Does that number depend on the interval length? What if we were to take an interval, say [0, 2]? Would the maximum number of houses double (i.e. 34)? or is there a non-linear correlation? And, as it turns out, the number is not limited by the number of significant figures, which a lot of people assumed.

  28. This problem was not interesting enough for me to really pay attention and think it through, but your doing a video on it at the very least made a welcome distraction in times of boredom.

    TA JAMES.

  29. You should totally make more randomized response videos! and other polling tricks stuff.

  30. I was expecting an elegant, insightful, "eureka-like" solution. No need to say this was a let down. But thanks for sharing the problem anyway!

  31. big thanks for your videos. although i dont really understand everything u say, but i really enjoy watching it. please come to Lithuania and make a lecture about anything 😀 

  32. James, is it possible to generalize the proof for the complex plane bounded by -1 < x < 1, -i < y < i  ?

  33. 1st I thought that 9 was the limit, just by playing with the game almost randomly. Than, by luck I did 10… and never repeated it again, but I got hooked.
    So, instead of using the game I decided to do it my way… I am now at 14 houses. I was wondering though if this would keep forever despite I was feeling things were getting harder.
    Therefore I decided to watch this video and I am glad I did b/c now I know I am 3 houses from the limit, and I'll try to get there. It was/is a fun challenge!
    Nice proof by the way.

  34. How is a house on the boundary of a plot defined? Is it considered to be on the preceding or the following plot, or is it not allowed to be on the boundary? And if you define it to be on either of the plots, does this mean that either the first or the last plot is actually bigger? Or is 0 defined to be on the last plot (1 to be on the first plot respectively)?

  35. nice! I am a total failure, since i only got up to 10 houses… I was trying messing with the numbers and the fractions… thanks for the solution, thanks for sharing your knowledge with us.

  36. I wonder if this has any real world applications? I'll have to look into that. I find it amazing that it isn't infinite, but I am not so surprised its limit is a prime number. Finding the solution seems very recursive, thus could be a nice problem for a computer to solve.

  37. Very interesting, thanks for the puzzle! After thinking about it for a bit after you posted it, it seemed likely to me that a limit existed. When you first think of it more naively as just dividing up the number line into x equally sized quadrants it's obvious that that can be done indefinitely. But the restriction that you have to lay the points down in order and divide up the space as you go, you start to realize this actually puts huge restraints on the problem and it's actually easy to find yourself stuck unable to divide things up further. What is NOT obvious at all is that there isn't some "perfect" way to do this so that you don't get stuck. Or why, as you state, the limit should be a seemingly arbitrary number like 17, given the simple rule set. I'm assuming the same result can be extended to any arbitrary contiguous subset of the real number line?

  38. Would be nice to do an example with an actual size for the houses and not just a dimensionless point. This might have practical value for town planner…

  39. You're finally back!!!!!! Where in gods name have you been all my life??!!

  40. You're finally back!!!!!! Where in gods name have you been all my life??!!

  41. Fascinating!  Thank you for your clear and compelling explanation.

  42. What happens if you try to generalize the problem? for some fixed n, is there an infinite sequence of points in the closed unit ball in R^n such that for all k, the first k terms in the sequence are separated by neighborhoods of radius 1/k? what if you change to some other topology? are there any known sufficient conditions you can impose on your space such that infinite sequence of this kind will exist?

    Normally I would try to figure it out myself. Unfortunately these questions are most likely out of my league.

  43. I really enjoy it when you upload a brainteaser like this, it always keeps me busy for at least 3 hours, very entertaining.
    I wish you'd upload more, but it's allright; it's your channel, i wouldn't want you making content against your will either.
    Once again great video, looking forward to the next.

  44. Can you do the problem where you take a line segment [0, 1], make two cuts on the line according to a uniform distribution, and then determine if the three pieces will form a triangle

  45. Does this imply an optimax of 17 levels for tree structures generally?

  46. James, is anything known about the 2-D version of this problem where the first 4 points need to be in different quadrants, the first 9 in different ninths, etc.? Does that also have a finite maximum?

  47. Can you explain the proof of non-existence of greco-latin squares of order 6?

  48. I pondered the problem for a bit, and didn't think I'd be able to come up w/ any analytic solution, so I took the brute force approach and wrote a script to do interval searches for solutions.  It manage to find a 17 point solution in about a minute and a half — though it took me rather longer to write and debug the script. 🙂  This should be the "sequentially earliest" 17-point solution:

       #1 [  0/1 ,  1/17 ) 0.029412
       #2 [  7/13,  6/11 ) 0.541958
       #3 [ 11/13,  6/7  ) 0.851648
       #4 [  4/15,  3/11 ) 0.269697
       #5 [ 12/17,  5/7  ) 0.710084
       #6 [  5/12,  3/7  ) 0.422619
       #7 [ 12/13, 13/14 ) 0.925824
       #8 [  2/15,  1/7  ) 0.138095
       #9 [  8/13,  5/8  ) 0.620192
      #10 [  1/3 ,  6/17 ) 0.343137
      #11 [ 10/13, 11/14 ) 0.777473
      #12 [  1/5 ,  3/14 ) 0.207143
      #13 [  8/17,  1/2  ) 0.485294
      #14 [ 16/17,  1/1  ) 0.970588
      #15 [  1/15,  2/17 ) 0.092157
      #16 [ 11/17, 11/16 ) 0.667279
      #17 [  6/17,  7/17 ) 0.382353

  49. I just kept trying to work backwards (starting at the last house) and find an algorithm that worked… I assumed if I could find a rule that let you work backwards from some final number of steps, n, I could get some insight that showed you could "start" from infinity and work your way back. I even made a different but equivalent game of starting from http://puu.sh/7U5BO.png and going like so http://puu.sh/7U5yS.png
    My intuition is that this is really something rooted in chaos theory… It really just seemed unpredictable which choices lead to dead ends and which ended in a solution, especially since nothing that stayed symmetrical around the 1/2 mark could make it to a solution. I'd love to see how it behaves if you relax the constraints a bit; maybe something like expand each allowed interval at each step by some fixed percent and let them overlap (ex. each by 10%; 1st step: 0-1, 2nd step: 0-.55 and .45-1, 3rd step: 0-.3666… and .3-.7 and .6333…-1, etc)

  50. It doesn't look like you take into account that you gave us the free point 1. If you consider that, the bound could potentially increase by more than 1 given that the order of points matters, right?

  51. So mind-boggling. And the proof (along with starting from 9th step – cause why not make things even more seemingly arbitrary) just makes you feel more confused.
    But what's funny is that upon hearing the problem, I thought to myself "Sounds like Lwów school. I'm guessing… Steinhaus?". And yes it is 😀

  52. I see that the max number of houses for no more than 1 house is 17.  What if the max tolerance was 2 houses?  What would the absolute limit be then? Continue this thought past that, is there even a max limit that no matter the max tolerance of houses chosen, you can't go above a certain number of plots?

  53. uhh I graduated with a mathematics degree and I usually cannot solve your puzzles.

  54. What if the boarders were not uniform in shape but all even in size? What is the highest division you would be able to get?

  55. Using a computer, I've calculated the number of ways to arrange the houses for every possible number of plots. I consider a unique arrangement as a unique set of house number and plot number combinations (5th house ends up in the 17th plot etc.).
    That's what I've got:
    1 – 1
    2 – 2
    3 – 6
    4 – 16
    5 – 64
    6 – 128
    7 – 512
    8 – 1024
    9 – 2624
    10 – 3968
    11 – 11392
    12 – 7168
    13 – 17920
    14 – 11776
    15 – 8064
    16 – 4608
    17 – 1536

    It doesn't seem that follows any particular pattern, but you can notice some interesting behaviors here:

    1. The number of combinations goes up first, but then decreases as the number of plots gets closer to 17
    2. From 4 to 8, the combinations number follows the powers of 2 patters with some gaps
    3..May be the most interesting part is the drop at 12 plots.
     

  56. Maybe the limit 17 has something to do… with prime numbers?

  57. But hey! This means that each of the houses could be decorated with one of the the ONLY 17 possible wallpaper patterns. Can you find the link ! ?

  58. Jim, I hope you still read comments here, but I am confused. I came across this video and had some fun with puzzle on my own getting 12 points. However when I saw the solution video, I entered the solution you showed in and for some reason I can only get 16 points. The moment I enter the 17th on your list, it fails. I am not sure why. Also, would this same rule apply to a total plot of greater length: say a 2 mile plot? http://imgur.com/E6BFsWe 

  59. How would this get extended to 2 dimensions? In reality the houses are in 2 dimensional fields, so you can always cut up the tracts of lands indefinitely.

  60. James, what if we used the  dozenal system? A line from 0 to E (El).. or 0 to 1.2… what would be the longest sequence?

    Base 12 – Numberphile

  61. 17 is also the lowest number of clues given in a Sudoko that yields a unique solution

  62. Your videos are excellent. I love it when things have limits. Would you be making on on the  Farey Seq.? It does look pretty interesting.

  63. What's great about this is that this small problem/solution set is the basis for all limit mathematics!  That's the first time I was able to see the lower limit of limit math explained so well!

  64. I got to 12 points by placing each point exactly in the middle of the open plot… maybe a reason for that?

  65. Interesting. I'd played with it enough to convince myself that there was a limit. I was using a spreadsheet to divide things into intervals, branching where there were different possible choices. It gets hard after 10 or 11 points.  The most frustrating thing is that this sequence looks so promising: 0,1, 1/2, 1/4, 3/4, 3/8, 5/8, 1/8, 7/8, 7/16. (Looks very nice in binary, too.) But then, at the next point, which you'd think would be some other odd sixteenth, it fails.

    Fractions are like primes, in that where they are and the patterns they make are of course completely determined, but still not always easily predictable or easy to grasp or see.

  66. I got to 13 before watching this video:
    0, 1, .5, .27, .7, .417, .8, .179, .611, .35, .864, .125, .654

  67. yes but the amount of numbers between any 2 integers is infinite because any decimal you can think of I can think of one more bigger or smaller or more precise, therefore there is an infinite number of decimals available in this problem, so that also means there is an infinite number of fractions that equal said decimals thus making the problem have infinite solutions. But thats just my idea on it.

  68. Hey man!
    I recently saw your channel. I always thought you were numberphile! :O
    Keep it up man! Would be great to see more of your videos 🙂
    Very interesting, even though I dont study maths, but informatics

  69. It worth to mention that If you allow point on the exact border of plots to be assigned to either left or right plot (e.g. point at 0.5 to serve 0 – 0.5 plot at 2 points stage then serve 0.5 – 0.75 at 4 points stage) then you can place up to 23 points (houses).

  70. is there a f(x) that when n is imputed it generates a sequence of numbers that satisfies the 17 houses solution? I thought for sure that f(x) = (phi * n) % 1 would do it but to no avail f(x) =( n * golden angle/360) % 1 didn't work either.

  71. what happen if you skip ONLY the 18 partition? You go to 19 and so on… (?)

Leave a Reply

Your email address will not be published. Required fields are marked *