| Yatir
Halevi |
A group of people went to see a picture exhibition of 200 pictures. None of the visitors saw all the pictures and there were no picture that was seen by none. Prove that there were a pair of visitors: A, B and a pair of pictures: a, b, such that A saw a but not b and that B saw b but not a. Enjoy, Yatir |
||
| Matthew
Buckley |
How about this: No-one saw every painting, but every painting was seen, thus there were at least 2 people in the group. Without loss of generality, we can assume that one of these people saw the most number of paintings out of the whole group (it may be 199, but it could be less - the main point is that this person saw the maximum out of the group.) Let A be the set of paintings seen by this person. We know someone else saw the other painting(s) that A didnt see. Call this set of paintings B. Now, it is obvious that A is the largest set possible, and that B is not completely contained by A, thus there exists regions A\B, B\A, and A n B. Now, there exists at least one painting in B\A (as A does not contain all the paintings,) but A contains more paintings than B, hence there exists a painting in A\B. Thus, if we let the sets A and B be two people in the group, we have the result that is required. Hopefully I haven't been silly - if someone could check my logic, I would be very grateful. Matt |
||
| Yatir
Halevi |
Exactly as I solved it! Yatir |
||
| Matthew
Buckley |
Yatir, If you have any other puzzles like that, then please post them - I think these are the most satisfying type of problem to solve, as it simply tests logical reasoning, and not the ability to remember huge formulae etc. Also, the maths used is very basic, and I think many people could follow the logic! Matt |
||
| Joel
Kammet |
I don't think that proves it. If P is the set of all paintings, A is a proper subset of P, and you define B=P-A, then {AÇB}={ Æ}, isn't it? I would start out similarly, and let X be the set of pictures seen by your visitor A (who saw the most pictures), and let Y be the set of pictures NOT seen by A,so Y=P-X. Since every picture was seen by at least one person, there must exist a visitor B, and a setZ of pictures seen by B such that there is at least one picture z Î (YÇZ). Now, either XÇZ is the nullset,or it's not. If XÇZ is null, we're finished. A and B and any picture in X and any picture in Z satisfy the required condition. If XÇZ is not null, since A is the biggest subset of P, there must be some x Î X\Z. Then A and B and that x Î X\Z and z Î Y\capZ satisfy the condition. (I'musing X\Z to represent ''X intersection Z-complement. Is that the usual format here? I don't see any way to put a bar over a letter.) |
||
| Angelina
Lai |
But B isn't defined as P-A. It's just another set which may overlap with A but definately contains P-A (if I wasn't mistaking). |
||
| Joel
Kammet |
He said B is "the other painting(s) that A didn't see". Isn't that P-A? Anyway, I don't like using A and B to be the paintings AND the people. Call me fussy. |
||
| Angelina
Lai |
Lol, actually, I think really you guys meant the same things. |
||
| P8125 |
More or less. |
||
| Brad
Rodgers |
Is there really a reason to resort to fairly abstruse logical operations? Call the visitor who saw the most pictures ''A''. There was at least one picture A didn't see - call this picture b. Some visitor, however, saw b - call him B. B did not see all the pictures A saw (and b), though; for if he did, he would have seen more pictures than A. So A saw some picture B didn't - call this picture a. QED This is effectively the same argument given above by others, but I personally don't find it as hard to follow. Then again, I wrote it, so maybe I'm biased...:-) Brad |
||
| P8125 |
I like that, Brad. Guess I was trying too hard to sound smart. Joel |
||
| Demetres
Christofides |
Yatir, why did you write the 200 in bold ? It could be any integer > = 2. Demetres |
||
| Marcos |
Red herring? |
||
| Yatir
Halevi |
I was in a happy and humoristic mood! Yatir |