Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2021 USAMO Problems/Problem 4"
(Change to the actual Q4)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
The Planar National Park is a subset of the Euclidean plane consisting of several trails which meet at junctions. Every trail has its two endpoints at two different junctions whereas each junction is the endpoint of exactly three trails. Trails only intersect at junctions (in particular, trails only meet at endpoints). Finally, no trails begin and end at the same two junctions. (An example of one possible layout of the park is shown to the left below, in which there are six junctions and nine trails.)
+
A finite set <math>S</math> of positive integers has the property that, for each <math>s\in S</math>, and each positive integer <math>d</math> of <math>s</math>, there exists a unique element <math>t \in S</math> satisfying <math>\gcd(s,t)=d</math> (the elements <math>s</math> and <math>t</math> could be equal).
−
<center>
+
 
−
<img>https://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvZS9mLzc1YmNjN2YxMWZhZTNhMTVkZTQ4NWE1ZDIyMDNhN2I5NzY0NTBlLnBuZw==&rn=Z3JhcGguUE5H</img>
+
Given this information, find all possible values for the number of elements of <math>S</math>.
−
</center>
 
−
A visitor walks through the park as follows: she begins at a junction and starts walking along a trail. At the end of that first trail, she enters a junction and turns left. On the next junction she turns right, and so on, alternating left and right turns at each junction. She does this until she gets back to the junction where she started. What is the largest possible number of times she could have entered any junction during her walk, over all possible layouts of the park?
 

Revision as of 13:22, 15 September 2021

Problem

A finite set $S$ of positive integers has the property that, for each $s\in S$, and each positive integer $d$ of $s$, there exists a unique element $t \in S$ satisfying $\gcd(s,t)=d$ (the elements $s$ and $t$ could be equal).

Given this information, find all possible values for the number of elements of $S$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_USAMO_Problems/Problem_4&oldid=162298"