Aus zwei Zahlen mache Eins und wieder Zwei.

07.07.2017, 23:51

Dukkha

Aus zwei Zahlen mache Eins und wieder Zwei.

Richard möchte gerne die Information von $\begin{eqnarray*} 2 \end{eqnarray*}$ natürlichen Zahlen $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} y \end{eqnarray*}$ speichern, hat aber nur Speicherplatz für eine Zahl (Diese kann aber beliebig gross sein). Wie kann Richard das Problem mathematisch lösen, ohne das Einführen von neuen Symbolen wie einem Trennungssymbol $\begin{eqnarray*} x\|y \end{eqnarray*}$ ?

Beispielsweise die Konkatenation $\begin{eqnarray*} f(x,y)=xy \end{eqnarray*}$ funktioniert natürlich nicht, weil ich bei $\begin{eqnarray*} 332 \end{eqnarray*}$ nicht weiss, ob es sich um $\begin{eqnarray*} 33 \end{eqnarray*}$ und die Zahl $\begin{eqnarray*} 2 \end{eqnarray*}$ handelt, oder um $\begin{eqnarray*} 3 \end{eqnarray*}$ und die Zahl $\begin{eqnarray*} 32 \end{eqnarray*}$ handelt.

Edit X: Nicht erlaubt sind jegliche Art von Trennungssymbolen. Das heisst $\begin{eqnarray*} x,y \end{eqnarray*}$ in Binärzahlen und dazwischen eine $\begin{eqnarray*} 8 \end{eqnarray*}$ ist nicht erlaubt. ( $\begin{eqnarray*} (3,2) \to 11810 \end{eqnarray*}$ ist nicht erlaubt)

Edit X2: Die Reihenfolge spielt eine Rolle, d.h. das Eingabe-Tupel $\begin{eqnarray*} (2,3) \end{eqnarray*}$ ist nicht dasselbe wie $\begin{eqnarray*} (3,2) \end{eqnarray*}$ !

08.07.2017, 05:14

Dopap

Auf diesen Beitrag antworten »

wenn $\begin{eqnarray*} x^y=\bigg(\prod_{i=1}^k p_i^{\alpha_i}\bigg)^y=\prod_{i=1}^k p_i^{\alpha_iy}=\prod_{i=1}^k p_i^{q_i} \end{eqnarray*}$ gilt, dann lässt sich doch x und y rekonstruieren. Oder nicht ? verwirrt

08.07.2017, 05:21

Dukkha

Auf diesen Beitrag antworten »

Was sind $\begin{eqnarray*} k, p_i, \alpha_i, q_i \end{eqnarray*}$ ?

PS: vielleicht hast du eine Lösung gefunden, ich gehe aber davon aus, dass es nicht stimmt. Tipp: Denke mengentheoretisch.

Edit:

$\begin{eqnarray*} x^y = c = x^z + k \end{eqnarray*}$ ist offensichtlich nicht eindeutig?

Edit 2: Die Operation ist nicht kompliziert. Denke mengentheoretisch.

08.07.2017, 05:41

Dopap

Auf diesen Beitrag antworten »

$\begin{eqnarray*} x=\prod_{i=1}^k p_i^{\alpha_i} \end{eqnarray*}$

ist doch eine übliche Darstellung der Primzahlfaktorenzerlegung.

die $\begin{eqnarray*} p_i \end{eqnarray*}$ sind der Reihe nach die Primzahlen 2,3,5,7...

k ist "letzte" Index

$\begin{eqnarray*} \alpha_i \in \{0,1,2,3,\cdots\} \end{eqnarray*}$

und $\begin{eqnarray*} q_i=\alpha_iy \end{eqnarray*}$

das ergibt sich doch aus dem Zusammenhang.

08.07.2017, 05:44

Dukkha

Auf diesen Beitrag antworten »

Und weshalb ist das eindeutig? (Vielleicht stimmt deine Antwort, bitte ausführlicher)

Also $\begin{eqnarray*} 2^4 \end{eqnarray*}$ und $\begin{eqnarray*} 4^2 \end{eqnarray*}$ stimmen nicht.

Edit : Mein Edit beachten. Die Operation ist nicht kompliziert, sie ist sehr simple. Denke mengentheoretisch.

08.07.2017, 05:59

Dukkha

Auf diesen Beitrag antworten »

