Das wichtigste natürlich wie immer zuerst: Die Kopfkoordinaten sind natürlich rein fiktiv, hier kann man keinen Cache finden.
In der Gemeinde Brechen soll ein großes Geocacher-Festival stattfinden. Das Organisationsteam will natürlich viele Cacher ins heimische Gebiet locken und legt extra ein paar schöne Tradi-Runden aus. Da einer der Organisatoren ein regelrechter Statistik-Cacher ist, will er rund um und in der Großgemeinde einen (irrsinnigen) Powertrail aus 1000 Caches legen. Dafür hatte er sich schon vor einiger Zeit genauso viele PETlinge besorgt und diese mit den zugehörigen Logbüchern ausgestattet. Die Dosen und Logbücher hatte der Cacher auch schon beschriftet, sodass auf jeder Dose und dem dazugehörigen Logbuch der Cachename inkl. der dazugehörigen Nummer steht (also z.B. „Mini-Serie in und um Brechen #573“). Die PETlinge hatte er auch schon schön sortiert in einer Kiste, sodass er beim Auslegen nur noch zugreifen musste. Blöderweise ist ihm jetzt diese Kiste auf den Boden gefallen und viele der Dosen sind vollkommen durcheinander. Den Powertrail einfach fallen zu lassen kommt für den Cacher nicht in Frage, also fängt er an die PETlinge wieder zu sortieren. Dabei geht er wie folgt vor:
Zuerst legt er alle Dosen von links nach rechts auf den Tisch. Dabei sind sie natürlich noch völlig durcheinander. Gehen wir in diesem Beispiel erstmal davon aus, dass es nur fünf PETlinge sind, die folgendermaßen auf dem Tisch liegen:
Wir suchen nun von links nach rechts den PETling mit der kleinsten Zahl. Der Cacher schaut sich den PETling ganz links an. Da bis zu diesem Zeitpunkt erst eine Dose betrachtet wurde, ist die Zahl der ersten Dose natürlich auch die kleinste Zahl, die der Cacher bis hierhin gefunden hat. Er merkt sich die Position 1 also als kleinste Zahl. Jetzt begutachtet er die Dose, die eine Position weiter rechts liegt. Er vergleicht diese mit dem Inhalt der Dose, die bis hierhin die kleinste Zahl enthält. Da die 2 kleiner ist als die 4, notiert sich der Cacher die Position 2 als kleinste Zahl. Nun wird der PETling weiter rechts angeschaut. Er trägt die Nummer 5. Vergleicht man die 5 mit der bis hierhin niedrigsten Zahl 2, so stellt man fest, dass es kein neues Minimum gibt. Also geht es weiter zur nächsten Dose. Hier findet der Cacher eine 1. Verglichen mit dem aktuellen Minimum 2 ist die 1 natürlich kleiner. Der Cacher merkt sich also die Position der Dose 1 (in diesem Fall die 4. Position). Nun betrachtet er noch den nächsten und letzten PETling. Er trägt die Nummer 3. Da die 3 größer als die 1 ist, kann hier kein neues Minimum gefunden werden. Nun ist der Cacher am Ende der Reihe angekommen und weiß, dass an Position 4 die kleinste Zahl steht. Er geht nun hin und vertauscht den PETling an Position 4 mit der Dose an Position 1. Das sieht wie folgt aus:
Nach diesem ersten Durchlauf ist sicher, dass der PETling mit der kleinsten Zahl ganz links steht. Nun vollzieht der Cacher dieses Verfahren erneut, beginnt aber sinnvollerweise erst bei der Position 2, da an der ersten Position ja schon die kleinste Zahl steht. Er vergleicht, ob die 5 kleiner als die 2 ist, dann ob die 4 kleiner als die 2 ist, und letztendlich, ob die 3 kleiner als die 2 ist. Da in diesem Fall aber kein Cache eine kleinere Nummer hat, als der Cache an Position 2, wird hier nichts vertauscht. Man weiß aber nun, dass die Dosen an Position 1 und 2 die kleinsten Nummern haben und aufsteigend sortiert sind:
Nun geht das Spiel erneut los, allerdings natürlich ab Position 3: Ist die 4 kleiner als die 5? In der Tat, also merkt man sich die Position 4 als kleinste Zahl. Weiter geht’s: Ist die 3 kleiner als das aktuelle Minimum 4? Auch das stimmt, also merkt man sich die Position 5 als kleinste Zahl. Da man nun wieder um Ende angekommen ist, wird die Position 5 mit der Position 3 getauscht:
Und nochmal: Man startet an Position 4, da 1 bis 3 schon richtig aufsteigend sortiert sind. Jetzt wird wieder verglichen: Ist die 5 kleiner als die 4? Natürlich nicht, also wird nichts getauscht. Da nun nur noch eine Dose an Position 5 übrig bleibt, muss diese selbstverständlich eine größere Nummer haben, als alle anderen Dosen, die links von ihr liegen. Hier kann also auch nichts mehr verglichen oder vertauscht werden.
Wunderbar – der Cacher hat alle PETlinge korrekt sortiert :-) Bei diesem Verfahren wurden insgesamt 10 Vergleiche durchgeführt und 2 Vertauschungen.
Der Statistik-Cacher hätte sich an dieser Stelle echt freuen können, wenn er tatsächlich nur eine Mini-Serie mit 5 Dosen auslegen wollte. Er hat aber insgesamt 1000 PETlinge! Durch seinen kleinen Unfall ist Unordnung in die Sache gekommen. Die Dosen liegen nun folgendermaßen vor dem Cacher:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 822, 450, 624, 122, 144, 247, 976, 803, 242, 438, 340, 250, 270, 374, 383, 605, 590, 571, 367, 330, 993, 319, 585, 865, 926, 197, 673, 727, 574, 168, 572, 743, 1000, 159, 423, 790, 665, 736, 193, 816, 869, 153, 542, 689, 884, 745, 989, 813, 468, 744, 352, 889, 485, 175, 881, 979, 821, 323, 616, 389, 298, 375, 283, 556, 569, 967, 629, 713, 702, 971, 183, 842, 230, 843, 296, 759, 312, 315, 925, 880, 581, 915, 652, 687, 437, 598, 458, 635, 287, 320, 506, 617, 362, 466, 717, 439, 678, 373, 623, 784, 804, 278, 397, 207, 773, 403, 218, 414, 226, 681, 327, 645, 706, 820, 649, 396, 432, 772, 526, 333, 173, 747, 902, 540, 463, 351, 524, 753, 789, 467, 483, 261, 530, 391, 244, 907, 877, 501, 292, 399, 900, 253, 544, 553, 966, 917, 754, 174, 344, 136, 798, 356, 796, 625, 701, 631, 126, 448, 811, 162, 782, 953, 408, 275, 791, 593, 726, 560, 163, 361, 237, 484, 415, 282, 879, 555, 192, 722, 920, 297, 632, 557, 964, 895, 529, 823, 893, 308, 614, 547, 668, 746, 965, 970, 862, 139, 503, 299, 234, 943, 477, 996, 734, 418, 406, 723, 761, 871, 732, 551, 416, 479, 700, 863, 243, 562, 799, 422, 272, 213, 514, 897, 502, 219, 690, 123, 733, 851, 850, 309, 471, 712, 819, 788, 675, 143, 924, 956, 930, 441, 921, 519, 859, 888, 792, 494, 716, 954, 357, 945, 370, 766, 891, 224, 525, 724, 167, 584, 817, 548, 276, 644, 583, 646, 935, 767, 856, 922, 305, 252, 919, 401, 853, 937, 674, 639, 260, 273, 987, 185, 128, 628, 968, 335, 184, 489, 227, 595, 962, 545, 328, 258, 388, 800, 212, 400, 148, 814, 324, 145, 941, 480, 588, 985, 214, 659, 615, 929, 848, 841, 570, 204, 535, 302, 240, 641, 933, 289, 657, 321, 636, 882, 977, 683, 342, 444, 497, 537, 131, 932, 515, 233, 912, 846, 453, 999, 304, 648, 587, 719, 958, 465, 424, 684, 656, 413, 861, 288, 825, 206, 794, 838, 923, 536, 827, 527, 462, 606, 721, 369, 225, 604, 246, 121, 762, 407, 660, 739, 679, 774, 951, 249, 265, 133, 992, 867, 711, 459, 125, 508, 500, 815, 695, 513, 199, 728, 662, 786, 368, 410, 749, 232, 840, 341, 436, 151, 688, 708, 973, 834, 969, 251, 775, 285, 696, 520, 512, 359, 768, 669, 828, 293, 160, 314, 460, 511, 178, 801, 504, 564, 518, 451, 974, 883, 829, 364, 181, 322, 395, 898, 129, 855, 349, 836, 903, 211, 157, 231, 200, 758, 908, 984, 878, 189, 972, 610, 130, 472, 149, 179, 640, 948, 201, 533, 909, 180, 667, 366, 326, 676, 155, 663, 457, 269, 983, 209, 132, 402, 936, 236, 534, 336, 405, 493, 182, 378, 931, 546, 844, 872, 577, 580, 661, 946, 594, 741, 452, 347, 345, 797, 618, 868, 196, 385, 266, 509, 955, 507, 481, 210, 826, 653, 284, 150, 141, 241, 715, 579, 894, 707, 217, 582, 621, 434, 750, 990, 417, 522, 832, 934, 694, 812, 905, 313, 637, 738, 152, 316, 190, 864, 573, 835, 146, 166, 995, 194, 280, 730, 505, 664, 655, 433, 412, 372, 140, 440, 549, 597, 763, 411, 254, 329, 238, 642, 290, 461, 771, 858, 714, 963, 704, 550, 949, 705, 857, 916, 360, 268, 499, 198, 404, 420, 756, 666, 510, 215, 824, 267, 777, 496, 303, 960, 780, 470, 446, 633, 176, 612, 939, 735, 355, 517, 698, 338, 409, 435, 839, 906, 576, 205, 478, 449, 630, 346, 860, 886, 447, 672, 691, 318, 473, 558, 575, 239, 430, 778, 137, 849, 392, 229, 602, 138, 235, 899, 870, 245, 600, 729, 975, 255, 307, 259, 216, 942, 650, 911, 779, 257, 331, 262, 950, 959, 256, 135, 228, 831, 300, 998, 488, 386, 765, 795, 626, 764, 988, 306, 454, 482, 847, 429, 978, 938, 940, 802, 742, 532, 222, 982, 543, 874, 127, 991, 892, 154, 622, 334, 521, 709, 837, 281, 873, 944, 913, 455, 445, 896, 539, 147, 456, 671, 177, 393, 770, 651, 866, 961, 807, 263, 295, 172, 634, 793, 692, 876, 442, 737, 854, 371, 286, 725, 538, 223, 498, 491, 748, 431, 578, 703, 808, 187, 740, 348, 757, 311, 685, 343, 427, 783, 464, 332, 910, 927, 487, 810, 443, 195, 591, 566, 686, 186, 358, 170, 317, 191, 875, 169, 476, 528, 833, 601, 279, 567, 523, 552, 890, 776, 752, 220, 613, 980, 720, 363, 421, 425, 350, 760, 377, 541, 337, 981, 755, 294, 264, 274, 599, 379, 208, 769, 380, 398, 202, 619, 928, 643, 918, 677, 291, 277, 390, 381, 310, 428, 134, 563, 171, 718, 561, 627, 699, 164, 947, 620, 607, 994, 188, 751, 120, 731, 710, 682, 609, 475, 852, 156, 486, 559, 419, 845, 904, 901, 957, 680, 997, 339, 124, 474, 142, 531, 221, 203, 492, 670, 568, 806, 830, 394, 165, 376, 248, 365, 787, 589, 952, 426, 693, 596, 611, 469, 608, 354, 654, 158, 697, 885, 325, 554, 382, 914, 161, 516, 603, 658, 818, 301, 785, 592, 271, 781, 565, 638, 384, 495, 887, 490, 805, 353, 986, 387, 809, 586, 647
Geht davon aus, dass der Cacher das oben gezeigte Verfahren verwendet. Die Frage ist nun: Wie viele Vergleiche und Vertauschungen werden in diesem Fall vorgenommen?
A sei die Anzahl der Vergleiche
B sei die Anzahl der Vertauschungen
Gesucht ist nun eine Lösungszahl, die ganz einfach berechnet werden kann:
Lösungszahl = A + B
Wenn ihr diese Zahl bei certitudes.org eingebt, erhaltet ihr die Koordinaten der Dose und könnt schon mal eins der tausend Verstecke aufsuchen :-)
Da es hier einen Bonus bei dieser Cacheserie gibt, notiert euch bitte die Bonuszahl, falls ihr auch noch diese Dose finden möchtet. Viel Spaß beim rätseln, rechnen, suchen und loggen! Es ist möglich diese Serie auch als Wanderung anzugehen - was ich übrigens auch empfehle. Die Wegstrecke beträgt etwa 5km. Benutzt dafür den angegebenen Parkplatz. Ich empfehle euch dabei die Caches in der Reihenfolge (Chaos 5, Chaos 1, Chaos 2, Chaos 4, Chaos 3 und Chaos Bonus) anzugehen.