MathDB

Good subsets

Source: Indian TST Day 2 Problem 3

June 20, 2011

number theorygreatest common divisorsearchcombinatorics unsolvedcombinatorics

Problem Statement

Let

T

be a non-empty finite subset of positive integers

\ge 1

. A subset

S

of

T

is called good if for every integer

t\in T

there exists an

s

in

S

such that

gcd(t,s) >1

. Let

A={(X,Y)\mid X\subseteq T,Y\subseteq T,gcd(x,y)=1 \text{for all} x\in X, y\in Y}

Prove that :

a)

If

X_0

is not good then the number of pairs

(X_0,Y)

in

A

is even.

b)

the number of good subsets of

T

is odd.

Back to Problems View on AoPS