Lösung Variante 2
Hallo,
und hier noch mein Vorschlag für Variante 2:
Eine Gewinnsituation liegt genau dann vor, wenn die Zahl n gerade ist und n sich nicht darstellen lässt als n=2^k mit k ungerade (D.h. n verliert, falls n ungerade ist oder wenn n eine Zweierpotenz ist mit ungeradem Exponenten).
Beweis durch vollständige Induktion:
Sei M die Menge aller derjenigen natürlichen Zahlen n, für die die Menge N(n)={1,2,3,…,2*n) die Eigenschaft hat, dass in ihr alle ungeraden Zahlen sowie alle Zweierpotenzen mit ungeradem Exponenten verlieren und alle geraden Zahlen gewinnen, die keine Zweierpotenzen mit ungeradem Exponenten sind.
Dann lautet meine Behautung: M=Menge der natürlichen Zahlen.
Schritt 1:
1 ist ungerade und 1 verliert, denn es gibt keinen zulässigen Teiler.
2 ist eine Zweierpotenz mit ungeradem Exponenten und 2 verliert, denn es gibt auch hier keinen zulässigen Teiler.
Somit ist 1∈M.
Schritt 1:
Sei n∈M. Ich zeige nun, dass dann auch n+1∈N gilt.
Zunächst wird 2*n+1 untersucht. Es muss ein Teiler m abgezogen werden, der größer als 1 und kleiner als 2*n+1 ist. Da 2*n+1 ungerade ist, ist m ebenfalls ungerade und d=2*n+1-m ist gerade. d ist zwar gerade, kann aber keine Zweierpotenz sein, was man wie folgt sieht: Da m ein echter Teiler von 2*n+1 ist, ist m auch ein echter Teiler von d=2*n+1-m. Wäre nun d eine Zweierpotenz, so müsste m ein echter Teiler einer Zweierpotenz sein, also wäre m gerade. Als Teiler der ungeraden Zahl 2*n+1 ist m aber ungerade. d ist also eine gerade Zahl, die nicht Zweierpotenz ist, also erst recht nicht Zweierpotenz mit ungeradem Exponenten. Somit ist d eine Gewinnzahl für den Gegner und 2*n+1 eine Gewinnzahl für mich.
Jetzt wird 2*n+2 untersucht. Hierbei sind 3 Fälle zu unterscheiden.
i) 2*n+2 ist Zweierpotenz mit ungeradem Exponenten
ii) 2*n+2 ist Zweierpotenz mit geradem Exponenten
iii) 2*n+2 ist keine Zweierpotenz.
Zu i) 2*n+2 hat nur gerade Teiler m, also ist d=2*n+2-m gerade. Da 2*n+2 eine Zweierpotenz ist, ist d genau dann eine Zweierpotenz, wenn m=n+1 ist. Für m≠n+1 ist d also eine gerade Zahl, die nicht Zweierpotenz ist. Für m=n+1 ist d zwar eine Zweierpotenz, aber der Exponent ist gerade, da 2*n+2=2*(n+1) eine Zweierpotenz mit ungeradem Exponenten ist. Egal welchen Zug ich ziehe, die Zahl d ist immer eine gerade Zahl, die keine Zweierpotenz mit ungeradem Exponenten ist. Wegen n∈M, führt also jeder legale Zug zu einer Gewinnsituation des Gegners und somit ist 2*n+2 eine Verlustzahl.
Zu ii) m=n+1 ist Teiler von 2*n+2, also kann ich den Zug d=2*n+2-m=n+1 ziehen. Da 2*n+2 eine Zweierpotenz mit geradem Exponenten ist, ist n+1 eine Zweierpotenz mit ungeradem Exponenten. Also habe ich mit d einen Zug gefunden, bei dem mein Gegner eine Verluststellung vorfindet (beachte n∈M). Also ist 2*n+2 eine Gewinnzahl.
Zu iii) Da 2*n+2 keine Zweierpotenz ist, gibt es einen ungeraden Teiler m, so dass d=2*n+2-m ungerade ist. Wegen n∈M führt somit d zu einer Verluststellung für meinen Gegner, also ist 2*n+2 eine Gewinnzahl.
Insgesamt habe ich also für 2*n+2 gezeigt, dass 2*n+2 eine Gewinnzahl ist, wenn sie keine Zweierpotenz mit ungeradem Exponenten ist. Also ist n+1∈M.
Schritt 3:
In Schritt 1 habe ich gezeigt, dass 1∈M.
In Schritt 2 habe ich gezeigt, dass n∈M impliziert, dass auch n+1∈&M gilt.
Nach dem Prinzip der vollständigen Induktion sind also M und die Menge der natürlichen Zahlen identisch.
w.z.b.w.
Viele Grüße
Jens
P.S. Wer meine Behauptung (trotz Beweis) nicht glaubt, kann ja folgendes c++ Programm compilieren und ausführen. Es berechnet für alle natürlichen Zahlen n∈{1,…,N}, ob n eine Gewinnzahl (1) oder eine Verlustzahl (0) ist.
#include
using std::cout;
using std::cin;
using std::endl;
#include
using std::vector;
void check(vector& field, long int n);
void show(vector field);
int main(void)
{
bool weiter=false;
do
{
long int N=0;
cout \> N;
if ( weiter = (N != 0) );
{
vector field;
for (long int n=1; n& field, long int n)
{
bool victory=false;
for (long int teiler=2; teiler field)
{
long int n=0;
for ( vector::iterator i = field.begin(); i != field.end(); i++ )
cout
