| Autor |
Beitrag |
    
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Montag, den 05. August, 2002 - 17:02: | 
|
Beim britischen Geheimdienst wurden früher alle Agenten durch einen fünfstelligen Zahlencode identifiziert. James Bond hatte also in Wirklichkeit den Code 00007. Aus Sicherheitsgründen wurden nur Codes verwendet, die sich an mindestens zwei Stellen unterscheiden, ein einfacher Tippfehler hätte ja fatale Folgen gehabt! Und so war James Bond der einzige 0000-Agent, was auch immer die Filmleute behaupten mögen.
Aber wieviele solcher Codes gibt es denn genau?
|
clara
Unregistrierter Gast
| | Veröffentlicht am Dienstag, den 06. August, 2002 - 16:15: |
|
9999?
clara |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Dienstag, den 06. August, 2002 - 16:27: |
|
Hi clara, nein.
Wie bist du auf diese interessante Zahl gekommen?
sol@ti
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1291
Registriert: 07-2000
| | Veröffentlicht am Dienstag, den 06. August, 2002 - 17:30: |
|
Könnte man nicht sagen "es kommt drauf an"?
Aber, wie ich dich kenne, suchst du die größtmögliche Anzahl ;-) |
clara
Unregistrierter Gast
| | Veröffentlicht am Dienstag, den 06. August, 2002 - 17:48: |
|
Hi
dann muss ich noch etwas überlegen.
Ich kam durch Neunerschritte auf diese Zahl. Wenn man zu einer Zahl die nicht auf 0 endet, neun addiert ändern sich zwei Ziffern.
Auf jeden Fall werden es dann weniger als 9999 sein.
clara |
Onkel Murray (murray)
Erfahrenes Mitglied
Benutzername: murray
Nummer des Beitrags: 118
Registriert: 10-2001
| | Veröffentlicht am Dienstag, den 06. August, 2002 - 18:09: |
|
Ich finde das Clara garnicht so weit weg ist, oder gibt es da einen Haken (bei sol@ti gibt es immer einen)?
Also es gibt maximal 10^5 Kombinationen. Dabei müssen jetzt 2 Ziffern immer verschieden sein. Also sollte es reichen diejenigen Zahlen abzuziehen, bei denen alle Ziffern gleich sind, das sind 10.
Daraus folgt es gibt 9990 Kombinationen.
Murray |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Dienstag, den 06. August, 2002 - 18:36: |
|
Hallo!
@Zaph: Ja, danke für den Hinweis. Allerdings könnte man die Anzahl der Codes nur durch zusätzliche Bedingungen verkleinern. Wenn man prinzipiell alle fünfstelligen Ziffernkombinationen zulässt, gibt es zwar viele Auswahlmöglichkeiten, aber die Mächtigkeit der Menge aller Codezahlen ist eindeutig.
@clara: Du hast gute Argumente, aber ich muss dich enttäuschen. Es gibt mehr als 9999.
@Murray: Nach deiner Rechnung wären es 99990, das ist zuviel. Bei zwei Codezahlen dürfen höchstens drei Stellen übereinstimmen, z.B. bei PABCQ und XABCY muss P ungleich X und Q ungleich Y sein!
Viele Grüße
sol@ti
|
Onkel Murray (murray)
Erfahrenes Mitglied
Benutzername: murray
Nummer des Beitrags: 119
Registriert: 10-2001
| | Veröffentlicht am Dienstag, den 06. August, 2002 - 18:56: |
|
Achso, die haben sich nicht nur an einer Stelle, sondern an zwei Stellen unterschieden - gleich ein doppelter Fehler (erst der Tipfehler :-).
Also Kombinatorik ist auch nicht so mein Ding, aber ich versuchs nochmal:
Klar ist, das es maximal 10^5 sind. Wir müssen alle Kombinationen abziehen bei denen 4 Stellen gleich sind (da sind die, bei denen alle 5 Stellen gleich sind, schon dabei) - das sind 100*5 Stück.
Es bleiben als nur noch Kombinationen mit 2 oder 3 Stellen gleich, oder anders formuliert mit mindestens 2 Stellen verschieden, übrig.
Ergo gibt das 99500 Möglichkeiten.
Auf 100 * 5 komm ich, weil sich das theoretisch wie eine Kombination mit zwei Stellen an 5 verschiedenen Positionen verhält.
Bsp: 11114 oder 11141 oder 11411 u.s.w.
Murray
PS: Ich denke der Weg ist richtig, aber bei den 500 bin ich mir nicht sicher.
(Beitrag nachträglich am 06., August. 2002 von murray editiert) |
Thomas (johnnie_walker)
Fortgeschrittenes Mitglied
Benutzername: johnnie_walker
Nummer des Beitrags: 55
Registriert: 06-2002
| | Veröffentlicht am Dienstag, den 06. August, 2002 - 19:25: |
|
Hi Sol@ti,
ich trau mich dann doch noch mal
Es gibt jeweils 10 Klassen, in denen eine Zahl doppelt vorkommt, nämlich die Klassen (0,0)-(9,9)
In jeder dieser Klassen dürfen neben den genannten Zahlen nur die anderen Ziffern vorkommen, also ein Ziehen ohne Zurücklegen.
Anzahl verschiedene Ziffern pro Klasse 9*8*7
Jede Klasse kann ich dann 5fach permutieren,
9*8*7*5!=60480
10 Klassen, also 604800 Möglichkeiten.
Gruß
Thomas |
Thomas (johnnie_walker)
Fortgeschrittenes Mitglied
Benutzername: johnnie_walker
Nummer des Beitrags: 56
Registriert: 06-2002
| | Veröffentlicht am Dienstag, den 06. August, 2002 - 20:29: |
|
Habe vergessen, daß
00123 ja eine Permutation von 00123 ist.
Versuche es noch zu retten :
Ich muß in jeder Klasse noch jeweils 9*8*7 abziehen, also
9*8*7*5!-(9*8*7) = 59976,
also 599760 Möglichkeiten |
Thomas (johnnie_walker)
Fortgeschrittenes Mitglied
Benutzername: johnnie_walker
Nummer des Beitrags: 57
Registriert: 06-2002
| | Veröffentlicht am Dienstag, den 06. August, 2002 - 20:52: |
|
Aaah !
Du bringst mich mit Deinen Rätseln um den Verstand !
neuer Versuch :
10 Klassen, 9*8*7 Möglichkeiten, habe da schon die Permutationen der letzten 3 Ziffern mit berücksichtigt, also muß bei jeder folgenden Permutation eine 0 ihren Platz verändern,jede 0 hat 3 Möglichkeiten auf eine der letzten drei Stellen zu gelangen,also
10*9*8*7*6=30240
wenigstens werdens immer weniger ...
Thomas
(Beitrag nachträglich am 06., August. 2002 von johnnie_walker editiert)
(Beitrag nachträglich am 06., August. 2002 von johnnie_walker editiert) |
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 74
Registriert: 03-2001
| | Veröffentlicht am Mittwoch, den 07. August, 2002 - 00:38: |
|
hi sol@ti.
es gibt genau 10000 gültige codes.
überlegung: man geht der reihe nach vor!
der erste code ist lt. aufgabe 00007. der nächste kann nicht von der form 0000* sein, also muß also 0001* lauten.
(so sieht man bereits, daß es maximal 10000 sein können. da du weiter oben angemerkt hast, daß es mehr als 9999 sind, wäre man sogar schon fertig.)
die letzte stelle kann hierbei alles sein, nur keine 7. nehmen wir an, es ist eine 8. der nächste muß nun mit 0002 beginnen, die letzte ziffer kann weder eine 7 noch eine 8 sein, nehmen wir an, es ist eine 9 usw. um zum nächsten code zu gelangen, erhöhen wir nun die letzte und die vorletzte ziffer jeweils um 1.
numerieren wir die codes durch, beginnend mit code(0).
code(0) = 00007
code(1) = 00018
code(2) = 00029
code(3) = 00030
code(4) = 00041
code(5) = 00052
code(6) = 00063
code(7) = 00074
code(8) = 00085
code(9) = 00096
code(10) muß von der form 0010* sein, die letzte ziffer darf aber keine 7 sein, wegen code(0)=00007. also erhöhen wir alle 10 codes die letzte ziffer zusätzlich um 1.
code(10) = 00108
code(11) = 00119
...
code(18) = 00186
code(19) = 00197
code(20) = 00209
code(21) = 00210
...
dasselbe tritt alle 100 bzw. 1000 codes auf, an diesen stellen wird die letzte ziffer nochmals jeweils um 1 erhöht.
code(99) = 00995
code(100) = 01008
...
code(9999) = 99993
allgemein:
code(n) = abcde
abcd = n
e = (7 + n + (n mod 10) + (n mod 100) + (n mod 1000)) mod 10
= (7+a+b+c+d) mod 10
zu diesen codes kann man keinen mehr hinzufügen, der nicht an mindestens 4 stellen mit einem bereits vorhendenen übereinstimmt.
dies ist nur eine von (wie bereits oben angemerkt) vielen möglichkeiten. man könnte z.b. auch so beginnen: 00007, 00015, 00022, 00034, 00048, 00051, 00063, 00079, 00086, 00090, 00109, 00113,... kann man aber nicht so schön aufschreiben bzw. erklären.
gruß
markus |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Mittwoch, den 07. August, 2002 - 16:24: |
|
Gratuliere Markus, ganz ausgezeichnet!
Vielen Dank für diese ausführliche und lückenlose Herleitung. Kurz zusammengefasst entspricht es genau dem Algorithmus der praktisch verwendet wird: 5.Stelle = Ziffernsumme der ersten vier Stellen modulo 10. Und in Basis 2 heißt das dann Parity-Bit (werden einige schon mal gehört haben ;-). Echt super Markus!
@clara: Das "nein" zu deinem 1.Beitrag war natürlich schon hart. Sei mir bitte nicht bös', aber dadurch wurde die kreative Phantasie der anderen erst so richtig geweckt.
@Thomas: Nicht ärgern! Das Wichtigste ist der Spass am mathematischen Knobeln. Ob diese oder jene Zahl herauskommt ist zweitrangig.
Danke an alle, die aktiv mitgemacht haben!
sol@ti
|
Onkel Murray (murray)
Erfahrenes Mitglied
Benutzername: murray
Nummer des Beitrags: 120
Registriert: 10-2001
| | Veröffentlicht am Mittwoch, den 07. August, 2002 - 17:04: |
|
Aha, für mich liest sich die Aufgabe so:
"nur Codes die sich an mindestens zwei Stellen unterscheiden"
Also ein Code muß an mindestens zwei Stellen verschiedene Ziffern haben. Unter dieser Prämisse gibt es zwar keinen 00007-Agent, aber egal
Soviel also zum Thema, warum ich in der Schule Textaufgaben immer falsch hatte
Danny |
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1294
Registriert: 07-2000
| | Veröffentlicht am Mittwoch, den 07. August, 2002 - 21:23: |
|
Hallo,
gibt es genau 10000 gültige Codes?
Auch auf die Gefahr, mich zu wiederholen: Es kommt darauf an!
Ich habe mal ein Progrämmchen geschrieben, das zufällige 5-stellige Codes erzeugt, und diese nur dann in die Liste aufnimmt, wenn sie den Bedingungen des Geheimdienstes ihrer Majestät entsprechen.
Genauer gesagt, sucht das Programm solange zufällige Codes, bis 6500 zulässige Codes erzeugt wurden. Danach sucht es systematisch alle 5-stelligen Codes ab und nimmt sie ggf. in die Liste auf.
Ergebnis: Es wurden zwischen 6600 und 6800 Codes gefunden.
Die Lösung von Markus resp. Sol@ti stellt eine spezielle Methode dar, 10000 Codes zu erzeugen. Aber ist die Zahl 10000 wirklich maximal?
Wie lautet die MINIMALE Anzahl von Codes, sodass es keinen Code mehr gibt, der in die Liste aufgenommen werden kann?? |
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 75
Registriert: 03-2001
| | Veröffentlicht am Donnerstag, den 08. August, 2002 - 03:01: |
|
hallo zaph.
10000 ist die maximale anzahl gültiger codes.
stell dir die codes, auf welche weise auch immer du zu ihnen gelangt bist, aufsteigend geordnet vor. der erste lautet 00007. der nächste muß mit 0001 beginnen, sonst wären ja bereits die ersten 4 stellen gleich. somit erhältst du höchstens 10000 codes, nämlich mit den anfangsziffern von 0000 bis 9999.
über die minimale anzahl muß ich noch nachdenken.
gruß
markus |
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 76
Registriert: 03-2001
| | Veröffentlicht am Donnerstag, den 08. August, 2002 - 03:38: |
|
hallo nochmal.
der erste code lautet 00007. nun kann der nächste auf jeden fall ebenfalls mit 000 beginnen, die letzten beiden stellen müssen sich nur von 07 unterscheiden. zwischen 00000 und 00099 kann es maximal 10 gültige codes geben (s.o.).
diese 10 gibt es aber auf jeden fall! wären es nur 9, dann kommt sowohl bei den letzten als auch bei den vorletzten stellen dieser 9 codes eine der 10 ziffern 0-9 nicht vor. daraus können wir uns einen zehnten code basteln. also gibt es immer 10000 codes.
diese argumentation reicht meines erachtens für die gesamten codes aus. kA, warum dein programm nicht alle 10000 ausgespuckt hat.
oder, anders formuliert:
zu jedem code gibt es 9 andere, bei denen 3 stellen mit diesem übereinstimmen. gibt es weniger, so kann man sich die fehlenden codes erstellen, indem man die an den anderen beiden stellen nichtvorkommenden ziffern (0-9) verwendet.
gruß
markus |
Markus (boothby81)
Moderator
Benutzername: boothby81
Nummer des Beitrags: 77
Registriert: 03-2001
| | Veröffentlicht am Donnerstag, den 08. August, 2002 - 04:19: |
|
stop!
ich nehme meinen letzten beitrag zurück.
die minimale anzahl liegt wohl doch unter 10000. gibt es z.b. die 9 codes 314ab mit ab=11, 22, ..., 99 schon, dann kann man den code 31400 evt. nicht hinzufügen, weil es z.b. 21400 schon gibt.
gruß
markus |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Donnerstag, den 08. August, 2002 - 16:08: |
|
Hallo Zaph, hallo Markus!
Dass 10000 die maximale Anzahl ist, dürfte geklärt sein. Aber beim Minimum hast du vollkommen recht, Zaph. Meine Bemerkung "die Mächtigkeit der Menge aller Codezahlen ist eindeutig" ist definitv falsch. Und zwar schon bei dreistelligen Codes (die sich an mindestens 2 Stellen unterscheiden)! Der Fall ist überschaubar, nach Markus' Methode gibt es maximal 100 Codes. Ich hab ein kleines Beispiel gebastelt. Einen Beweis für das Minimum habe ich aber nicht einmal für diesen Spezialfall.
Folgende 74 Codezahlen sind nicht erweiterbar:
000 011 022 033 044 055 066 077 088
101 110 123 132 145 154 167 176 189 198
202 213 220 231 246 257 264 275
303 312 321 330 347 356 365 374
404 415 426 437 440 451 462 473
505 514 527 536 541 550 563 572
606 617 624 635 642 653 660 671
707 716 725 734 743 752 761 770
808 819 880 891
918 981 999
Die schwarzen Zahlen sind alle 64 Kombinationen ABC mit 0 <= A,B <=7 und C = A+B (falls A+B<=7) bzw. C = |A-B| (falls A+B>7). Die blauen Zahlen sind mit einiger Überlegung ausgewählt (es werden "viele" Ziffern 8 und 9 verwendet).
Wenn man versucht einen neuen Code, der mit 2,3,4,5,6 oder 7 beginnt, zu definieren, bleiben als Endziffern nur 88,89,98,99; die sind aber alle in den blauen Zahlen schon verwendet. Man kann leicht überprüfen, dass es auch keine neuen Codes kann, die mit 0,1,8 oder 9 beginnen.
Ein Beweis für das Minimum oder zumindest eine gute untere Schranke wäre schon interessant!
Viele Grüße
sol@ti
|
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1297
Registriert: 07-2000
| | Veröffentlicht am Donnerstag, den 08. August, 2002 - 21:11: |
|
Doch, das mit den 10000 Codes ist jetzt klar.
Nochmal das Argument:
Für 0 <= ABC < 1000 (ABC soll die Dezimaldarstellung sein) gibt es zwischen 100*ABC und 101*ABC maximal 10 Codes, da eine Zahl zwischen 100*ABC und 101*ABC von der Form ABCXY ist. Folglich gibt es maximal 10*1000 = 10000 verschiedene Codes.
Die 74 für dreistellige Codes als untere Schranke ist schon ziemlich gut. Mit zufälligem Suchen bin ich gerade bis 80 gelangt.
Man sollte die Sache also doch eher irgendwie systematisch angehen. |
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1298
Registriert: 07-2000
| | Veröffentlicht am Freitag, den 09. August, 2002 - 14:40: |
|
Kleine Korrektur. Soll heißen (2 x):
statt
"... zwischen 100*ABC und 101*ABC ..."
besser
"... größergleich 100*ABC und kleiner 100*(ABC + 1) ..."
|
Roland (excalibur81)
Neues Mitglied
Benutzername: excalibur81
Nummer des Beitrags: 2
Registriert: 08-2002
| | Veröffentlicht am Mittwoch, den 14. August, 2002 - 08:25: |
|
Wieviel ist denn jetzt die kleinste Anzahl von Codes?
Zu jedem Code gibt es 45 Codes, die nicht auftreten können (wenn man jeweils eine Ziffer verändert gibt es 5*9 falsche Codes).
100.000 / 46 = 2173,9
Also muss es schon mal mindestens 2174 Codes geben, egal wie man es macht.
Wahrscheinlich gibt es aber keine Möglichkeit, die Codes so zu machen, dass sich die jeweils 45 dazu gehörenden falschen Codes nicht ziemlich oft wiederholen. |
Zaph (zaph)
Senior Mitglied
Benutzername: zaph
Nummer des Beitrags: 1307
Registriert: 07-2000
| | Veröffentlicht am Mittwoch, den 14. August, 2002 - 21:06: |
|
Hallo Roland,
hieran beißen wir uns wohl die Zähne aus. Deine Überlegung stimmt aber leider nicht. Nimm an, du hast die Codes 00007 und 70000 in der kleinsten nicht erweiterbaren Menge zulässiger Codes. Da 00007 dabei ist, kann 70007 nicht hinzugenommen werden, wie du korrekt bemerkst. 70007 kann aber auch deshalb nicht hinzugenommen werden, da 70000 bereits in der Menge liegt. D. h. bei deiner Methode wird 70007 doppelt gezählt.
Oder habe ich dich falsch verstanden?
Ich vermute, da hier eine naheliegende Fragestellung vorliegt, hat sich irgend jemand vor uns schon mal den Kopf drüber zerbrochen.
Z. |
Roland (excalibur81)
Neues Mitglied
Benutzername: excalibur81
Nummer des Beitrags: 3
Registriert: 08-2002
| | Veröffentlicht am Donnerstag, den 15. August, 2002 - 08:10: |
|
Hallo Zaph,
das hab ich gemeint. Wenn man 2173 Zahlen hat und annimmt, dass alle jeweils 45 falschen Codes verschieden wären, hat man zusammen 2173*46 = 99968 Codes, also findet man noch eine 2174. Zahl, wobei dann nur noch 31 Zahlen übrig bleiben. Also hat man schon mindestens 45-31 = 14 falsche Codes, die zu mehreren richtigen Codes gehören. Dadurch kann man wahrscheinlich annehmen, dass in Wirklichkeit sehr viel mehr als 14 falsche Codes mehrfach vorkommen und man noch viele richtige Codes finden kann. |
sol@ti
Unregistrierter Gast
| | Veröffentlicht am Donnerstag, den 15. August, 2002 - 16:37: |
|
Hallo Roland, hallo Zaph,
mir ist aufgefallen, dass sich die Frage auf ein bekanntes Problem der Graphentheorie zurückführen lässt: Die Suche nach maximalen Cliquen. Das ist leider ein Standardbeispiel für NP-harte Probleme. Hier kurz die Idee:
Betrachte die Relation "2-unterscheidbar" auf der Menge aller n-stelligen Codes 00...00 bis 99...99. Zwei n-stellige Codes c,d heißen 2-unterscheidbar, wenn sie sich an mindestens zwei Stellen unterscheiden. Unsere Codemengen sind dann alle Mengen C mit den Eigenschaften:
(i) c,d aus C ==> c,d sind 2-unterscheidbar
(ii) Sei x ein n-stelliger Code, x nicht in C ==> es existiert c aus C, sodass c,x nicht 2-unterscheidbar
Die Relation 2-unterscheidbar ist symmetrisch und definiert daher einen ungerichteten Graphen auf der Knotenmenge aller n-stelligen Codes. Und die Codemengen C sind gerade die maximalen Cliquen dieses Graphen. Das ursprüngliche Rätsel bestand also darin, eine größte maximale Clique zu finden. Zaphs Frage ist nun die Suche nach einer kleinsten maximalen Clique.
Durch die spezielle Struktur unseres Graphen ist es "zufällig" möglich eine größte maximale Clique mit der von Markus gefundenen Ziffernsumme-Prüfziffer zu konstruieren. Ich habe inzwischen die dreistelligen Codes mit einem Greedy-Algorithmus durchsucht und keine kleinere maximale Clique als 74 gefunden. Ob das Konstruktionsprinzip meines 74er Beispiels auf mehrstellige Codes erweiterbar ist wäre zu überlegen. Allerdings fehlt dann immer noch eine scharfe untere Schranke, die die Minimalität der Konstruktion bestätigt.
Viele Grüße
sol@ti
|
|
