Andy's Math/CS page

Thursday, February 15, 2007

More Parity Puzzles

...because I'm odd that way. Both are in the same 'can-do' spirit of the last one, yet neither use quite the same techniques; still simple.
Guaranteed correct, 'cause they're not mine, but lifted from the problem sets I'll credit.

1. Two delegations A and B, with the same number of delegates, arrived at a conference. Some of the delegates knew each other already. Prove that there is a non-empty subset A' of A such that either each member in B knew an odd number of members from A', or each member of B knew an even number of members from A'.

2. Given a finite set X of positive integers and a subset A of X, there exists a subset B of X, such that A are precisely the elements of X that divide by an odd number of elements of B.

(Hint: not a number theory puzzle.)

First is from the 1996 Kurschak Competition (Hungarian), via the Kalva site (see sidebar). Second is from the book '102 Combinatorial Problems' by Andreescu and Feng. Enjoy!

Labels: ,