Wie heute morgen schon angedroht hab ich hier nochmal ein kleines
Rätselchen, welches mir letztendlich meine Mittagspause geraubt hat :)
---
Ihr steht vor einem 100-stöckigen (für die Harten unter euch:
n-stöckigen) Hochhaus und habt ein Säckchen voll Murmeln. Ihr möchtet
herausfinden aus welchem Stock ihr die Murmeln maximal werfen könnt ohne
dass sie zerbersten. Dazu wollt ihr aber maximal 2 Murmeln opfern.
Wieviel Versuche braucht man minimal mindestens um eine sichere Antwort
geben zu können?
Wie sähe eine Strategie aus um die Worst-Case Versuchsanzahl zu
minimieren?
---
Beispielstrategie um den Sachverhalt zu veranschaulichen: Ich beginne im
ersten Stock und gehe immer einen Stock nach oben bis eine Murmel
kaputtgeht.
Worst-Case: 100 Versuche (die Murmel überlebt auch Etage 100)
Sukzessive Approximation.
Scheitert aber an der Suche nach der weggerollten Murmel (==> es sind
mehr als 2 Murmeln notwendig) und wegen des Polizeieinsatzes.
Variante 1:
Murmel Nr.1 aus dem 100. Stock werfen. Überlebt sie, genügt der eine
Versuch. Ansonsten mit der zweiten Murmel von ganz unten anfangen.
best case 1 Versuch, worst case 100 Versuche.
Variante 2:
Murmel Nr.1 aus dem 50. Stock werfen. Im Überlebensfall nach oben
vorarbeiten. Ansonsten mit der zweiten Murmel von ganz unten anfangen.
best case 2 Versuche, worst case 51 Versuche.
Icke ®. schrieb:> Variante 2:> Murmel Nr.1 aus dem 50. Stock werfen. Im Überlebensfall nach oben> vorarbeiten. Ansonsten mit der zweiten Murmel von ganz unten anfangen.> best case 2 Versuche, worst case 50 Versuche.
Diese Variante kann man noch optimieren, in dem man die erste Murmel aus
dem 33 Stock wirft. Geht sie kaputt, fängt man mit der anderen von ganz
unten an. Bleibt sie ganz, wirft man sie aus dem 66.
Im worst case also 34 Versuche.
Ich würde von unten Anfangen und alle 10 Stockwerke eine Murmel fallen
lassen.
Wenn die Mumel bei einem Stockwerk kaputt gehen sollte, dann nehme ich
die zweite Murmel und Taste mich vom letzten Zehnerstockwerk in
einser-Schritten weiter. Wenn dann die zweite Murmel kaputt geht, weiss
ich genau welches Stockwerk es ist.
Wenn ich mich nicht verhauen habe sind 19 Würfe der worst case.
Ich sehe aber ein Problem mit der Intervallhalbierung.
Angenommen nur im ersten und zweiten Stock bleibt die Murmel ganz, dann
habe ich mehr kaputt gemacht, bis ich die Lösung hätte...
edit
oh hab was überlesen, hat keinen Bezug auf die Vorherigen Varianten,
aber Intervallhalbierung ist trotzdem doof ;)
John Drake schrieb:> Was stört euch an den schon genannten (implizit - aber welcher Ingenieur> kennt die Arbeitsweise von ADC nicht?) 7 Versuchen?
Nichts stört daran, aber kannst du auch eine Strategie liefern die das
leistet und nicht gegen die Voraussetzungen verstößt?
Ansonsten habe ich schon 19 gelesen, wer bietet weniger? :)
D. I. schrieb:> Ansonsten habe ich schon 19 gelesen, wer bietet weniger? :)
14
Wenn man die Abstände zwischen den Stockwerken, aus denen man die Murmel
zunächst fallen lässt, nicht konstant wählt, sondern absteigend (14.,
27., 39,...).
J.-u. G. schrieb:> D. I. schrieb:>> Ansonsten habe ich schon 19 gelesen, wer bietet weniger? :)>> 14>> Wenn man die Abstände zwischen den Stockwerken, aus denen man die Murmel> zunächst fallen lässt, nicht konstant wählt, sondern absteigend (14.,> 27., 39,...).
Jup das ist korrekt.
Yalu X. schrieb:> @D. I.:>> Klasse Rätsel! Wo nimmst du die Dinger immer nur her?
Internet und Bücher :) Naja ums etwas zu präziser auszudrücken: Im
wesentlichen Artikel, Literatur, Erfahrungsberichte, etc. die sich unter
anderem damit beschäftigen was einem in großen US IT Unternehmen so in
Vorstellungsgesprächen unter die Räder kommt.
Und da ich viele davon selbst erst das erste Mal gehört habe und ich
auch regelmäßiger Konsument dieses Forums bin, ist es oft so, dass die
meisten von euch sie auch noch nicht kennen. Ich finds interessant auf
was für unterschiedliche Ansätze die Leute kommen und in letzter Instanz
dann immer deine mathematischen Begründungen. ;)
Dir würd ich blindlings zutrauen, dass du ohne weiteres den technisch /
algorithmischen Part solcher Interviews wuppen würdest.
Das von gestern und heute waren aus der Reihe "15 BANNED Google
Interview Questions That Will Make You Feel Stupid"
Die Rätsel die ich vor geraumer Zeit mal gestellt habe kamen mir während
des Studiums so entgegen. Z.B. das mit dem Hüteratespiel ;)
Mike Mike schrieb:> Würde es dir was aus machen, noch ein paar mehr Rätsel online zu> stellen? Ich finde die sehr spannend!
Ne macht mir nix aus ;) Ein paar Alte kannste auch noch finden wenn du
Off-topic nach meinem Nick und irgendwas mit rätsel suchst oder so.
Aber hier hab ich noch nen Low-Brainer als Absacker:
Gegeben ist ein 8x8 Schachbrett bei dem 2 gegenüberliegende Ecken
herausgeschnitten werden. Ist es möglich das Brett mit 31 Dominosteinen
(2x1 Größe) zu bedecken, so dass alle Felder bedeckt sind? Wenn ja gib
ne Konfiguration an, wenn nein warum nicht?
@Yalu: Ich hätte da noch ein relatives heftiges Programmierproblem an
dem ich selbst noch hadere, Interesse? (Die Knoblerehre gebietet es mir
nicht in die Musterlösung zu schauen...)
Edit: Falls es auch andere interessiert:
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=528&page=show_problem&problem=3914
Also ich denke jetzt mal, ich muss das nicht unbedingt mit einem 8x8
Feld machen,
da ich theoretisch gesehen die Mitte mit einem rechteckigen Klotz füllen
könnte.
Könnte aber jetzt schon ein Denkfehler sein.
Wenn ich das ganze mit einem 4x4 Feld versuche, bleibt bei jeder
Möglichkeit immer ein "T" Stück übrig, also sage ich mal es geht nicht.
Mike Mike schrieb:> Wenn ich das ganze mit einem 4x4 Feld versuche, bleibt bei jeder> Möglichkeit immer ein "T" Stück übrig, also sage ich mal es geht nicht.
Kannst dus auch stichhaltig begründen? Denn nur weil es für 4x4 nicht
geht, induziert ja nicht zwingend, dass es nicht für 8x8 oder 1000x1000
gehen könnte.
Meine Überlegung ist:
Egal wie ich eine Wand fülle (wegen der ungeraden Blockzahl), es
beeinflusst die nebenliegenden Seiten so, dass es "nicht aufgeht", das
heißt, es bleibt immer ein 1x1 Feld, das ja irgendwie auch abgedeckt
werden will.
Lege ich nun einen Block drauf, sorgt es wiederum dafür, dass ich
irgendwann wieder bei einem 1x1 Block lande. Solange, bis eben zwei 1x1
Felder übrig bleiben, die sich Diagonal gegenüberliegen.
Ich arbeite an etwas Stichhaltigem, lass mir noch bisschen zeit ;)
Ich habe es!
Ein Dominostein wird auf das Schachbrett gelegt.
Egal wie ich ihn lege, die eine Hälfte liegt auf einem schwarzem Feld
und die andere auf einem weißen!
Und genau da ist der Knackpunkt. Die Beiden Felder die an den Ecken
entfernt werden, haben die gleiche Farbe. D.h. genau, das eben zwei
gleichfarbige Felder übrigbleiben, und da kann ich keinen Dominostein
drauflegen, da ein Dominostein auf zwei verschiedenfarbigen Feldern
liegen muss.
Sehr gut, so ist es. :)
"Der stolze Moment bei dem man selbstständig auf eine Lösung kommt"
Wenn du jetzt noch 5 handelsübliche Würfel so aufeinander stapelst, dass
die Summe der Augenzahlen auf allen 4 Säulenseiten gleich ist, dann kann
mas für heute gut sein lassen :)
Eher der Moment in dem man sich auf die Stirn klatscht, weil es so
trivial ist.
Habe verschiedene Ansätze gehabt, mit verschiedenen Anordnungen der
Steine und habe damit versucht zu beweisen, warum es nicht "aufgeht".
Aber jetzt bin ich schlauer ;)
edit
Rätzel in Arbeit, moment
Wenn ich mich nicht verrechnet habe, geht das glaube ich nicht.
Wir sehen uns eine Seite an.
Die Obere Würfelzahl wäre a, die nächste b, bis zur letzten, e.
Dann wäre die Summe a+b+c+d+e
Jeweils gegenüberliegende Würfelzahlen haben den Wert 7-Augenzahl
D.h. wir haben die Gleichung
1
a+b+c+d+e=7-a+7-b+7-b+7-c+7-d+7-e
2
3
a+b+c+d+e=-a+-b+-b+-c+-d+-e+35
4
5
2*(a+b+c+d+e)=35
6
7
a+b+c+d+e=17,5
Da Augenzahlen und damit auch die Summer der Augenzahlen nur ganze
Zahlen sein können, geht es nicht!
Jawohl, genug für heute.
Wenn mir wieder eins in die Finger kommt werde ich das Forum nochmal
malträtieren.
Ansonsten kannst du dich ebenfalls an der Programmieraufgabe versuchen.
D. I. schrieb:> Ansonsten kannst du dich ebenfalls an der Programmieraufgabe versuchen.
hab grad versucht mich anzumelden, aber ich krieg keine mail von denen.
Im Spamfilter isses auch nicht hängen geblieben. Habs auch mit 2
unterschiedlichen Mai-Accounts probiert.
Wollte eigentlich nur versuchen rauszufinden, in welchen Sprachen man
die Lösuingen Posten kann.
An sich klingt das nich so wahnsinnig kompliziert.
Aufhänger sind die Schwarzen Ecken.
Ich würde durch das Feld gehen und schauen, wie viele korrekte
Möglichkeiten es für jedes schwarze Feld gibt, das Teil zu plazieren.
Die Felder mit 1 können direkt entfernt werden.
Das ganze solange wiederholen (Wiederholung jeweils auf direkt
beeinflusste Umgebung beschränken), bis keine mehr entfernt werden
können.
irgenwdwann wird man raten müssen. weiter also per Backtracking.
Aktuelles Feld und Entscheidung auf einen Stack und rechnen. Im
Fehlerfall letzte Entscheidung vom Stack herstellen und einen anderen
Weg ausprobieren.
Gibts da Speicherbeschränkungen?
in simplester Implementierung schlägt ein Speicherstand mit 250.000B zu
Buche. Ist schon recht viel.
Optimieren ließe sich das auf 62.500 (2bit pro feld, 4 pro Byte) oder
mit extrem ekligen Zugriffen 50.000 (5 Felder pro Byte).
Für eine Speicherung und zum nicht drauf arbeiten ist es aber fast egal.
Theoretisch könnte man hier noch weiter komprimieren, da die weißen
Felder weniger Information tragen, als schwarz oder leer.
Als Quickcheck könnte man schauen,
- ob es genau doppelt so viele weiße wie schwarze gibt
- ob an jedes weiße mindestens 1 schwarzes (4er nachbarschaft) angrenzt
- ob an jedes schwarze mindestens 2 (4er nachbarschaft) weiße
angrenzen
- ob es nicht mehr als 2 aufeinanderfolgende schwarze gibt (hor und
vert).
Ich vermute das Feld sollte sich relativ schnell ausdünnen.
bin aber zu faul, das jetzt zu implementieren.
kannst du es ja mal den Rahmen (also das einparsen und grundlegendste
Feld-Struktur) posten.
Vlad Tepesch schrieb:> hab grad versucht mich anzumelden, aber ich krieg keine mail von denen.> Im Spamfilter isses auch nicht hängen geblieben.
Ach, du auch nicht? Dann liegt's also nicht daran, dass ich mich evtl.
bei der E-Mail-Adresse vertippt habe.
> Wollte eigentlich nur versuchen rauszufinden, in welchen Sprachen man> die Lösuingen Posten kann.
Es scheinen die gleichen wie bei http://uva.onlinejudge.org zu sein.
Dort sind wählbar:
1
- ANSI C 4.5.3 - GNU C Compiler with options: -lm -lcrypt -O2 -pipe -ansi -DONLINE_JUDGE
2
3
- JAVA 1.6.0 - Java Sun JDK
4
5
- C++ 4.5.3 - GNU C++ Compiler with options: -lm -lcrypt -O2 -pipe -DONLINE_JUDGE
6
7
- PASCAL 2.4.0 - Free Pascal Compiler
> Die Felder mit 1 können direkt entfernt werden.> irgenwdwann wird man raten müssen. weiter also per Backtracking.> Ich vermute das Feld sollte sich relativ schnell ausdünnen.
Ich schätze, das hat D. I. auch schon probiert. Wenn aber bei den über
500²/3 möglichen schwarzen Feldern nur jedes 1000ste nicht direkt ent-
fernt werden kann, müssen mehr als 10²⁴ Varianten durchprobiert werden.
Vlad Tepesch schrieb:> hab grad versucht mich anzumelden, aber ich krieg keine mail von denen.> Im Spamfilter isses auch nicht hängen geblieben. Habs auch mit 2> unterschiedlichen Mai-Accounts probiert.Yalu X. schrieb:> Ach, du auch nicht? Dann liegt's also nicht daran, dass ich mich evtl.> bei der E-Mail-Adresse vertippt habe.
Habe es gerade eben auch mal mit meiner gmail-Adresse versucht und
sofort den Link per Mail erhalten. Vielleicht gabs in der Nacht ein
Problem? Auf jeden Fall kann man resend machen, dann sollte sie kommen.
Titel: "ACM-ICPC Live Archive - Your Registration is Pending Approval"
und nach klicken vom Link
Titel: "ACM-ICPC Live Archive - New User Details"
Yalu X. schrieb:> Ich schätze, das hat D. I. auch schon probiert. Wenn aber bei den über> 500²/3 möglichen schwarzen Feldern nur jedes 1000ste nicht direkt ent-> fernt werden kann, müssen mehr als 10²⁴ Varianten durchprobiert werden.
Bei 500x500 brauch ich den Ansatz nicht mal probieren um zu wissen, dass
das nicht klappen wird :) Mein bisheriger Ansatz war bipartites Matching
/ maximaler Fluss, aber das gab Time-Limit was bei sovielen Knoten
leider fast schon klar war >.<
Yalu X. schrieb:> Es scheinen die gleichen wie bei http://uva.onlinejudge.org zu sein.> Dort sind wählbar:
Das stimmt, ist dasselbe System, im Live Archive landen allerdings nur
die Aufgaben der vergangenen ICPC Regionals und World Finals.
