Vollständige Induktion Gewichte

Question

Aufgabe:

Mit einem einzigen Gewichtssatz der Form {2^0kg, 2^1kg,..., 2^^(n-1)kg} kann man alle Gewichte 1kg, 2kg, 3kg,...,2^ⁿ -1kg zusammenstellen.

Beweise die Behauptung für alle n Element von N durch vollständige Induktion.

Problem/Ansatz

Zuerst habe ich

A(n): Alle Gewichte g ELement von {1,...,2^ⁿ -1} sind mit einem Gewichtssatz der Form g= ∑xi 2i (unter dem Summenzeichen i=0 und darüber n-1)mit x_i =0 oder 1 darstellbar.

Induktionsanfang

A(1): 2^¹-1=1 und x_i*2¹=2 für x_i =1

Induktionsvoraussetzung

Es sei n eine Zahl für die A(n) stimmt.

Zu zeigen:

g ELement von {1,...,2^ⁿ⁺¹ -1} => g=∑xi 2i (unter dem Summenzeichen i=0 und darüber n)

Nun würde ja der Induktionsschritt kommen, aber mit dem komm ich einfach nicht zurecht, ich dachte an Fallunterscheidung deswegen habe ich xi mit 0 und 1 gewählt.

Answer 1

Fallunterscheidung ist doch OK.

1. Fall g < 2ⁿ . Dann ist das nach Ind.annahme darstellbar, sogar ohne das 2ⁿ kg. Stück zu benutzen.

2. Fall g ≥ 2ⁿ . Dann nehme ich das 2ⁿ kg Stück und muss dann mit den übrigen

das restliche Gewicht von   g -2ⁿ darstellen. Das geht lt. Ind.annahme, da der

Rest weniger als 2ⁿ ist.

Comments

Aber mein Problem ist ich verstehe die Fallunterscheidung einfach nicht. Also ich verstehe noch die Fälle:

1 Fall. g<2ⁿ und auch 2. Fall g>=2ⁿ aber die Begründung, wie ich das beweisen kann versteh ich nicht.

Ich kann auch deiner Antwort oben nicht wirklich folgen, warum das so ist. Kann man das auc vielleicht noch anders erklären?

---

Aber ich seh grad mein Induktionsanfang is scho falsch

---

A(n)=Mit einem einzigen Gewichtssatz der Form {2^0kg, 2^1kg,..., 2^(n-1)kg} kann man alle Gewichte 1kg, 2kg, 3kg,...,2ⁿ -1kg zusammenstellen.

A(1) wäre dann :Mit einem einzigen Gewichtssatz der Form {1kg} kann man alle Gewichte 1kg zusammenstellen.  Das sit wohl wahr.

Angenommen für ein n gilt A(n) .

Dann ist zu zeigen:  Mit einem einzigen Gewichtssatz der Form {2^0kg, 2^1kg,..., 2^(n-1)kg, 2^nkg} kann man alle Gewichte

1kg, 2kg, 3kg,...,2^(n -1)kg , 2ⁿ kg zusammenstellen.

Dann wird auch vielleicht der Rest des Beweises klarer.

---

Ok danke mir is ds ganze jz schon klarer.

Ds bedeutet wenn ich g<2ⁿ habe, dann bedeuted das so viel wie, ich will ein Gewicht mit dem Satz darstellen, was aber kleiner ist als 2ⁿ und deswegen benötige ich das 2ⁿ Gewicht gar nicht.

Bei Fall 2 da blick ich mich noch immer nd ganz durch, weil mein Gewichtssatz is ja gegeben bis 2^(n-1) und das Gewicht mit 2ⁿ -1. Ich versteh hier einfach nicht wieso der Rest dann weniger ist als 2ⁿ

Oder ich weiß jetzt nicht mehr bezieht sich das g jetzt auf den Gewichtssatz oder das Gewicht selbst :-/

---

Das g ist das Gewicht, was du darstellen sollst.

Wenn das größer oder gleich 2ⁿ ist, dann brauchst du ja jedenfalls das 2ⁿ - Gewichtsstück.

Und mit den anderen Gewichtsstücken musst du nur noch

