Quellenangaben
In Cambridge hab ich eine schöne Serie von mjouk entdeckt. Diese Serie wurde inspiriert durch Project Euler.
Allgemeine Bemerkungen
Um die Project Euler Rätsel zu lösen, muss man vermutlich ein kleines Computerprogramm schreiben. Ich habe es mit VBA in Excel gemacht.
Die Rätsel
Nord
Gitterpfade
Wenn man in einem 2x2 Raster an der linken oberen Ecke startet und immer nur rechts oder nach unten gehen kann, gibt es genau 6 Möglichkeiten, die rechte untere Ecke zu erreichen.
Wenn man das mit einem 1000x1000 Raster wiederholt, wird man wesentlich mehr Möglichkeiten finden. Die Zahl beginnt mit 204 und endet mit 120. Die mittleren 3 Ziffern sind 851.
Um die Nordkoordinate zu ermitteln, errechne die Anzahl der Möglichkeiten in einem 2074x2074 Raster. Die Koordinate ist dann N50° 09.X, wobei X die mittleren 3 Zahlen der Anzahl plus 4 ist.
Ost
Wir zählen Sonntage, Montage, ...
Dreißig Tage hat September,
April, Juni und November.
Februar hat achtundzwanzig,
nur im Schaltjahr neunundzwanzig.
Alle andere ohne Frage
haben einunddreißig Tage.
Du musst auch wissen, dass der 01. Januar 1900 ein Montag war. Jedes Jahr, dass durch 4 teilbar ist, ist ein Schaltjahr, außer es handelt sich um ein Jahrhundert. Ein Jahr, dass durch 400 teilbar ist, ist jedoch wieder ein Schaltjahr.
Das bedeutet, dass 400 Jahre 146097 Tage haben, was genau 20871 Wochen entspricht. Dieses Ergebnis legt nahe, dass sich der Kalender nach 400 Jahren wiederholt. Damit wäre der 01. Januar 2300 wieder ein Montag.
Um die Ostkoordinate zu ermitteln, musst du zählen, wie oft etwas innerhalb eines 400 Jahre-Zyklus auf einen bestimmten Wochentag fällt. Dabei gilt:
a(d) Der 31. eines Monats fällt auf den Wochentag d.
b(d) Der 13. eines Monats fällt auf den Wochentag d.
c(d) Eulers Geburtstag fällt auf den Wochentag d.
e(d) Der 29. Februar fällt auf den Wochentag d.
f(d) Der 30. eines Montas fällt auf den Wochentag d.
Zum Beispiel gilt c(FR)=58. Das bedeutet, dass von den 400 Geburtstagen, die Euler erlebt hätte, hätte er zwischen 1900 und 2300 gelebt, 58 auf einen Freitag fallen.
Um die Ostkoordinate zu erhalten, berechne nun:
[a(SA)+a(FR)+b(FR)+b(SA)+f(DI)]*4*[c(Mo)+e(Mo)]+[c(SA)+c(MO)]*e(MO)*e(MO)-[f(DI)-11]/3
Acknowledgements
In Cambridge I found a nice series by mjouk. It was inspired by Project Euler.
General notes
To solve Project Euler puzzles, you will probably have to write a computer program.
The Puzzles
North
Lattice Paths
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.
You can assume that the coordinates of this geocache are N 50 09.xxx.
If you repeat the calculation above on a 1000×1000 grid, you'll find many more paths. This number begins 204, ends 120, and the middle three digits are 851.
To find the missing numbers calculate how many similar paths there are in a 2074×2074 grid, extract the middle three digits of this big number and add 4.
East
Counting Sundays, Mondays, …
Thirty days has September,
April, June and November.
All the rest have thirty-one,
Saving February alone,
Which has twenty-eight, rain or shine.
And on leap years, twenty-nine.
You are also told that 1 Jan 1900 was a Monday, and that a leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
Taken together this means that there are 146,097 days in 400 years, which corresponds to exactly 20,871 weeks. This result implies that the calendar repeats after 400 years, so 1 Jan 2300 will be a Monday too.
Solving this puzzle involves counting how often things fall on particular days of the week during one 400 year cycle. Specifically let's introduce the following counts:
| a(d) |
The 31st of a month falls on day d. |
| b(d) |
The 13th of a month falls on day d. |
| c(d) |
Euler's birthday falls on day d. |
| e(d) |
The 29th of February falls on day d. |
| f(d) |
The 30th of a month falls on day d. |
For example, you will find that c(Fri) = 58, which means that of the 400 birthdays Euler would have enjoyed had he lived between 1900 and 2300, 58 of them fall on a Friday.
To find the eastern coordinate calculate:
[a(Sat)+a(Fri)+b(Fri)+b(Sat)+f(Tue)]*4*[c(Mo)+e(Mo)]+[c(Sat)+c(Mon)]*e(Mon)*e(Mon)-[f(Tue)-11]/3