# 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

1. Mike Kotsch

Thanks for bending my brain once more. Really inspiring stuff.

2. Gustavo Lamonica

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 🙂

3. Kain Yusanagi

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

4. James Burke

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

5. Ben Grund

Hah wow

6. palmomki

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?

7. Small Fry

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

8. James Burke

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)?

9. Grinsekotze

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.

10. Angelina Lee

00:40 you need a hair cut Jim! LOL

11. Bob Spitfire

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 ¬.¬

12. James Burke

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

13. MetalMeerkat314

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 😛

14. Djorgal

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.

15. Duco Mortem

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?

16. LynneSkysong

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.

17. Phlip

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.

18. 777greenday777

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

19. J H

What happens to the MAX when you add a decimal place?

20. J H

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.

21. Elliott Collins

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.

22. user4931092322

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

23. TyYann

I have been: you're welcome.

24. MorRobots

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?

25. Aescula Janus

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"

26. TheDrB0B

Excelent video! Do you use this kind of material for your students?

27. Justin Shahriyar

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?

28. ivarbug

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?﻿

29. Lightn0x

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..

30. Parlyne

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.

31. Maxim Frey

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".

32. Onjit

Haha! Called it!

33. IceMetalPunk

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

34. Ivan Pryakhin

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.

35. JustOneAsbesto

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.

Very cool 🙂

37. Hugo Gomes

Of course I have been! You're welcome 😉

38. geographymathmaster

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

39. Leonardo Donelli

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!

40. Ham Slice

Omg 17! That's my conspiracy number. It's always 17

41. Ergo Proxy

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 😀

42. BlokenArrow

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

43. culwin

I couldn't even get past 2!

44. justpaulo

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.

45. 23PowerL

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)?

46. Jacob Shepley

and….if you have been, thanks for reading

47. Spiguel

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.

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.

49. Locut0s

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?

50. Galakyllz

I love these videos. Thanks for giving me something to think about.

51. garou108

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…

52. Evan McCormick

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

53. Evan McCormick

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

54. bengski68

Wonderful puzzle, wonderful explanation.  Thank you!

55. jonnie thumbs

I reckon the local fence builder retired early….. 🙂

56. David Oranchak

Fascinating!  Thank you for your clear and compelling explanation.

57. HyperanimateForm

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.

58. althair2

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.

59. James Pedid

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

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

61. Careless Labs

Local council would never give permission for 17 new houses!

62. Charles Greathouse

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?

63. msolec2000

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

64. ThreeXcore

You are no fool !

65. William R Somsky

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

66. Martin Lane

We live in a mysterious world

67. LydianLights

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)

68. Dlpizz

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?

69. Jan Rzymkowski

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 😀

70. farstar31

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?

71. derek du

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

72. watrick144

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?

73. simon paulsen

FUUUUUUUUUU got 16 :'C

74. MegaLokopo

it can go on for an infinite number of houses. your proof is wrong.

75. Yogev P.

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.

76. jpheitman

Bloody Farey.

77. Anonymous71475

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

78. 16elcl

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 ! ?

79. jesusthroughmary

Does this have anything to do with the 17-hint Sudoku proof?

80. Andrew Smith

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

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.

82. Rodrigo Limão

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

83. G1

does it have anything to do with Gauss' inscribed 17 sided polygon?

84. Kelvin Tang

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

85. TLH 496

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.

86. billy ruiz

🙁 this is harder than solving enigma ,' i got 10 btw :p hahahhahah

87. Mr Autistic

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!

88. Puzzle1cisuM90

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

89. Angi Long

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.

90. dolfin rule

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

91. Drew M-R

I got 11

92. Devin Flener

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.

93. xnick

"17 is reeeeally odd" 😉

94. Rankhole

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

95. rasowa

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).

96. Luke Costello

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.

97. Siro

how many points can you put in there if it was a square?

98. Littlemanz Jordan

60.001 views, I broke the beautiful number

99. Donald Sayers

17 is not the answer to any sensible problem!

100. Drestanto

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