Combinatorial Nullstellenzatz is a great topic. You can combine it with Dwir's ideas and some other stuff where the key idea is to construct an impossible polynomial though there is no mention of any polynomial in the original problem setup. Let me know if you want more details (I've got to run now) :).