Schachrätsel

Wie holt Weiß am Zug hier den entscheidenden Vorteil?

-- Birgit

Spot the difference

Exactly one of the employees of the real estate company in the link below is a programmer. Can you spot him?

http://www.deansproperty.com.au/Home/Profiles

kR Birgit

Mathematik-Übungen

Ein McDonalds in Tiengen hat am 27.05.2010 folgende Preistabelle (leicht gekürzt) für Getränke aushängen:

	0.25l	0.4l	0.5l
Cola	1.10€	1.79€	2.39€
Orangensaftgetränk	1.79€	2.19€	2.49€

a) Man berechne im Kopf (bzw. schätze ab), welche Größe bei Cola das beste Preis-Leistungs-Verhältnis hat.

b) Timo hat großen Durst und möchte deshalb genau 2.65l trinken. Was ist die günstigste Kombination von Bechergrößen, wenn er Cola bzw. Orangensaftgetränk trinken will?

lG Birgit

Spieltheorie @ Stargate Universe

SPOILER ALERT

Ein kleines spieltheoretisches Gedankenexperiment, aus der letzten Folge von Stargate Universe (1.13 "Faith"):

Gegeben: Ein großes Raumschiff mit zwei Shuttles, eines davon beschädigt. Die beiden Shuttles können auf Planeten landen, das große Schiff nicht. Es gibt keine anderen Möglichkeiten, zwischen Schiff und Planet zu reisen.

Etwa 15 Leute, sowohl Zivilisten als auch Militärpersonal, sind mit dem intakten Shuttle zu einem Planeten geflogen. Es gefällt ihnen dort so gut, dass sie bleiben möchten. Allerdings muss das große Raumschiff bald weiterreisen, und fliegt dabei so schnell, dass die Shuttles dann nicht mehr nachkommen könnten. Eine spätere Rückkehr des großen Schiffes zum Planeten ist höchst unwahrscheinlich, Hilfe von außen ebenso. Sobald das große Schiff weiterfliegt, wären alle auf dem Planeten also dauerhaft dort gestrandet. Ebenso wären aus Sicht des Raumschiffes alle dort zurückbleibenden Personen, Shuttles und Vorräte dauerhaft verloren.

Der Commander (namens Young) des Raumschiffes will die auf dem Planeten verbliebenen Leute (oder zumindest einen Teil davon) sowie das intakte Shuttle wieder zurückholen, notfalls mit Gewalt. Andererseits will er denen, die wirklich zurückbleiben wollen, helfen, indem er ihnen das beschädigte Shuttle überlässt, das zwar gerade noch zum Planeten fliegen kann und dort auch in Bodennähe herumfliegen könnte, von dort aber wegen der beschädigten Antriebe vermutlich nicht mehr zurückkehren könnte. (Noch ist das defekte Shuttle im Hangar des Raumschiffes, mit mäßigen Chancen auf vollständige Reparatur.)


"Lösung" in der Serie: Young fliegt mit dem beschädigten Shuttle zum Planeten und schlägt den Zurückbleibenden dort vor, ihnen das defekte Shuttle zu überlassen, während er mit dem intakten Shuttle und den restlichen Leuten zum Raumschiff zurückfliegt. Es entsteht folgendes Gespräch:
YOUNG: "Ich werde Ihnen das [beschädigte] Shuttle nur unter einer Bedingung überlassen: Das gesamte militärische Personal kehrt mit mir zum Raumschiff zurück. Wenn Sie meinen Vorschlag ablehnen, werden wir Sie alle zurückbringen, und zwar mit Gewalt."
ZIVILIST: "Das können Sie nicht tun!"
YOUNG: "Darauf sollten Sie es lieber nicht ankommen lassen."

So. Es gibt einen selbstgebackenen Gugelhupf für denjenigen oder diejenige, der/die mir als erster antwortet, was die zwei bis drei ganz groben Schnitzer in Youngs Überlegung sind.

lG Birgit

Millionenfrage

Welches österreichische Bundesland hat die oben abgebildete Flagge, bestehend aus einem weißen und einem roten Streifen, wobei der rote Streifen unten ist?
A) Salzburg
B) Tirol
C) Vorarlberg
D) Wien

lG Birgit

Millionenfrage

Welcher der folgenden FPÖ- bzw. BZÖ-Politiker trug bei seiner Geburt den Familiennamen Hojač?
A) Peter Westenthaler
B) Uwe Scheuch
C) Heinz-Christian Strache
D) Martin Graf

