Zahlen mit unterschiedlichen Ziffern
On Januar 11, 2021 by adminBetrachten Sie die Menge der natürlichen Zahlen von 0 bis einschließlich 999. Angenommen, wir wählen eine Teilmenge dieser Menge so aus, dass jedes Zahlenpaar nicht mehr als eine Ziffer an denselben Positionen teilt. Zur Verdeutlichung sind
- Paare wie 123 und 456 offensichtlich zulässig, da sie keine gemeinsamen Ziffern haben.
- 123 und 321 sind seitdem zusammen zulässig, während sie haben die gleichen exakten Ziffern, nur die 2 befindet sich tatsächlich an der gleichen Position.
- 812 und 212 wären nicht erlaubt, da beide die „12“ an ihrem Ende teilen, die ist zwei Ziffern.
- 206 und 246 sind ebenfalls nicht zulässig, die gemeinsam genutzten Ziffern müssen nicht zusammenhängend sein.
- Führende Nullen sind wichtig, daher sind 5 und 205 ein verbotenes Paar als Gut. (Stellen Sie sich 5 als „005“ vor.)
Denken Sie daran, dass dies für jedes Zahlenpaar in der Teilmenge gelten muss. Was ist die größte (wie in die meisten Elemente ) mögliche Menge, die diese Bedingung erfüllt? Wie wäre es mit der Menge mit der größten Summe von Elementen?
(Puzzle inspiriert von einem Gespräch mit a Freund bezüglich der falschen Eingabe von ID-Nummern. Entschuldigung, wenn dies hier bereits gefragt wurde.)
Antwort
Für das, was es wert ist, Ich habe eine gute Vorstellung davon, warum die Antwort 100 lautet:
Stellen Sie sich zunächst einen einfacheren Fall vor, in dem Sie alle Zahlen 0-99 haben und nicht zwei Zahlen eine Ziffer an derselben Stelle teilen können. Wir können eine Tabelle mit Zahlen wie folgt zeichnen:
Beachten Sie, dass jede Zahl in einer Zeile ihre erste Ziffer und jede Zahl in einer Spalte ihre zweite Ziffer teilt Ziffer. Daher müssen Sie Zahlen so auswählen, dass sich keine zwei eine Zeile oder Spalte teilen. Es ist ziemlich klar, dass die maximale Anzahl von Zahlen, die Sie auswählen können, 10 beträgt. Hier ist eine Lösung:
Betrachten Sie nun den in der Frage gestellten Fall. Holen Sie sich 10 dieser 0..99-Tabellen, außer dass die zweite Tabelle 100..199, die dritte 200..299 usw. enthält. Dann schichten Sie sie hintereinander, um eine zu bilden 10x10x10 Raster von 0..999 (Ich habe einige der Zahlen eingegeben, um Ihnen die Idee zu geben):
Beachten Sie, dass jede Zahl in einem beliebigen „Streifen“ von zehn Würfeln (Zeile oder Spalte) haben zwei Ziffern gemeinsam. Daher müssen Sie Zahlen so auswählen, dass keine Zahl einen „Streifen“ teilt.
Nachdem Sie ein wenig nachgedacht haben, ist klar, dass Sie nur in der Lage sind um 100 solcher Zahlen auszuwählen.
Antwort
Um PrisonMonkeys eine Antwort hinzuzufügen, jede Menge mit 100 Elemente haben dieselbe Summe, dh 49950. Für jede Stelle in der Zahl kann jede Ziffer nur an dieser Stelle erscheinen e höchstens 10 Mal, da es nicht zweimal mit demselben Wert für einen anderen Ort angezeigt werden kann. Dies bedeutet, dass jede Ziffer genau zehnmal an jeder Stelle erscheinen muss, damit sich insgesamt 100 Zahlen im Satz befinden. Daher können wir jeden Ort separat summieren, um 45000 + 4500 + 450 = 49950 zu erhalten.
Antwort
Ich habe eine Lösung mit 100 Elemente in der Menge. Generieren Sie jede Zahl wie folgt:
Fügen Sie für das Element $ 0 \ leq n \ leq 99 $
ABC
hinzu Die Menge, in derAB
$ n $ ist (mit einer führenden Null, wenn $ n < 10 $) undC
istA+B mod 10
. Für $ n = 3 $ istAB
03
undC
0+3 mod 10=3
, was bedeutet, dassABC
033
ist.
In diesem Satz gibt es keine Zahlenpaare, die gegen die Bedingung verstoßen (soweit ich weiß). Und es gibt keine dreistellige Nummer ABC
mit einem anderen AB
Teil, da ich alle 100 Möglichkeiten abgedeckt habe. Dies bedeutet, dass dies die größtmögliche Menge ist, die die Bedingung erfüllt.
Ich habe noch keine Lösung für die zweite Frage.
Kommentare
- Ihre Erklärung des Sets schien ziemlich unklar. Ich habe versucht, es aufzuräumen, um es verständlicher zu machen. Sie können es jederzeit ändern, wenn Sie das Gefühl haben, dass ich nicht ' erfasst habe, was Sie sagen wollten.
- @RobWatts Vielen Dank, genau das war ich Versuche zu sagen. Es scheint einfacher zu verstehen, obwohl ' schwer zu sagen ist, ich habe bereits verstanden, was ich meinte.
- Hallo. Können Sie bitte ein Beispiel mit n > 10 hinzufügen?
- @Kalissar Zum Beispiel $ n = 57 $, dann ist
AB
57
(A=5
undB=7
) undC
ist5+7 mod 10=2
, alsoABC
ist572
.
Schreibe einen Kommentar