Zeigen Sie, dass f bijektiv ist

Question

Sei f : N² → N gegeben durch f(a, b) = max(a, b)² + max(a, b) + a − b.

Zeigen Sie, dass f bijektiv ist

Comments

Hallo nochmal !

So ungefähr zu gleichen Teilen zu meinem Vergnügen und zur Selbstbestätigung sowie aus etwas Corona-Langeweile habe ich mich nun noch um einen Algorithmus für die Umkehrfunktion bemüht. Der soll uns also zu einer beliebigen natürlichen Zahl

z ∈ ℕ₀  die beiden (eindeutig bestimmten)  Zahlen  x , y  ∈ ℕ₀  liefern, für welche die Gleichung  z = max(x,y)² + max(x,y) + x - y  gilt.

Hier mein Algorithmus:

1.)  Berechne  max:= ⌊\( \sqrt{z} \)⌋

(Floor-Funktion: Abrunden auf ganzzahligen Wert)

2.)  Berechne  p := max · (max + 1)

3.)  Falls  z ≥ p ist, dann setze  x := max  und  y:= max + p - z

   und andernfalls  ( z < p)  setze  y := max  und  x:= max - p + z

Answer 1

Interessant !

Ich hab mir mal von Wolfram Alpha eine kleine Tabelle schreiben lassen:

https://www.wolframalpha.com/input/?i=table+%28max%28x%2C+y%29%29%5E2+%2B+max%28x%2Cy%29+%2B+x+%E2%88%92+y+%2C+x%3D0..9+%2C+y%3D0..9

... und erstaunlicherweise scheint es zu passen !

Um das Ganze nachvollziehen zu können, müsste man wohl die Reihenfolge der Zahlenwerte in der Tabelle in Quadraten und daran anschließendenQuadrat-Säumen im Detail verfolgen.

Comments

Ich bedanke mich ganz herzlich!

---

mein Gehirn funktioniert nicht mehr, Wie kann ich es zeigen, dass es eine bijektion ist?

---

injektiv geht aber wie kann man subjektivität zeigen? kannst du ein paar Tipps geben?

---

Wenn du die Injektivität von f schon hast zeigen können, bleibt wirklich nur noch zu zeigen, dass f auch surjektiv  (nicht "subjektiv" !) ist.

Dazu könntest du allenfalls den Algorithmus benutzen, den ich für die Umkehrfunktion schon angegeben habe. Zeige also:

(1.) dieser Algorithmus liefert zu jeder beliebigen Zahl  z ∈ ℕ₀  ein Zahlenpaar (x,y) ∈ ℕ₀²  , und

(2.)  für dieses Zahlenpaar gilt dann auch wieder  f(x,y) = z .

Damit wäre dann gezeigt, dass der Wertebereich der Abbildung f wirklich die gesamte Menge  ℕ₀  ist, was bedeutet, dass f tatsächlich surjektiv ist.

(wenn ich die Tabelle betrachte, die ich für f  aufgestellt habe, scheint mir die Tatsache der Bijektivität der Abbildung anschaulich eigentlich absolut klar)