Hallo,
ich schnibbel gerade Marker für einen Prototypen und hab mir dabei dieses Rätsel ausgedacht. Ich glaube die Lösung zu kennen:
Gegeben ist ein Rechteckiges Raster voller quadratischer, gleich großer Counter. Die Counter sind regelmäßig angeordnet, d.h. wir haben gerade Schnittlinien und in jeder Zeile und Spalte sind gleich viele Counter (z.B. 7x7 oder 12 x3).
Ich kann nicht gut um die Ecke schneiden, also schneide ich immer eine ganze Spalte oder eine ganze Reihe, bis ich eine Zeile mit Countern habe, die ich dann einzelnd abschneide.
Was ist die effizienteste Methode (also die mit den wenigsten Schnitten) und wie viele Schnitte benötigt die?
Gibt es unterschiedliche Methoden für unterschiedliche Größen oder für Quadrate/Rechtecke die keine Quadrate sind?
Jeweils mit Beweis bitte!
Bei einem 2x2-Raster ist die Sache natürlich klar: Ich kann die mittlere Reihe oder die mittlere Spalte zuerst durchschneiden und habe dann 2 2er-Reihen die ich jeweils mit einem Schnitt durchschneide um die 4 Counter auszuschneiden.
Nur so als Beispiel...
ciao
peer
Counter schnibbel Rätsel
-
Christian Fechner
Re: Counter schnibbel Rätsel
Hallo,
ich glaube, das ist nicht allzu schwer, solange es nicht erlaubt ist, mehrere Schichten aufeinanderzulegen:
Es ist vollkomen egal, in welcher Reihenfolge man die Schnitte macht, man benötigt bei x Spalten und y Reihen immer x*y-1 Schnitte.
Beweis per vollständiger Induktion:
IA: x=1, y=1 => x*y-1=0, korrekt da 1 Counter nicht mehr ausgeschnitten werden muss
IS: (wegen Symmetrie reicht der Schritt für x=>x+1)
#Schnitte(x+1,y)
= (wegen Symmetrie reicht es, die Unterteilung der x Reihen zu betrachten)
min_{über alle t, 0<1= (IV)
(x+1-t)*y-1+t*y-1
=(x+1)*y-1
q.e.d.
ich glaube, das ist nicht allzu schwer, solange es nicht erlaubt ist, mehrere Schichten aufeinanderzulegen:
Es ist vollkomen egal, in welcher Reihenfolge man die Schnitte macht, man benötigt bei x Spalten und y Reihen immer x*y-1 Schnitte.
Beweis per vollständiger Induktion:
IA: x=1, y=1 => x*y-1=0, korrekt da 1 Counter nicht mehr ausgeschnitten werden muss
IS: (wegen Symmetrie reicht der Schritt für x=>x+1)
#Schnitte(x+1,y)
= (wegen Symmetrie reicht es, die Unterteilung der x Reihen zu betrachten)
min_{über alle t, 0<1
(x+1-t)*y-1+t*y-1
=(x+1)*y-1
q.e.d.
-
peer
Saubere Lösung!
Hi,
Christian Fechner schrieb:
>
> Hallo,
>
> ich glaube, das ist nicht allzu schwer, solange es nicht
> erlaubt ist, mehrere Schichten aufeinanderzulegen:
>
> Es ist vollkomen egal, in welcher Reihenfolge man die
> Schnitte macht, man benötigt bei x Spalten und y Reihen immer
> x*y-1 Schnitte.
>
> Beweis per vollständiger Induktion:
>
> IA: x=1, y=1 => x*y-1=0, korrekt da 1 Counter nicht mehr
> ausgeschnitten werden muss
>
> IS: (wegen Symmetrie reicht der Schritt für x=>x+1)
> #Schnitte(x+1,y)
> = (wegen Symmetrie reicht es, die Unterteilung der x Reihen
> zu betrachten)
> min_{über alle t, 0<1> = (IV)
> (x+1-t)*y-1+t*y-1
> =(x+1)*y-1
>
> q.e.d.
Lösung natürlich korrekt, auch wenn ichs etwas anschaulicher bewiesen habe ;-)
ciao
peer
Christian Fechner schrieb:
>
> Hallo,
>
> ich glaube, das ist nicht allzu schwer, solange es nicht
> erlaubt ist, mehrere Schichten aufeinanderzulegen:
>
> Es ist vollkomen egal, in welcher Reihenfolge man die
> Schnitte macht, man benötigt bei x Spalten und y Reihen immer
> x*y-1 Schnitte.
>
> Beweis per vollständiger Induktion:
>
> IA: x=1, y=1 => x*y-1=0, korrekt da 1 Counter nicht mehr
> ausgeschnitten werden muss
>
> IS: (wegen Symmetrie reicht der Schritt für x=>x+1)
> #Schnitte(x+1,y)
> = (wegen Symmetrie reicht es, die Unterteilung der x Reihen
> zu betrachten)
> min_{über alle t, 0<1
> (x+1-t)*y-1+t*y-1
> =(x+1)*y-1
>
> q.e.d.
Lösung natürlich korrekt, auch wenn ichs etwas anschaulicher bewiesen habe ;-)
ciao
peer
-
Andreas Last
Re: Saubere Lösung!
Dafür wird Christian weniger Bäume verbraucht haben :-P
Andreas (der die VI noch nie gebacken bekommen hat)
Andreas (der die VI noch nie gebacken bekommen hat)
Wer ist online?
Mitglieder in diesem Forum: 0 Mitglieder und 23 Gäste