A positive integer $n$ is known as an interesting number if $n$ satisfies \[{\ \{\frac{n}{10^k}} \} > \frac{n}{10^{10}} \] for all $k=1,2,\ldots 9$. Find the number of interesting numbers.
Problem
Source: China TST 2011 - Quiz 1 - D1 - P3
Tags: number theory proposed, number theory, combinatorics
math154
19.05.2011 20:02
It's easy to establish a bijection between interesting numbers (which must have at most $10$ digits) and aperiodic necklaces with $10$ beads of $10$ possible colors.
ZetaX
20.05.2011 01:30
What is $k$ supposed to do¿
math154
20.05.2011 03:21
$k$ ranges from $1$ to $9$.
ZetaX
20.05.2011 10:18
And that property is supposed to be true for all or for one¿
WakeUp
20.05.2011 13:40
For all, it's now been edited.
Amir Hossein
20.05.2011 14:21
Posted here (No solutions, though).
SCP
11.06.2011 10:41
math154 wrote: It's easy to establish a bijection between interesting numbers (which must have at most $10$ digits) and aperiodic necklaces with $10$ beads of $10$ possible colors. How do you do that? I can't understand and didn't see the solution. With max. $6$ digits there are $9*10^5-45$ numbers, but than we have already few numbers which can't work.
Yuriy Solovyov
14.06.2011 14:30
Answer: 999989991
#include <iostream>
const double pow10_10 = 1.0/10000000000.0;
const double pow10_x[9] = { 1./10, 1./100, 1./1000, 1./10000, 1./100000, 1./1000000, 1./10000000, 1./100000000.0, 1./1000000000 };
double frac(unsigned long long& n, int k)
{
double d = n * pow10_x[k];
return d - (unsigned long long)(d);
}
bool check(unsigned long long& n)
{
for (int k = 0; k < 9; ++k)
{
if (frac(n, k) <= n * pow10_10)
return false;
}
return true;
}
int main (int argc, const char * argv[])
{
long long total = 0;
unsigned long long last_n;
for (unsigned long long n = 1; n < 10000000000ULL; ++n)
{
if (check(n))
{
last_n = n;
++total;
}
if (n % 1000000 == 0)
std::cout << "n = " << n / 1000000 << "; total = " << total << std::endl;
}
std::cout << "--- FINAL ---" << std::endl;
std::cout << "last n = " << last_n << "; total = " << total << std::endl;
return 0;
}
SCP
18.06.2011 12:49
Yuriy Solovyov wrote: Answer: 999989991 Did anyone find without a computer program?
goodar2006
21.12.2011 06:37
it's obvious that no intresting number has more than $10$ digits. for a ten digit number $a_1a_2....a_{10}$ where some or all of $a_i$'s can be zero, define it's equivalence class to be all it's cyclic permutations, i.e numbers $a_2....a_{10}a_1$, $a_3...a_{10}a_1a_2$,...,$a_{10}a_1a_2....a_9$. each equivalence class has a minimum. if this minimum appeared once, then prove that minimum is the only intresting number in that class. but if that minimum appeared two times or more (this forces that number to have $2$ or $5$ or $10$ same blocks, like $1212121212$), then that equivalence class doesn't have any intresting numbers. hence the answer will be $\frac{1}{10}(10^{10}-10-(10^5-10)-(10^2-10))=10^9-10^4-9=999989991$.
Wolstenholme
07.04.2015 16:25
By looking at cyclic permutations of digits it's clear that the answer is equal to the number of aperiodic necklaces with ten beads colored in ten colors. Using the mobius inversion formula we easily find that answer is $ \frac{1}{10}\sum_{d \vert 10}10^d\mu\left(\frac{10}{d}\right) = 10^9 - 10^4 - 10 + 1 = \boxed{999989991}. $ Surprisingly simple for a China TST #3.
denery
18.01.2021 09:25
no i took two cases n>10^k,n<10^k and at last ended up in n<10^9