lG Birgit

P.S.: Alle Informationen von der deutschsprachigen Wikipedia.

Millionenfrage

Welche Stadt hat die meisten Bezirke?
A) Graz
B) Wien
C) München
D) Berlin

lG Birgit

Millionenfrage

Welches der folgenden Chinesischen Tierkreiszeichen ist nicht Yang zugeordnet?
A) Schlange
B) Tiger
C) Drache
D) Hund

Welches der folgenden Chinesischen Tierkreiszeichen ist nicht Feuer zugeordnet?
A) Schlange
B) Pferd
C) Schaf
D) Drache

lG Birgit

Millionenfrage

Millionenfragen des Tages:
(Wikipedia-Joker ist unfair, und bei der deutschsprachigen Wikipedia sogar nutzlos)

Was ist eine Beerenart?
A) Brombeere
B) Erdbeere
C) Stachelbeere
D) Himbeere
E) Preiselbeere
F) Blaubeere

Was ist keine Beerenart?
A) Paradeiser (Tomaten)
B) Melanzani (Aubergine, Eierfrucht)
C) Weintrauben
D) Banane
E) Granatapfel
F) Paprika
G) Kürbis

lG Birgit

Millionenfrage

Millionenfrage des Tages:
(Wikipedia-Joker ist unfair)

Welche der folgenden bekannten Personen ist nicht an AIDS gestorben?
A) Rock Hudson (Schauspieler)
B) Ronald Reagan (Politiker)
C) Freddy Mercury (Sänger)
D) Isaac Asimov (Schriftsteller)

lG Birgit

Millionenfrage

Millionenfrage des Tages:
(Es werden nur Tipps vor Einsatz des Wikipedia-Jokers angenommen. ;) )

Wie wird bei einer Schisprungschanze die Hillsize (bzw. Schanzengröße) festgelegt?
A) Wendepunkt der Landebahn
B) Punkt, an dem die Landebahn genau 32° Gefälle hat
C) Wird von einer Jury festgelegt
D) Größte auf der Schanze jemals gesprungene Weite

lG Birgit

Kuhhandel-Probleme

Vorbemerkung: 0 ist in diesem Artikel keine natürliche Zahl, und alle Teilmengen sind nicht-leer.

Gewisse Aspekte von "Kuhhandel" lassen sich folgendermaßen vereinfacht darstellen:

Es gibt 10 Karten: A, B, C, D, E, F, G, H, I, K. Jede dieser Karten hat einen Wert. (Im Originalspiel: 10, 40, 90, 160, 250, 350, 500, 650, 800, 1000.) Am Ende des Spieles hat jeder Spieler einige dieser 10 Karten. Die Punkte für den Spieler ergeben sich nun aus (Summe der Kartenwerte) * (Anzahl der Karten).

Beispiel:

• Birgit hat B (40) und F (350). Punkte: (40 + 350) * 2 = 780.
• Martin hat A (10), C (90) und E (250) Punkte: (10 + 90 + 250) * 3 = 1050.

Ein weiteres Beispiel:

• Birgit hat C (90) und D (160). Punkte: (90 + 160) * 2 = 500.
• Martin hat G (500). Punkte: (500) * 1 = 500.

Wie wir im zweiten Beispiel sehen, kann es bei diesen Kartenwerten also ein Unentschieden geben.

Fragestellung

Man finde Werte für die 10 Karten, sodass kein Unentschieden möglich ist und der höchste Wert minimal ist.

Mathematisch formuliert: Man finde eine 10-elementige Menge natürlicher Zahlen mit möglichst kleinem maximalen Element, die folgende Bedingung erfüllt: Es existieren keine zwei disjunkten Teilmengen, sodass (Anzahl der Elemente in der Teilmenge) * (Summe der Elemente in der Teilmenge) für beide Teilmengen dasselbe Ergebnis liefert.

Oder: Man finde eine 10-elementige Menge natürlicher Zahlen mit möglichst kleinem maximalen Element, die folgende Bedingung erfüllt: Die Wertigkeiten ((Summe der Elemente) * (Anzahl der Elemente)) von 2 Teilmengen sind höchstens dann gleich, wenn mindestens 1 Element in beiden Teilmengen vorhanden ist.

Hinweis: Es gibt mindestens eine Lösung (1,10,100,1000,...,1000000000), daher muss es auch eine kleinste Lösung geben.

Bekannte [nicht optimale] Lösungen und Nichtlösungen

