A final attempt to make a combinatorics problem

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

A final attempt to make a combinatorics problem

G H J

Reveal topic tags

combinatorics proposed

combinatorics unsolved

L

G H BBookmark kLocked kLocked NReply

Source: At the time of posting the problem I do not know the source if any

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

124 posts

#1 h May 24, 2025, 5:27 AM

Y by

Let $N$ be a positive integer and consider the set $S = \{1, 2, \ldots, N\}$ .

Two players alternate moves. On each turn, the current player must select a nonempty subset $T \subseteq S$ of numbers not previously chosen such that for every distinct $x, y \in T$ , neither $x$ divides $y$ nor $y$ divides $x$ .

After selecting $T$ , all multiples of every element in $T$ , including those in $T$ itself, are removed from $S$ .

The game continues with the reduced set $S$ until no moves are possible.
Determine, for each $N$ , which player has a winning strategy if any

Note: It might be wrong or maybe too easy.

This post has been edited 1 time. Last edited by JARP091, May 24, 2025, 5:30 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

35 posts

#2 h May 24, 2025, 5:50 AM

Y by

How does a player win?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

124 posts

#3 h May 24, 2025, 6:23 AM

Y by

wimpykid wrote:

How does a player win?

Thanks for replying, a player wins if the other player can not make any move i.e. cannot select a set $T$ which satisfies the above condition

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

162 posts

#4 h May 24, 2025, 6:37 AM

Y by

why not first player select $T=\{1\}$ ?
then all the subset gone -> first player win

JARP091 wrote:

Let $N$ be a positive integer and consider the set $S = \{1, 2, \ldots, N\}$ .

Two players alternate moves. On each turn, the current player must select a nonempty subset $T \subseteq S$ of numbers not previously chosen such that for every distinct $x, y \in T$ , neither $x$ divides $y$ nor $y$ divides $x$ .

After selecting $T$ , all multiples of every element in $T$ , including those in $T$ itself, are removed from $S$ .

The game continues with the reduced set $S$ until no moves are possible.
Determine, for each $N$ , which player has a winning strategy if any

Note: It might be wrong or maybe too easy.

JARP091 wrote:

wimpykid wrote:

How does a player win?

Thanks for replying, a player wins if the other player can not make any move i.e. cannot select a set $T$ which satisfies the above condition

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

124 posts

#5 h May 24, 2025, 6:46 AM

Y by

ItzsleepyXD wrote:

why not first player select $T=\{1\}$ ?
then all the subset gone -> first player win

uff I might never be a problem proposer

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a