Solve Logic Problem Using Pigeonhole Principle

  • Context: Undergrad 
  • Thread starter Thread starter chem3
  • Start date Start date
Click For Summary

Discussion Overview

The discussion revolves around a logic problem that involves the pigeonhole principle and its application to integer numbers. Participants are exploring how to demonstrate that among n integer numbers, there are at least two whose difference is a multiple of n-1. The scope includes mathematical reasoning and problem-solving techniques.

Discussion Character

  • Exploratory
  • Mathematical reasoning
  • Homework-related

Main Points Raised

  • One participant presents a logic problem that requires showing the existence of two numbers among n integers whose difference is a multiple of n-1.
  • Another participant questions the number of pairs and the number of remainders when considering modulo n-1.
  • A different participant suggests that additional logic principles may be necessary alongside the pigeonhole principle to solve the problem.
  • One participant calculates the number of pairs that can be formed from n elements, arriving at the formula for combinations but expresses uncertainty at that point.
  • Another participant introduces the concept of modulo arithmetic, explaining the possible remainders when dividing by n-1 and hints at how to relate the differences of pairs to these remainders.

Areas of Agreement / Disagreement

Participants do not appear to reach a consensus on the solution approach, and multiple viewpoints regarding the necessary principles and calculations remain present.

Contextual Notes

There are unresolved mathematical steps and assumptions regarding the application of the pigeonhole principle and modulo arithmetic that have not been fully explored.

chem3
Messages
6
Reaction score
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
How many pairs are there? How many remainders mod n-1 are there?
 
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?
 
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:
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).
 

Similar threads

MHB Combinatorics - The pigeonhole principle
  • · Replies 2 ·
Replies
2
Views
2K
MHB How Can the Pigeonhole Principle Solve These Mathematical Puzzles?
  • · Replies 2 ·
Replies
2
Views
2K
MHB Understanding induction proof of pigeonhole principle
  • · Replies 4 ·
Replies
4
Views
4K
Graduate "The Operation Combination Problem"
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Pigeonhole Principle question
  • · Replies 6 ·
Replies
6
Views
11K
Undergrad Ways to put n balls in m boxes such that exactly k boxes are empty?
  • · Replies 29 ·
Replies
29
Views
6K
MHB Solve Pigeon Hole Theory Problems
  • · Replies 1 ·
Replies
1
Views
3K
Graduate Number of unequal integers with sum S
  • · Replies 12 ·
Replies
12
Views
2K
High School Traditional logic and its usefulness in the past
  • · Replies 21 ·
Replies
21
Views
3K
High School Solving a RNG Problem: What is the Expected Value of N?
  • · Replies 2 ·
Replies
2
Views
2K