• 1,10,100,1000,...,1000000000 ist eine Lösung
• 1,2,4,8,...,512 ist keine Lösung: {2,4,16} = 66 = {1,32}
• 1,2,3,5,11,17,31,112,171,326 ist die Greedy-Lösung
• 1,4,6,7,8 ist eine optimale Lösung für n=5
• 1,4,7,12,13,14 ist eine optimale Lösung für n=6
• 1,2,3,13,19,22,25 ist eine optimale Lösung für n=7
• 1,2,3,22,32,38,42,45 ist eine Lösung für n=8
• 1,4,7,23,32,40,41,42 ist eine optimale Lösung für n=8
• 1,2,3,20,43,70,76,79,82 ist eine Lösung für n=9
• 1,2,3,43,61,70,76,79,82 ist eine Lösung für n=9

Verallgemeinerte Fragestellungen

• Man finde Kartenwerte für 10 bzw. n Karten, sodass kein Unentschieden möglich ist und der höchste Kartenwert möglichst klein ist. Und/oder:
• Man finde einen Algorithmus, der obiges Problem (für n=10) in < 24 Stunden berechnet.
• Vermutung (Birgit): Die Fragestellungen (*) und (**) (siehe unten) sind beide NP-vollständig (und folglich die obige erst recht).

(*): Gegeben eine Menge von n Zahlen. Man bestimme, ob es zwei Teilmengen dieser Menge mit gleichem Ergebnis ((Summe der Elemente) * (Anzahl der Elemente)) gibt.

(**): Für eine Zahl n bestimme man die kleinste Zahl Z(n), für die eine Menge von n natürlichen Zahlen existiert mit Z(n) als größter Zahl, sodass in der Menge keine Teilmengen mit gleichem Ergebnis ((Summe der Elemente) * (Anzahl der Elemente)) existieren.

(Problem posed by: Martin Windischer)

lG Birgit

Mystische Linien -- Auflösung

(Auflösung zu diesem Rätsel.)

Es handelt sich um die Trans Austria Gasleitung, eine Pipeline, deren genauer Verlauf auch hier zu sehen ist.

lG Birgit

Mystische Linien

Nicht nur bei Nazca gibt es mystische Linien, nein, auch mitten in der Steiermark findet man am Satellitenbild eine seltsame Linie. Auf der unten verlinkten Karte bei Google Maps habe ich diese einmal grob nachgezeichnet (allerdings um etwa 200m versetzt um die eigentliche Linie nicht zu überdecken). Außerdem habe ich einige besonders deutliche Stellen markiert.

Rätsel des Tages: Wos is des?

Antworten/Lösungsversuche erwünscht.
(Auflösung nächsten Montag.)

Karte:
http://maps.google.com/maps/ms?ie=UTF8&hl=en&t=k&msa=0&msid=114373892293392507762.00047c4ac689d8d885323&ll=47.17004,15.826607&spn=0.357099,0.891953&z=11

lG Birgit

Kleines Wörterbuch Wohnungssuche (Auflösung des Quiz)

(Vor einigen Wochen gab es hier im blog das dazugehörige Quiz.)

Billaggebühr -- Rundfunkgebühr
Cheminee -- Kamin
Estrich-Abteil -- Dachboden-Abteil
Frottierwäsche -- Handtücher / Badetücher
Lavabo -- Waschbecken
Plättliboden -- Fliesenboden
Rechaud -- Herd
Reduit -- Abstellkammer
Tumbler -- Wäschetrockner

(Ursprünglich geposted in meinem privaten Blog am 14.10.2009.)
lG Birgit

Kleines Wörterbuch Wohnungssuche (Quiz)

Auch wenn in der Schweiz offiziell Deutsch gesprochen wird -- für die Wohnungssuche braucht man ein gewisses Grundvokabular. Daher hier das Quiz darüber. (Auflösung folgt.)

Was bedeutet...
... Billaggebühr?
... Cheminee?
... Estrich-Abteil?
... Frottierwäsche?
... Lavabo?
... Plättliboden?
... Rechaud?
... Reduit?
... Tumbler?

(Ursprünglich geposted in meinem privaten Blog am 24.07.2009.)
lG Birgit

Bad Pixel

The equation in this picture is correct, there is only one bad pixel. Which one?

kR Birgit

Fun with Debugging: The Elevator

