# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Message body

 Emoticons View more Emoticons
 [quote="ralphmerridew"]Quick discussion of Fermat-Pell equation: For given N, solve x^2 - Ny^2 = +- 1 Say that a number (a + b*sqrt(N)), where [i]a[/i] and [i]b[/i] are integers, determines a solution to the equation iff a^2 - Nb^2 = +- 1. Note that if [i]p[/i] and [i]q[/i] determine solutions, then so does [i]pq[/i]: (p1 + p2 sqrt(N)) (q1 + q2 sqrt(N)) = (p1 q1 + N p2 q2) + (p1 q2 + p2 q1) sqrt (N) = (p1 q1 + N p2 q2)^2 - N (p1 q2 + p2 q1) ^ 2 = (p1^2 q1^2 + 2 N p1 p2 q1 q2 + N^2 p2^2 q2^2) - N (p1^2 q2^2 + 2 p1 p2 q1 q2 + p2^2 q1^2) = p1^2 q1^2 - N p1^2 q2^2 - N p2^2 q1^2 + N^2 p2^2 q2^2 = (p1^2 - N p2^2) (q1^2 - N q2^2) = (+- 1)*(+- 1) = +- 1 Next, if [i]p[/i] determines a solution, so does [i]1/p[/i]. (similar). If a nontrivial solution exists, define the generator as the smallest [i]g[/i] > 1 such that g determines a solution. (skipping over that there is unique) Consider any number [i]p[/i], p > 1, that determines a solution. Choose n as the integer such that g^n <= p < g^(n+1). g^n, 1/g^n, p/g^n determine solutions (above) g^n <= p < g^(n+1) implies 1 <= p/g^n < g. By definition of g, the only way that is possible is if p/g^n = 1, or p = g^n. Similarly, all solutions determined by a p < 1 are of form p^(-n). Now, finding that generator (if it exists), can be a bit tricky...[/quote]
Options
HTML is OFF
BBCode is ON
Smilies are ON
 Disable BBCode in this post Disable Smilies in this post

 All times are GMT
 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
 Topic review
Author Message
ralphmerridew
Posted: Tue Nov 15, 2011 8:24 pm    Post subject: 1

Using the generator method, you can quickly find

1 of 1
6 of 8
35 of 49
204 of 288
1189 of 1681
6930 of 9800
40391 of 57121
235416 of 332928
1372105 of 1940449
7997214 of 11309768
46611179 of 65918161
271669860 of 384199200
1583407981 of 2239277041
9228778026 of 13051463048
53789260175 of 76069501249
313506783024 of 443365544448
1827251437969 of 2584123765441
10650001844790 of 15061377048200
...
Chuck
Posted: Tue Nov 15, 2011 5:00 pm    Post subject: 0

For four digit house numbers, house 1189 out of 1681 qualifies.
ralphmerridew
Posted: Tue Nov 15, 2011 1:54 am    Post subject: -1

Quick discussion of Fermat-Pell equation:
For given N, solve x^2 - Ny^2 = +- 1

Say that a number (a + b*sqrt(N)), where a and b are integers, determines a solution to the equation iff a^2 - Nb^2 = +- 1.

Note that if p and q determine solutions, then so does pq:
(p1 + p2 sqrt(N)) (q1 + q2 sqrt(N)) = (p1 q1 + N p2 q2) + (p1 q2 + p2 q1) sqrt (N)
= (p1 q1 + N p2 q2)^2 - N (p1 q2 + p2 q1) ^ 2
= (p1^2 q1^2 + 2 N p1 p2 q1 q2 + N^2 p2^2 q2^2) - N (p1^2 q2^2 + 2 p1 p2 q1 q2 + p2^2 q1^2)
= p1^2 q1^2 - N p1^2 q2^2 - N p2^2 q1^2 + N^2 p2^2 q2^2
= (p1^2 - N p2^2) (q1^2 - N q2^2)
= (+- 1)*(+- 1)
= +- 1

Next, if p determines a solution, so does 1/p. (similar).

If a nontrivial solution exists, define the generator as the smallest g > 1 such that g determines a solution. (skipping over that there is unique)

Consider any number p, p > 1, that determines a solution. Choose n as the integer such that g^n <= p < g^(n+1).
g^n, 1/g^n, p/g^n determine solutions (above)
g^n <= p < g^(n+1) implies 1 <= p/g^n < g. By definition of g, the only way that is possible is if p/g^n = 1, or p = g^n.

Similarly, all solutions determined by a p < 1 are of form p^(-n).

Now, finding that generator (if it exists), can be a bit tricky...
Zag
Posted: Tue Nov 15, 2011 1:28 am    Post subject: -2

I knew GL would have a better way of solving it than I. Nicely done, rm.

m == my house number
n == highest house number
Using the approach that the sum from x to y is the average of x and y times the difference
Sum of numbers less than my house == m(m-1) /2
Sum of numbers greater than my house == (m+1 + n)(n-m) /2

Set these equal to each other and do some algebra

m(m-1) = (m+1 + n)(n-m) = mn + n + nn - mm - m - mn

The mn terms conveniently fall away, leaving

mm - m = nn + n - mm - m
2mm = nn + n
mm = n(n + 1) / 2

At this point I was quite surprised that it simplified so that m squared was another triangular number, but I guess, looking at rm's approach, it was kind of obvious that it would. I didn't know anything about Fermat-Pell (and I still don't understand it), so I quit at that point and used a spreadsheet.
ralphmerridew
Posted: Tue Nov 15, 2011 12:18 am    Post subject: -3

Doing it by hand:

m == my house number
n == highest house number
Sum of numbers less than your house == m(m-1)/2
Sum of all numbers == n(n+1)/2

(Sum of all numbers less than mine) + mine + (sum of all greater than mine) = sum of all
m(m-1)/2 + m + m(m-1)/2 = n(n+1)/2
m(m-1) + 2m + m(m-1) = n(n+1)
mm-m + 2m + mm - m = nn + n
2mm = nn + n
8mm = 4nn + 4n
8mm + 1 = 4nn + 4n + 1
2(2m)^2 + 1 = (2n+1)^2
(2n+1)^2 - 2(2m)^2 = 1
Set x = (2n+1), y = 2m
xx - 2yy = 1.
This is a Fermat-Pell equation. Generator is 3 + 2sqrt(2). All solutions are of form x + ysqrt(2) = (3 + 2sqrt(2))^k.

3 + 2 sqrt 2
17 + 12 sqrt 2
577 + 408 sqrt 2

m = y/2 = 204
n = (x-1)/2 = 288

Chuck
Posted: Mon Nov 14, 2011 11:59 pm    Post subject: -4

Yes, there is a solution. But a computer search made it too easy.
Zag
Posted: Mon Nov 14, 2011 10:57 pm    Post subject: -5

A co-worker told me this morning that he was cleaning out his father's attic and came across a very old book of puzzles. He had flipped through it and there was one he particularly liked, and I had never heard it before.

I worked on it through the two meetings I had this morning, and a couple of times heard, "Well, what do you think, Zag?" and had to have the question repeated. I did get it, though

-----------------------

I live on a street on which the houses are numbered from 1 up, with none missing. I noticed recently that the sum of all the house numbers less than mine exactly equals the sum of all the house numbers greater than mine. My house number has three digits. What is it?