Difference between revisions of "2021 USAMO Problems/Problem 4"

(Created page with "==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 differen...")
 
m (Problem)
 
(3 intermediate revisions by 2 users not shown)
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 divisor <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?
 

Latest revision as of 13:59, 3 March 2023

Problem

A finite set $S$ of positive integers has the property that, for each $s\in S$, and each positive integer divisor $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$.