After some amusing, confusing and somewhat annoying experiences with a very old elevator in the appartment house I'm living in, I've decided to let you join the fun. It took me some time to figure out how that elevator was probably programmed, but I think I by now have a pretty accurate model of how it works. I think it's an excellent example of well-intended programming going horribly wrong and would not want to deprive anyone out there from the chance to learn from it. (Nothing is worthless -- it can still be a bad example.)

Below you will find the details on how the elevator is programmed. Your task: Find as many use cases as possible where the elevator will not do what the user(s) would have expected.

=======================================
Let's assume some parts are implemented in hardware and all parts will work in parallel. The elevator has exactly one variable: destination, denoting the floor the elevator should go to. It furthermore can determine its current position, using a function named getPosition().

Whenever getPosition() != destination, i.e. the elevator is not where it should go to, the engine will move the elevator cabin towards the destination.

The doors are controlled mechanically. They can not be opened automatically (like modern elevator doors), but have to be pushed (or pulled) open manually by the persons using the elevator. The doors can however be locked or unlocked, which will happen semiautomatically. The function lockDoors() will lock all the doors. The function unlockDoors() will unlock the door where the cabin currently is. (That is, if the elevator is in floor 4, the door of floor 4 will be unlocked. If the elevator is not in front of any door, for example after someone pressing the emergency stop, no doors will be unlocked.) Additionally, it is possible to find out if a door is open, using a function isDoorOpen() that will return true if and only if at least one door is open. (Here, "open" means that the door is not only unlocked but also is currently opened.)

All movements of the cabin are therefore solely dependent on destination. An event-based structure will control this variable. There are four possible events:
* onButtonInCabinPressed(floor) will be invoked when a floor button in the cabin has been pressed, where floor denotes the number that was pressed.
* onCallButtonPressed(floor) will be invoked when the button outside the elevator has been pressed to call the elevator. Here, floor denotes the floor where the button was pressed.
* onStopButtonPressed() will be invoked when the emergency stop button in the elevator cabin is pressed.
* onDestinationReached() will be invoked when the cabin reaches its destination, i.e. when the cabin used to be moving because getPosition() != destination, and is not moving any more because the current position now equals the destination.

The first three functions will be called repeatedly as long as the buttons are being pressed. If more than one button is pressed at a time, the stop button will precede the other buttons, and the buttons inside the cabin will precede the call buttons outside.

For the simplicity of the code, let's assume that assert(...) will abort the execution of the called function if the assertion doesn't hold, but will not otherwise influence the state of the elevator.

Further, let's assume all of the following functions are atomical, that is, they will be executed to the end before another function can be executed. Also, the execution of one function will happen so fast that no human can change anything about the state in the meantime, i.e. the result of isDoorOpen() can't change during the execution of one function.

Here is the code for four abovementioned functions and their helper functions:

// Button in cabin has been pressed
onButtonInCabinPressed(floor) {
setDestination(floor);
}

// Call button has been pressed
onCallButtonPressed(floor) {
setDestination(floor);
}

// This function sets the new destination if possible. As both calling
// the elevator and pressing a floor button boil down to setting a new
// destination, we can use the same code for both.
setDestination(newdestination) {
// If the elevator is already moving and we set a new destination,
// it might start moving in the other direction instead of taking
// the people inside the cabin to the floor they wanted to go to.
// For example, if the elevator was moving up from the 2nd floor
// to the 5th, and someone in the 1st floor called the elevator,
// without this check it would turn around and go to the 1st floor.
// We therefore must assure the cabin is currently standing.
assert(getPosition() == destination);

// As soon as we set a new destination, the elevator will start
// moving. If the door is still open at that moment, it will both
// damage the mechanical locking system and endager the people
// currently stepping in or out. We therefore must assure the doors
// are closed before setting a new destination.
assert(!isDoorOpen());

// We've ruled out all the nasty cases, so we can now safely lock
// the doors and set the new destination.
lockDoors();
destination = newdestination;
}

// Someone pressed the emergency stop button in the elevator.
onStopButtonPressed() {
// To stop the elevator, we make it believe it is already exactly
// where it should be.
destination = getPosition();
}

// Elevator cabin reached its destination.
onDestinationReached() {
// We reached the destination, so we can unlock the doors.
unlockDoors();
}

=======================================

Bonus task 1: Find an implementation using also only one variable, but ameliorating as many of the problems of the above solution as possible.

Bonus task 2: Find a solution using at most n+1 variables (where n is the number of floors) that will satisfy most users. (Be aware that a the "normal" solution can't be implemented since there is only one call button per floor.)

Have fun! :)

kR Birgit