Question

a puzzle we have to place 30 birds on 5 trees such that no tree is left vacant and number of birds on each tree is odd ??? our maths teacher asked this , ....

Answer 1

There is no solution to this problem.

To see this, let n be an odd number. Then there is another integer k such that n = 2k + 1. For example 5 = 2 x 2 + 1.

So suppose the five trees have
n1, n2, n3, n4 and n5 birds respectively.

Then write n1 = 2k1 + 1, n2 = 2k2 + 1, etc.

Then the total
n1 + n2 + n3 + n4 + n5 = 30

But also
n1 + n2 + n3 + n4 + n5 = 2(k1 + k2 + k3 + k4 + k5) + 5
= 2(k1 + k2 + k3 + k4 + k5 + 2) + 1

i.e., the sum is an odd number. But 30 is not odd. Contradiction!

Hence it is not possible that each tree have an odd number of birds.

Answer 2

@JAmesJ
Is that a proof by contradiction and induction, or just contradiction?

Answer 3

Proof by contradiction: we want to prove a statement A. Assume A is false and show that leads to a logical contradiction. Then it must be the case that A is true.

In this case, A is the statement:
"It is NOT possible to place 30 birds on 5 trees such that no tree is left vacant and number of birds on each tree is odd."

Answer 4

I saw it was at least by contradiction, but by representing odds as 2k+1... oh, I just realized I thought somehow you slipped a k+1 in there which is what made me think of induction. Never mind, thanks for clearing that up.