Finding Subgroups of Size N/2 in {1, 2,..., N} with Property m<=N-n

  • Context: Graduate 
  • Thread starter Thread starter al-mahed
  • Start date Start date
  • Tags Tags
    Property
Click For Summary

Discussion Overview

The discussion revolves around a mathematical problem concerning the existence of subgroups within the set {1, 2, ..., N} that satisfy specific properties related to their size and intersection with other sets. The focus is on exploring the conditions under which these properties hold, particularly in relation to a positive whole number n and the derived number m.

Discussion Character

  • Exploratory, Technical explanation, Debate/contested, Homework-related

Main Points Raised

  • One participant asserts the existence of a number N such that for any subgroup A with at least N/2 elements, there exists a number m satisfying m <= N - n and a condition on the intersection of A with another set.
  • Another participant suggests a simpler approach by considering the top half and bottom half of the set.
  • A different participant expresses interest in seeing a solution and mentions having encountered a proof but is uncertain about its correctness.
  • One participant notes that the problem is related to an olympic problem, implying a competitive or advanced nature of the question.

Areas of Agreement / Disagreement

Participants do not appear to reach a consensus on the validity of the proposed proof or the best approach to the problem. Multiple perspectives and methods are presented without resolution.

Contextual Notes

Some assumptions regarding the properties of subgroups and the definitions of terms like "top half" and "bottom half" are not explicitly stated, which may affect the clarity of the discussion.

Who May Find This Useful

Readers interested in combinatorial mathematics, group theory, or competitive problem-solving may find the discussion relevant.

al-mahed
Messages
262
Reaction score
0
Given a positive whole number n, \exists N with the following property: if A is a subgroup of {1,2,...,N} with at least N/2 elements, then there is a positive whole number m<= N - n such that

|A \cap{m+1, m+2,..., m+k}|>=k/2

\forall k = 1, 2, …, n.
 
Last edited:
Physics news on Phys.org
Just look at the top half and the bottom half.
 
Hi, I'll be glad if you put your solution here. I already saw a proof, but I don't know if it's correct.
 
this is an olympic problem, by the way
 

Similar threads

Undergrad Proving inequality about dimension of quotient vector spaces
  • · Replies 25 ·
Replies
25
Views
4K
Undergrad Dfns group action & group, written in terms of the other
  • · Replies 26 ·
Replies
26
Views
1K
Undergrad Fourier Transformation on a Ring
  • · Replies 11 ·
Replies
11
Views
3K
MHB Statements with linearly independent vectors
  • · Replies 10 ·
Replies
10
Views
2K
Undergrad Prove that elements of x^i 0<i<n-1 are distinct
  • · Replies 3 ·
Replies
3
Views
1K
Graduate Structure of modulo-integer matrix group GL(r,Z(n))?
  • · Replies 17 ·
Replies
17
Views
7K
Prove that ##5 | (2^n a) \rightarrow (5 | a)##for any ##n##
  • · Replies 10 ·
Replies
10
Views
3K
Graduate Why does the Lie group ##SO(N)## have ##n=\frac{N(N-1)}{2}## real parameters?
  • · Replies 3 ·
Replies
3
Views
3K
MHB Understanding Vectors: Properties and Applications
  • · Replies 4 ·
Replies
4
Views
2K
MHB How can we find all the normal subgroups?
  • · Replies 11 ·
Replies
11
Views
3K