Es ist ein klassisches Problem der old-school theoretischen Informatik, bitte nicht googlen. Ich gebe dafür nochmals einen Tipp. (und noch mehr, so viel ihr wollt, aber bitte nicht googlen!) Die Antwort ist nicht kompliziert, du kennst sie bestimmt mit ein bisschen Nachdenken! Hier der Tipp:

$\begin{eqnarray*} \mathbb{N} \times \mathbb{N} \to \mathbb{N} \to \mathbb{N} \times \mathbb{N} \end{eqnarray*}$

Was brauchen wir, Surjektion, Injektion oder Bijektion?

08.07.2017, 07:35

Dukkha

Auf diesen Beitrag antworten »

Noch ein Tipp, dann sollte es klar sein.

@IfindU Es ist Analysis 1! Wink

@Clearly_wrong btw. die Aufgabe ist nur Analysis 1.

08.07.2017, 09:23

Clearly_wrong

Auf diesen Beitrag antworten »

Vielleicht haben wir genau aus diesem Grund nicht geantwortet, Dukkha Augenzwinkern

Aber gut, das lasse ich nicht auf mir sitzen.

Möglichkeit 1: Seien $\begin{align*} p,q \end{align*}$ beliebige Primzahlen. Wenn ich die Zahl $\begin{align*} p^xq^y \end{align*}$ speichere, weiß ich aufgrund der Eindeutigkeit der Primfaktorzerlegung genau, welche zwei Zahlen $\begin{align*} x,y \end{align*}$ ich gespeichert habe.

Möglichkeit 2: Gerader und ungerader Anteil einer Zahl: Wir bilden $\begin{align*} (x,y)\mapsto (2x-1)\cdot 2^{y-1} \end{align*}$ ab. Dabei handelt es sich sogar um eine Bijektion, wenn wir die natürlichen Zahlen bei $\begin{align*} 1 \end{align*}$ beginnen lassen, auch wenn eine Injektion wie in Möglichkeit 1 natürlich ausreicht.

08.07.2017, 09:27

Dopap

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 2^4=4^2 \end{eqnarray*}$

immer diese Minimalgegenbeispiele unglücklich

08.07.2017, 10:15

Dukkha

Auf diesen Beitrag antworten »

Zitat:

Original von Clearly_wrong
Vielleicht haben wir genau aus diesem Grund nicht geantwortet, Dukkha Augenzwinkern

Ich kenne keinen Beweis für Deine Aussage, aber ich denke, sie wäre richtig, wenn wir die $\begin{eqnarray*} 0 \end{eqnarray*}$ nicht zu den natürlichen Zahlen hinzufügen würden. Ich habe $\begin{eqnarray*} \mathbb{N}_0 \end{eqnarray*}$ kennengelernt. Aber natürlich, sehr gute Antwort!!

(PS: Das ist kein Analysis 1)

Edit: Deine zweite Antwort scheint auch korrekt zu sein. Hier funktioniert sogar der $\begin{eqnarray*} 0 \end{eqnarray*}$ -Fall. Well done, ich ziehe meinen Hut!
Auch wenn es nicht meine schöne Analysis 1 Lösung ist Augenzwinkern

Aber Lösung ist Lösung!

Findest du noch meine analytische Lösung raus?

08.07.2017, 10:36

Clearly_wrong

Auf diesen Beitrag antworten »

Irgendwie haben wir ein unterschiedliches Verständnis dafür, was man in Analysis 1 macht, aber ist ja nicht so wichtig, welcher Vorlesung nun was zugeordnet wird smile

Schönes Wochenende dir.

08.07.2017, 10:44

Dukkha

Auf diesen Beitrag antworten »

Zitat:

Original von Clearly_wrong
Schönes Wochenende dir.

Danke, dass wünsch ich Dir auch!

Ich möchte Dir aber noch meine Lösung nennen: "Das Cantorsche Diagonalverfahren". In diesem Fall nennt man das die Cantorsche Paarungsfunktion https://de.wikipedia.org/wiki/Cantorsche_Paarungsfunktion

Aber sehr schön, einen algebraischen Ansatz zu sehen Freude

08.07.2017, 10:47

Clearly_wrong

Auf diesen Beitrag antworten »

Schau auf der von dir verlinkten Seite mal bei Alternativen.

Da stehen witzigerweise auch beide meiner Möglichkeiten. Das ist also weniger ein algebraischer Ansatz als mehr eine andere Formulierung deiner Version Augenzwinkern

08.07.2017, 10:55

Dopap

Auf diesen Beitrag antworten »