den Rest, also  g - 2ⁿ darstellen. Und weil das g kleiner ist als 2ⁿ

klappt das laut Induktionsannahme.

---

So ist es schon klar, ich glaube ich häng einfach an dem +1.

Weil wenn man ja jetzt bei beiden n -> n+1 macht, dann habe ich bei den Gewichtssätzen {2⁰,...,2^^n-1+1=2ⁿ) und bei den Gewichten {1,...,2⁽ⁿ⁺¹⁾-1} und so sind die Gewichte ja mehr, deshalb versteh ich nd wie ma ds darstellen kann. So wie du es oben hast versteh ichs schon aber nicht wieso da 2ⁿ hinter beiden steht.

---

Bei den Gewichten, die du darstellen willst,

geht es ja - wie du richtig sagst - von 1 bis 2^(n+1)-1.

Und 2ⁿ liegt dabei so ungefähr in der Mitte.

Die erste Hälfte ( bis 2ⁿ - 1) kannst du ohne das

2ⁿ -Gewichtsstück darstellen.

Deshalb ist der 1. Fall g < 2ⁿ .

---

Ja genau, das versteh ich nun schon, aber wenn g>= 2ⁿ ist, dann gibt es ja nur Gewichtssätze bis 2ⁿ, aber wie kann man dann einen Gewichtssatz darstellen, der 2^(n+1)-1 ist? Oder funktioniert das, weil ich von dem 2ⁿ abziehe und dann erhalte ich weniger als 2ⁿ und das ist mit dem Rest der Gewichtssätze noch möglich darzustellen?

---

In deiner Formulierung

"dann gibt es ja nur Gewichtssätze bis 2n, aber wie kann man dann einen Gewichtssatz darstellen,..."

liegt schon ein gewisses Misverständnis.

Es müsste heißen

dann gibt es ja nur Gewichte bis 2ⁿ, aber wie kann man dann ein Gewicht darstellen, ...

Wenn du z.B Beispiel 6 kg Kartoffeln abwiegen willst

(Das hier mit dem darstellen gemeint.) , dann genügt dazu der Gewichtssatz

1 , 2, 4 ; denn du nimmst die beiden Gewichte 2 und 4 und legst die auf eine

Seite der Waage und die Kartoffeln auf die andere.

---

Achsoo also wenn ich jz ein Gewicht darstellen will, dass größer als 2ⁿ ist, dann brauch ich einmal das 2ⁿ Gewicht und den Rest kann ich dann noch darstellen, da der Recht kleiner als 2ⁿ ist. Ich glaub jetzt hab ich kapiert, wie das gemeint ist. Mir war glaub ich die ganze Aufgabe nicht verständlich.

Danke für deine Hilfe

Answer 2

"Mit einem einzigen Gewichtssatz der Form {2^0kg, 2^1kg,..., 2^(n-1)kg} kann man alle Gewichte 1kg, 2kg, 3kg,...,2ⁿ -1kg zusammenstellen.

Beweise die Behauptung für alle n Element von N durch vollständige Induktion."

Wenn wir die Null noch als Gewicht hinzuziehen , können wir mit n wie oben beschriebenen sortierten Gewichten 2ⁿ verschiedene Gewichte zusammen stellen.

Das gilt es zu beweisen.

Induktionsanfang

Ein Gewichte 2^1-1kg damit kann ich zwei verschieden Gewichte zusammen stellen,

0 kg und 1 kg bis 2¹-1 = 2-1 = 1 kg kann ich also die Gewichte zusammen stellen.

Induktionsannahme

Mit n Gewichten kann ich 2ⁿ verschiedene Gewichte darstellen. Das entspricht den Zahlen von 0 bis 2ⁿ - 1.

Nun fügen wir ein Gewicht 2^(n+1)-1kg hinzu.

Die oben erwähnten 2ⁿ Gewichte können wir immer noch darstellen, doch nun können wir jeweils das neue Gewicht dazu legen oder weglassen, dadurch haben wir als doppelt soviel

$$2 *2^n =2^{(n+1)}$$

Möglichkeiten. D.h.wir können wie zu zeigen war, die Gewichte von

$$0 bis 2^{(n+1)}-1 kg$$ legen.

Induktionsschluss