Solve Logic Problem Using Pigeonhole Principle

  • Thread starter chem3
  • Start date
In summary, the problem presented is to show that among n integer numbers, there are at least two numbers whose difference is a multiple of n-1. The question asks for the number of pairs and the number of remainders mod n-1. The total number of pairs is n(n-1)/2. The concept of modulo or clock arithmetic is introduced as a way to determine the remainder on division by n-1. The question also poses a hypothetical scenario and provides a hint for finding the remainder of z-y.
  • #1
chem3
6
0
Hello,

I have this logic problem which I know should be solved by the pigeonhole principle but I was not successful in solving it after many tries and I hope someone here would help me out.

The problem says:
n integer numbers are given. Show that there are at least two numbers among them whose difference is multiple of n-1.
 
Physics news on Phys.org
  • #2
How many pairs are there? How many remainders mod n-1 are there?
 
  • #3
matt grime said:
How many pairs are there? How many remainders mod n-1 are there?

That's all what the question said!
I think it may need some other logic principles used along with the pigeonhole principle to solve it?
 
  • #4
Ok from counting principles: The numbers of pairs you can choose from a group of n elements (order does not matter here) is:

(n // 2) i.e. n choose 2
and that's = n!/((n-2)!2!) = ... = n(n-1)/2

I got stuck right there!
 
Last edited:
  • #5
Have you met modulo, or clock, arithemetic? It is an important piece of mathematics, and one you were introduced to at the very start of your mathematics education: remainder arithmetic. Take one of those pairs. What is the remainder on division by n-1? It is one of 0,1,2,3,4,..,n-2 (e.g. after dividing by 8, you have remainder 0,1,2,3,4,5, or 7). Being divisible by n-1 means having remainder 0.

Suppose I tell you that x-y has remainder r on division by n-1, and that x-z has remainder s, what is the remainder of z-y? Hint z-y = (x-y)-(x-z).
 

1. What is the Pigeonhole Principle and how does it relate to logic problem solving?

The Pigeonhole Principle is a mathematical concept that states that if there are more pigeons than pigeonholes, at least one pigeonhole must contain more than one pigeon. In logic problem solving, this principle is used to help determine the number of possible outcomes or solutions by identifying the minimum number of pigeonholes (or categories) needed to contain all the pigeons (or possibilities).

2. Can you provide an example of how the Pigeonhole Principle is used in logic problem solving?

Sure! Let's say you have a logic problem with 10 clues and 7 categories. According to the Pigeonhole Principle, there must be at least 2 clues that share the same category. This can help narrow down the possibilities and make it easier to solve the problem.

3. Are there any limitations to using the Pigeonhole Principle in logic problem solving?

While the Pigeonhole Principle can be a useful tool in logic problem solving, it does have its limitations. It may not work for all types of logic problems, especially those with a large number of variables or complex clues. It is also important to note that the principle only guarantees the existence of a solution, not necessarily the uniqueness of the solution.

4. How can I apply the Pigeonhole Principle to improve my problem-solving skills?

Practice, practice, practice! The more you encounter and solve logic problems using the Pigeonhole Principle, the better you will become at identifying patterns and narrowing down possibilities. You can also try breaking down complex problems into smaller parts and applying the principle to each part individually.

5. Are there any other principles or strategies I should consider when solving logic problems?

Yes, there are many other principles and strategies that can be helpful in solving logic problems. Some common ones include the process of elimination, creating a table or chart to organize information, and looking for clues that can be used to make inferences. It's always a good idea to try different approaches and see what works best for you!

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
21
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
12
Views
912
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
970
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
935
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
412
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
2K
Back
Top