{"id":1921,"date":"2018-05-24T00:46:51","date_gmt":"2018-05-23T22:46:51","guid":{"rendered":"https:\/\/vielhuber.de\/?p=1921"},"modified":"2018-05-25T00:45:08","modified_gmt":"2018-05-24T22:45:08","slug":"froesche-fangen","status":"publish","type":"post","link":"https:\/\/vielhuber.de\/blog\/froesche-fangen\/","title":{"rendered":"Fr\u00f6sche fangen"},"content":{"rendered":"

Ein Frosch springt auf dem Zahlenstrahl umher und man versucht ihn zu fangen. Dabei wechseln sich Springen und Fangen stets ab. Der Frosch startet an Position \\(s \\in \\mathbb{Z}\\) und bei jedem Zug springt er eine Distanz von \\(z \\in \\mathbb{Z}\\) (falls \\(z>0\\), springt er nach rechts, anderen falls nach links). \\(z\\) ist bei jedem Sprung gleich. Das Fangen besteht aus der Angabe einer ganzzahligen Position. Man kennt weder \\(z\\) noch \\(s\\). Wir zeigen, dass es eine Vorgehensweise gibt, mit der man stets den Frosch f\u00e4ngt.<\/p>\n

<\/p>\n

Zun\u00e4chst ist \\(a_1 = s\\) und \\(a_{n+1} = a_n + z = s + n \\cdot z\\) mit \\(s,z \\in \\mathbb{Z}\\).<\/p>\n

Wir w\u00e4hlen nun\u00a0<\/p>\n

$$h:\\mathbb{N} \\to \\mathbb{Z}^2: h(2^k r) = \\left ( (-1)^{k+1} \\left \\lfloor \\frac{k+1}{2} \\right \\rfloor, (-1)^{\\frac{r+1}{2}} \\left \\lfloor \\frac{r+1}{4} \\right \\rfloor \\right ) $$<\/p>\n

als diejenige Funktion, die jeder nat\u00fcrlichen Zahl (genau) ein Zahlentupel ganzer Zahlen zuordnet. Die Wahl dieser Funktion ist durch die Funktionen \\(f(n) = (-1)^n \\left \\lfloor \\frac{n}{2} \\right \\rfloor\\), die \\(\\mathbb{N}\\) auf \\(\\mathbb{Z}\\) sowie \\(g(2^k r) = (k+1, \\frac{r+1}{2})\\), die\u00a0\\(\\mathbb{N}\\) auf \\(\\mathbb{N}^2\\) bijektiv abbilden, motiviert.<\/p>\n

Wir zeigen nun die Surjektivit\u00e4t von \\(h\\) (\\(h\\) ist auch injektiv, diese Eigenschaft ben\u00f6tigen wir jedoch nicht).<\/p>\n

Sei \\((x,y) = (2^{k_1} r_1, 2^{k_2} r_2) \\in\\mathbb{Z}^2\\). Dann ist aber<\/p>\n

$$h \\left ( 2^{2 \\cdot 2^{k_1} r_1 - 1} \\cdot (4 \\cdot 2^{k_2} r_2 - 1) \\right ) = (2^{k_1} r_1, 2^{k_2} r_2) = (x,y).$$<\/p>\n

Damit gilt: \\(\\forall (s,z) \\in \\mathbb{Z}^2 \\, \\exists \\, m \\in \\mathbb{N}\\) mit \\(h(m) = (x_m,y_m) = (s, z)\\).<\/p>\n

Sind wir beispielsweise am Zug bei \\(n = 88\\), berechnen wir \\(h(88)=(2,3)\\) und w\u00e4hlen als Position \\(2 + 88 \\cdot 3 = 266\\).<\/p>\n

Dann f\u00e4llt aber nach genau \\(m\\) Z\u00fcgen mit \\(x_m + m \\cdot y_m = s + m \\cdot z = a_m\\) die Wahl auf den Frosch.<\/p>\n

Neben \\(h\\) sind noch viele andere Funktionen wie die Cantorsche Paarungsfunktion<\/a> oder eine\u00a0bijektive Spirale<\/a> m\u00f6glich.<\/p>\n

Es folgt eine einfache Implementierung in JavaScript:<\/p>\n

See the Pen catch the frog<\/a> by David Vielhuber (@vielhuber<\/a>) on CodePen<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"

Ein Frosch springt auf dem Zahlenstrahl umher und man versucht ihn zu fangen. Dabei wechseln sich Springen und Fangen stets ab. Der Frosch startet an Position \\(s \\in \\mathbb{Z}\\) und bei jedem Zug springt er eine Distanz von \\(z \\in \\mathbb{Z}\\) (falls \\(z>0\\), springt er nach rechts, anderen falls nach links). \\(z\\) ist bei jedem […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"gtbabel_prevent_lngs":"","gtbabel_alt_lng":"","footnotes":""},"categories":[1],"tags":[],"class_list":{"0":"post-1921","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-blog"},"acf":[],"yoast_head":"Fr\u00f6sche fangen < Vielhuber David<\/title>\n<meta name=\"description\" content=\"Ein Frosch springt auf dem Zahlenstrahl umher und man versucht ihn zu fangen. Dabei wechseln sich Springen und Fangen stets ab. Der Frosch startet an\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/vielhuber.de\/blog\/froesche-fangen\/\" \/>\n<meta property=\"og:locale\" content=\"de_DE\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Fr\u00f6sche fangen < Vielhuber David\" \/>\n<meta property=\"og:description\" content=\"Ein Frosch springt auf dem Zahlenstrahl umher und man versucht ihn zu fangen. Dabei wechseln sich Springen und Fangen stets ab. Der Frosch startet an\" \/>\n<meta property=\"og:url\" content=\"https:\/\/vielhuber.de\/blog\/froesche-fangen\/\" \/>\n<meta property=\"og:site_name\" content=\"Vielhuber David\" \/>\n<meta property=\"article:published_time\" content=\"2018-05-23T22:46:51+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2018-05-24T22:45:08+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/vielhuber.de\/wp-content\/uploads\/about.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"700\" \/>\n\t<meta property=\"og:image:height\" content=\"552\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"David\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@vielhuber\" \/>\n<meta name=\"twitter:site\" content=\"@vielhuber\" \/>\n<meta name=\"twitter:label1\" content=\"Verfasst von\" \/>\n\t<meta name=\"twitter:data1\" content=\"David\" \/>\n\t<meta name=\"twitter:label2\" content=\"Gesch\u00e4tzte Lesezeit\" \/>\n\t<meta name=\"twitter:data2\" content=\"2\u00a0Minuten\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/froesche-fangen\\\/#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/froesche-fangen\\\/\"},\"author\":{\"name\":\"David\",\"@id\":\"https:\\\/\\\/vielhuber.de\\\/#\\\/schema\\\/person\\\/64d4ff14713d413ea4d9b210d0c2c6ef\"},\"headline\":\"Fr\u00f6sche fangen\",\"datePublished\":\"2018-05-23T22:46:51+00:00\",\"dateModified\":\"2018-05-24T22:45:08+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/froesche-fangen\\\/\"},\"wordCount\":351,\"publisher\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/#\\\/schema\\\/person\\\/64d4ff14713d413ea4d9b210d0c2c6ef\"},\"articleSection\":[\"Blog\"],\"inLanguage\":\"de\"},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/froesche-fangen\\\/\",\"url\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/froesche-fangen\\\/\",\"name\":\"Fr\u00f6sche fangen < Vielhuber David\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/#website\"},\"datePublished\":\"2018-05-23T22:46:51+00:00\",\"dateModified\":\"2018-05-24T22:45:08+00:00\",\"description\":\"Ein Frosch springt auf dem Zahlenstrahl umher und man versucht ihn zu fangen. Dabei wechseln sich Springen und Fangen stets ab. Der Frosch startet an\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/froesche-fangen\\\/#breadcrumb\"},\"inLanguage\":\"de\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/vielhuber.de\\\/blog\\\/froesche-fangen\\\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/vielhuber.de\\\/blog\\\/froesche-fangen\\\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/vielhuber.de\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Fr\u00f6sche fangen\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/vielhuber.de\\\/#website\",\"url\":\"https:\\\/\\\/vielhuber.de\\\/\",\"name\":\"Vielhuber David\",\"description\":\"Full-Stack Developer\",\"publisher\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/#\\\/schema\\\/person\\\/64d4ff14713d413ea4d9b210d0c2c6ef\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/vielhuber.de\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"de\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\\\/\\\/vielhuber.de\\\/#\\\/schema\\\/person\\\/64d4ff14713d413ea4d9b210d0c2c6ef\",\"name\":\"David\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"de\",\"@id\":\"https:\\\/\\\/vielhuber.de\\\/wp-content\\\/uploads\\\/about.jpg\",\"url\":\"https:\\\/\\\/vielhuber.de\\\/wp-content\\\/uploads\\\/about.jpg\",\"contentUrl\":\"https:\\\/\\\/vielhuber.de\\\/wp-content\\\/uploads\\\/about.jpg\",\"width\":700,\"height\":552,\"caption\":\"David\"},\"logo\":{\"@id\":\"https:\\\/\\\/vielhuber.de\\\/wp-content\\\/uploads\\\/about.jpg\"},\"sameAs\":[\"https:\\\/\\\/x.com\\\/vielhuber\"]}]}<\/script>","yoast_head_json":{"title":"Fr\u00f6sche fangen < Vielhuber David","description":"Ein Frosch springt auf dem Zahlenstrahl umher und man versucht ihn zu fangen. Dabei wechseln sich Springen und Fangen stets ab. Der Frosch startet an","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/vielhuber.de\/blog\/froesche-fangen\/","og_locale":"de_DE","og_type":"article","og_title":"Fr\u00f6sche fangen < Vielhuber David","og_description":"Ein Frosch springt auf dem Zahlenstrahl umher und man versucht ihn zu fangen. Dabei wechseln sich Springen und Fangen stets ab. Der Frosch startet an","og_url":"https:\/\/vielhuber.de\/blog\/froesche-fangen\/","og_site_name":"Vielhuber David","article_published_time":"2018-05-23T22:46:51+00:00","article_modified_time":"2018-05-24T22:45:08+00:00","og_image":[{"width":700,"height":552,"url":"https:\/\/vielhuber.de\/wp-content\/uploads\/about.jpg","type":"image\/jpeg"}],"author":"David","twitter_card":"summary_large_image","twitter_creator":"@vielhuber","twitter_site":"@vielhuber","twitter_misc":{"Verfasst von":"David","Gesch\u00e4tzte Lesezeit":"2\u00a0Minuten"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/vielhuber.de\/blog\/froesche-fangen\/#article","isPartOf":{"@id":"https:\/\/vielhuber.de\/blog\/froesche-fangen\/"},"author":{"name":"David","@id":"https:\/\/vielhuber.de\/#\/schema\/person\/64d4ff14713d413ea4d9b210d0c2c6ef"},"headline":"Fr\u00f6sche fangen","datePublished":"2018-05-23T22:46:51+00:00","dateModified":"2018-05-24T22:45:08+00:00","mainEntityOfPage":{"@id":"https:\/\/vielhuber.de\/blog\/froesche-fangen\/"},"wordCount":351,"publisher":{"@id":"https:\/\/vielhuber.de\/#\/schema\/person\/64d4ff14713d413ea4d9b210d0c2c6ef"},"articleSection":["Blog"],"inLanguage":"de"},{"@type":"WebPage","@id":"https:\/\/vielhuber.de\/blog\/froesche-fangen\/","url":"https:\/\/vielhuber.de\/blog\/froesche-fangen\/","name":"Fr\u00f6sche fangen < Vielhuber David","isPartOf":{"@id":"https:\/\/vielhuber.de\/#website"},"datePublished":"2018-05-23T22:46:51+00:00","dateModified":"2018-05-24T22:45:08+00:00","description":"Ein Frosch springt auf dem Zahlenstrahl umher und man versucht ihn zu fangen. Dabei wechseln sich Springen und Fangen stets ab. Der Frosch startet an","breadcrumb":{"@id":"https:\/\/vielhuber.de\/blog\/froesche-fangen\/#breadcrumb"},"inLanguage":"de","potentialAction":[{"@type":"ReadAction","target":["https:\/\/vielhuber.de\/blog\/froesche-fangen\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/vielhuber.de\/blog\/froesche-fangen\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/vielhuber.de\/"},{"@type":"ListItem","position":2,"name":"Fr\u00f6sche fangen"}]},{"@type":"WebSite","@id":"https:\/\/vielhuber.de\/#website","url":"https:\/\/vielhuber.de\/","name":"Vielhuber David","description":"Full-Stack Developer","publisher":{"@id":"https:\/\/vielhuber.de\/#\/schema\/person\/64d4ff14713d413ea4d9b210d0c2c6ef"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/vielhuber.de\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"de"},{"@type":["Person","Organization"],"@id":"https:\/\/vielhuber.de\/#\/schema\/person\/64d4ff14713d413ea4d9b210d0c2c6ef","name":"David","image":{"@type":"ImageObject","inLanguage":"de","@id":"https:\/\/vielhuber.de\/wp-content\/uploads\/about.jpg","url":"https:\/\/vielhuber.de\/wp-content\/uploads\/about.jpg","contentUrl":"https:\/\/vielhuber.de\/wp-content\/uploads\/about.jpg","width":700,"height":552,"caption":"David"},"logo":{"@id":"https:\/\/vielhuber.de\/wp-content\/uploads\/about.jpg"},"sameAs":["https:\/\/x.com\/vielhuber"]}]}},"_links":{"self":[{"href":"https:\/\/vielhuber.de\/xh\/wp-json\/wp\/v2\/posts\/1921","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/vielhuber.de\/xh\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/vielhuber.de\/xh\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/vielhuber.de\/xh\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/vielhuber.de\/xh\/wp-json\/wp\/v2\/comments?post=1921"}],"version-history":[{"count":42,"href":"https:\/\/vielhuber.de\/xh\/wp-json\/wp\/v2\/posts\/1921\/revisions"}],"predecessor-version":[{"id":2126,"href":"https:\/\/vielhuber.de\/xh\/wp-json\/wp\/v2\/posts\/1921\/revisions\/2126"}],"wp:attachment":[{"href":"https:\/\/vielhuber.de\/xh\/wp-json\/wp\/v2\/media?parent=1921"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/vielhuber.de\/xh\/wp-json\/wp\/v2\/categories?post=1921"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/vielhuber.de\/xh\/wp-json\/wp\/v2\/tags?post=1921"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}