1.) zwei Primzahlen kann ich als Produkt speichern. Die Rückzerlegung in 2 Faktoren ist zwar eindeutig aber kommutativ. Das ist aber nicht gestattet !
2.) und was ist mit den anderen Zahlenpaaren ??

Kann jemand bei mir für etwas Erleuchtung sorgen?

btw: in der Rätselecke sollte die Lösung des TS schon von Diesem irgendwann dargelegt werden.

08.07.2017, 10:58

Dukkha

Auf diesen Beitrag antworten »

Ach dann kanntest du die Lösung schon von Anfang an. geschockt

Ich finde schon noch ein Rätsel, dass du nicht kennst Augenzwinkern

Hast du Informatik studiert oder bist du Algebraiker?

08.07.2017, 11:00

Clearly_wrong

Auf diesen Beitrag antworten »

@Dopap:

Ich verstehe deinen Einwand mit der Kommutativität nicht. Mal ein Beispiel: Ich wähle die Primzahlen 2 und 3. Kannst du mir jetzt x,y nennen, für die ich aus 2^x*3^y nicht wieder herausfinden kann, was x,y waren?

@Dukkha: Meinst du mich oder Dopap? Falls du mich meinst:

Ich habe Mathematik studiert, habe aber mit Algebra überhaupt nichts am Hut, damit kannst du mich jagen Big Laugh

Die Lösung kannte ich schon, nur nicht als Rätsel verpackt. Wir sollten in Analysis 1 (duck und weg Big Laugh

) mal eine Bijektion zwischen $\begin{align*} \mathbb N \end{align*}$ und $\begin{align*} \mathbb N^2 \end{align*}$ explizit angeben und damals war mir das Diagonalverfahren zu umständlich, deswegen der gerade und ungerade Anteil.

08.07.2017, 12:11

Dopap

Auf diesen Beitrag antworten »

Zitat:

Original von Clearly_wrong
@Dopap:

Ich verstehe deinen Einwand mit der Kommutativität nicht. Mal ein Beispiel: Ich wähle die Primzahlen 2 und 3. Kannst du mir jetzt x,y nennen, für die ich aus 2^x*3^y nicht wieder herausfinden kann, was x,y waren?

Ach sooo! . Irgendwie habe ich das nicht herauslesen können oder wollen. Schreibe das doch klar und deutlich und in Latex hin.
edit: mathjax kann ich nicht lesen, dann lag es daran, Sorry

Meine eigene Idee war so ein Versuch in die richtige Richtung, aber $\begin{eqnarray*} 2^x\cdot 3^y \end{eqnarray*}$ (*) ist natürlich überzeugend !

Zitat:

@Dukkha: Meinst du mich oder Dopap? Falls du mich meinst:

Ich habe Mathematik studiert, habe aber mit Algebra überhaupt nichts am Hut, damit kannst du mich jagen Big Laugh

[...]

geht mir ähnlich ...

(*) könnte mich ärgern denn schon vor langer Zeit hatte ich folgende Verschlüsselungsidee:

$\begin{eqnarray*} Kurt=2^{11}3^{21}5^{18}7^{20} \end{eqnarray*}$ Big Laugh

08.08.2017, 06:38

Dukkha

Auf diesen Beitrag antworten »

Zitat:

Original von Dopap
verwirrt

Ich habe diesen Beitrag überlesen. Ich habe die Lösung vorher gepostet, über ein Diagonalverfahren. Meine Lösung war: die Cantorsche Paarungsfunktion. Clearly_wrong hat aber eine andere Lösung gefunden.

20.03.2018, 09:10

Tochrim

Auf diesen Beitrag antworten »

Ich weiß zwar nicht ob man das als "mathematische Lösung" betrachten kann, aber warum zerlege ich meine Zahlen nicht in die kleinsten Teiler?
Beispiel:
ich will zahl 40 und 24 Speichern.

2*2*2*5 =40
2*2*2*3 =24

und für mein System speichere ich dann

222502223

die 0 ist das Trennzeichen, da die 0 bei der Zerlegung nicht als Faktor vorkommen kann.

Falls ich etwas mit 0 speichern will wäre es auch eindeutig, da dann als einziges zwei bzw drei 0 hintereinander wären.

000
00x
x00

Edit:
Ok, ich habe den zweiten Edit nicht gelesen... Das mit den binären und der 8...
und ohne trennungszeichen klappte es leider bei sowas wie 2 und 4 nicht weil dann in beiden fällen 222 raus käme

