answersLogoWhite

0


Best Answer

The easiest way might to answer that might be to show you an example.

Let's look at a Chess board with two of the diagonally opposite corners removed. Is it possible to cover the board with pieces of domino whose size is exactly two board squares?

The reason this is a pigeonhole problem is because the two diagonal square on a chess board

are the same color. So when you remove them you have 2 more square of one color than you do of the other.

So assume by contradiction that you can cover the board with pieces of domino whose size is exactly two board squares. Now every piece of domino must cover exactly two squares and these will be squares of different colors because adjacent square on the chess board are different colors. So for every domino piece I place, I set up a 1 to 1 correspondence between the set of one color square and the set of the other color squares. We now know the cardinality of the two sets is different since we removed those corners. So the pigeonhole principle tells us we can not have a 1 to 1 correspondence between two sets with different cardinalities. We conclude that it can't be done.

The idea in all cases where you want to use the pigeonhole principle and prove by contradiction is to assume it works and then let the pigeonhole principle prove it can't work.

User Avatar

Wiki User

14y ago
This answer is:
User Avatar

Add your answer:

Earn +20 pts
Q: How can you solve pigeonhole questions using contradiction?
Write your answer...
Submit
Still have questions?
magnify glass
imp
Related questions

How do you solve complicated trigonometry questions?

You make them less complicated by using trigonometric relationships and identities, and then solve the less complicated questions.


What is a style of proof of using contradiction?

bjjvbnkl


How do you solve unemployment problems by using 3 fundamental question of economics?

One possible way to solve unemployment problems is by using the 3 fundamental questions of economics. These are what to produce, how to produce it, and the cost of production.


What is a good website used to solve algebra questions using elimination?

x+y=2 x-4=4


How do you solve a standard normal distribution?

You do not solve a standard normal distribution. It is not a question nor an equation or inequality to be solved. You can answer questions using the standard normal distribution but what you do depends on the question and on what information is given.


How do you solve an or problem if a variable is unrestricted in sign?

Solve the problem using the + sign for the variable. Then solve the problem using the - sign for the variable. Report your answer as the answer that you got using + or the answer that you got using -.


When using a indirect proof you show that the negation of the desired conclusion leads to a contradiction?

True


Can you give me a sentence using solve?

We can solve the mystery.


How do you put contradiction in a sentence?

One way to create a contradiction in a sentence is to use two phrases or ideas that oppose each other. For example, "The ice cream was delicious, but it tasted terrible." This sentence sets up a contradiction by using contradictory descriptions for the ice cream's taste.


What symbol represents contradiction?

In Formal Logic proofs, the contradiction is represented with an inverted T (or upside-down T) as follows: ┴ The contradiction symbol can be introduced at any time a logical contradiction is encounterd, for example, all of the the following contradictory logical statements (using different symbols) can be replaced with the contradiction symbol: The ball is completely blue and the ball not completely blue. P ^ ¬P P & ~P P & !P P AND NOT P


How do you solve questions pertaining to buffer solutions in ionic equilibrium?

first wright the eqn then write their concentration at initial , used and then equilibrium. using the formula substitute the values given at equilibrium.


How do you solve math?

by using a calculator