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 "2014 OIM Problems/Problem 6"
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
Given a set <math>X</math> and a function <math>f: X \to X</math>, we say that for each <math>x \in X</math>, <math>f^1(x)=f(x)</math>, and for each <math>j \ge 1</math>, <math>f^{j+1}=f(f^j(x))</math>.  We say that <math>a \in X</math> is a fixed point of <math>f</math> if <math>f(a) = a</math>. For each real number <math>x</math>, we define <math>\pi (x)</math> as the number of smaller positive primes less or equal to <math>x</math>. Given a positive integer <math>n</math>, we say that <math>f : {1, 2, \cdots , n} \to {1, 2, c\dots , n}</math>
+
Given a set <math>X</math> and a function <math>f: X \to X</math>, we say that for each <math>x \in X</math>, <math>f^1(x)=f(x)</math>, and for each <math>j \ge 1</math>, <math>f^{j+1}=f(f^j(x))</math>.  We say that <math>a \in X</math> is a fixed point of <math>f</math> if <math>f(a) = a</math>. For each real number <math>x</math>, we define <math>\pi (x)</math> as the number of smaller positive primes less or equal to <math>x</math>. Given a positive integer <math>n</math>, we say that <math>f : \left\{1, 2, \cdots , n\right\} \to \left\{1, 2, c\dots , n\right\}</math>
−
it's "''catracha''" if <math>f^{f(k)}(k)=k</math> for all <math>k \in {1,2,\cdots,n}</math>
+
it's "''catracha''" if <math>f^{f(k)}(k)=k</math> for all <math>k \in \left\{ 1,2,\cdots,n\right\}</math> Prove:
 +
 
 +
1. If <math>f</math> is ''catracha'', then <math>f</math> has at least <math>\pi (x)-\pi (\sqrt{x})+1</math> fixed points
 +
 
 +
2. If <math>n\ge36</math>, there exist a ''catracha'' function with exactly <math>\pi (x)-\pi (\sqrt{x})+1</math> fixed points
  
 
~translated into English by Tomas Diaz. ~orders@tomasdiaz.com
 
~translated into English by Tomas Diaz. ~orders@tomasdiaz.com
Line 10: Line 14:
 
== See also ==
 
== See also ==
 
[[OIM Problems and Solutions]]
 
[[OIM Problems and Solutions]]
 +
 +
== Side note ==
 +
"''Catracha''" is a fried tortilla, covered in fried beans and grated cheese, originating from Honduras.

Latest revision as of 14:23, 14 December 2023

Problem

Given a set $X$ and a function $f: X \to X$, we say that for each $x \in X$, $f^1(x)=f(x)$, and for each $j \ge 1$, $f^{j+1}=f(f^j(x))$. We say that $a \in X$ is a fixed point of $f$ if $f(a) = a$. For each real number $x$, we define $\pi (x)$ as the number of smaller positive primes less or equal to $x$. Given a positive integer $n$, we say that $f : \left\{1, 2, \cdots , n\right\} \to \left\{1, 2, c\dots , n\right\}$ it's "catracha" if $f^{f(k)}(k)=k$ for all $k \in \left\{ 1,2,\cdots,n\right\}$ Prove:

1. If $f$ is catracha, then $f$ has at least $\pi (x)-\pi (\sqrt{x})+1$ fixed points

2. If $n\ge36$, there exist a catracha function with exactly $\pi (x)-\pi (\sqrt{x})+1$ fixed points

~translated into English by Tomas Diaz. ~orders@tomasdiaz.com

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

See also

OIM Problems and Solutions

Side note

"Catracha" is a fried tortilla, covered in fried beans and grated cheese, originating from Honduras.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_OIM_Problems/Problem_6&oldid=207408"