Edit 2:
Wobei, wenn ich das ganze als:
1222512223
aufschreibe geht es, da es dann eindeutig ist ohne das ich explizit mit der 0 trenne und die zerlegung beinhaltet wenn ich will ja auch ne 1

20.03.2018, 09:38

Tochrim

Auf diesen Beitrag antworten »

Ok, das klapt auch nicht bei den zahlen zB:

1 und 11, da es
1*1 und 1*11 wären und ich das dann
11111
sind... und das könnte ich 1 zu eins vertauschen. Aber wenn ich die zahlen vorher mal 2 Multipliziere sollte es spätestens gehen.

dann wären die Zahlen
121211

Also 2x2y kann man bei der Faktorzerlegung ohne probleme als eine Zahl ohne Trennzeichen (da die 1 ja auch ein Faktor ist) aus meiner sicht speichern.

20.03.2018, 11:44

HAL 9000

Auf diesen Beitrag antworten »

Komplett unausgegorener Vorschlag: Bei Kodierung 2223 weiß man nicht, ob sie für

2*2*2*3 = 24
2*2*23 = 92
oder
2*223 = 446

steht. Von Eindeutigkeit also keine Spur. unglücklich

20.03.2018, 12:25

Tochrim

Auf diesen Beitrag antworten »

Da hast du natürlich recht.
Da muss man es anderst angeben.
wenn ich die komplette reihe der primzahlen angebe und statt zB 2*2*2 die 2^3 nehme sollte es doch dann aber klappen, oder? Also bei 24
1^0*2^3*3^1 =102331
und bei 92
1^0*2^2*3^0*5^0*7^0*11^0*13^0*17^0*19^0*23^1=1022305070110130170190231.
Und 24,92 wäre dann
1023311022305070110130170190231?

20.03.2018, 12:40

Tochrim

Auf diesen Beitrag antworten »

Ich meine, dadurch das ich immer das Schema:

1^0bzw1*2^a*3^b*5^c*7^d*11^e*13^f*17^g*19^h*23^i...
habe lässt sich doch ein Muster erkennen, wo ich sehr klar die Wiederholung ausmachen kann

Edit:
Okok, bei

2^3*3^333 bzw bei
2^33*3^33 läge das selbe problem vor -.- also bei ganz großen zahlen gehts nicht... außerich setze immer ne 0 dazwischen a la

2^03*3^0333 -> 20330333
2^033*3^033 -> 20333033

05.04.2018, 13:56

m@he

Auf diesen Beitrag antworten »

Wie wäre es denn damit:

In beiden Zahlen werden alle "Nullen" durch die Kombination "01" ersetzt und beide Zahlen durch "00" miteinander verbunden! Durch die Ersetzung mittels "01" kann in den beiden Zahlen keine mehrfache Null mehr auftreten. Die einzige Stelle mit doppelter Null ist die Trennstelle. In den beiden wieder herausgelösten Ziffernfolgen werden alle "1"-en nach einer Null gestrichen und man hat die Ausgangszahl.

2 und 4 => 2004

binär: 10 und 100 => 1010010101

1001 und 4056 => 1010110040156

binär: 1111101001 und 111111011000 => 1111101101011001111110111010101

Da jedes (sinnvolles) Zahlensystem mit mindestens zwei Ziffern arbeitet und eine einstellige Zahl, die bzgl. der Addition neutrale Zahl ist, und eine andere einstellige Zahl, die bzgl. der Multiplikation neutrale Zahl ist, sind die beiden zu wählenden Ziffern in jedem Zahlensystem vorhanden.

Das Verfahren lässt sich beliebig modifizieren, z.B.: Man schiebt in jeder Zahl, nachdem n-Mal eine Null gestanden hat, eine beliebige, aber unbedingt von Null verschiedene Ziffer ein. Dann verbindet man beide Zahlen mit (n+1)-Mal einer Null. Die Dekodierung findet die größte Anzahl an aufeinanderfolgenden Nullen und nimmt diese als Trennzeichen für die beiden Zahlen. Von der maximalen Anzahl aufeinanderfolgender Nullen wird eine Stelle abgezogen und bei jedem Auftreten dieser Anzahl von aufeinanderfolgenden Nullen wird die folgende Ziffer gestrichen. Bei diesem Verfahren muss man nicht mitteilen, wie viele Nullen man als Trennzeichen verwendet und man muss auch nicht die "1" als Auffüller verwenden.

Neue Frage »

Antworten »

Aus zwei Zahlen mache Eins und wieder Zwei.

Verwandte Themen