Number theory question I don’t understand at all

L

Levido

Junior Member
Joined
Dec 22, 2019
Messages
54
Hi, thanks for coming here to look at my problem. I’m going through a book and I’ve reached a problem I just don’t understand. At the moment I just need an explanation.

809ED27B-1AD5-4A0D-AE0F-1A5E43C70823.jpeg
I’m reading that n is an integer, then that we’re permitting it’s decimal digits, which an integer wouldn’t have. So I’m really stuck.

I do understand that n’ isn’t an integer so it could have decimal numbers.

thanks for your help ?
 
Levido said:
Hi, thanks for coming here to look at my problem. I’m going through a book and I’ve reached a problem I just don’t understand. At the moment I just need an explanation.

View attachment 33530
I’m reading that n is an integer, then that we’re permitting it’s decimal digits, which an integer wouldn’t have. So I’m really stuck.

I do understand that n’ isn’t an integer so it could have decimal numbers.

thanks for your help ?
Click to expand...
"Decimal" here means "base ten", not "fractional part". (Yes, it's unfortunate that the term is used with both meanings.) For example, the decimal digits of 12 are 1 and 2, whereas its binary digits are 1, 1, 0, and 0.

And the result of permuting the digits will be another integer.

For example, starting with 4839, if we permute it to 9843, the difference is 9843-4839 = 5004, which is a composite number.
 
Dr.Peterson said:
"Decimal" here means "base ten", not "fractional part". (Yes, it's unfortunate that the term is used with both meanings.) For example, the decimal digits of 12 are 1 and 2, whereas its binary digits are 1, 1, 0, and 0.

And the result of permuting the digits will be another integer.

For example, starting with 4839, if we permute it to 9843, the difference is 9843-4839 = 5004, which is a composite number.
Click to expand...
Thanks Dr Peterson ?

I could whinge that they could have said digits, but then it’s probably imprecise in some way. For example does decimal digits then exclude the infinite 0’s after the decimal point? Not sure, this feels like a question for a semantics forum rather than a maths one
 
Dr.Peterson said:
"Decimal" here means "base ten", not "fractional part". (Yes, it's unfortunate that the term is used with both meanings.) For example, the decimal digits of 12 are 1 and 2, whereas its binary digits are 1, 1, 0, and 0.

And the result of permuting the digits will be another integer.

For example, starting with 4839, if we permute it to 9843, the difference is 9843-4839 = 5004, which is a composite number.
Click to expand...
Isn't the question also failing to mention that the number of decimal of n must be greater than 1?

For example, for [imath]n \in \{1,2,...,9\}[/imath]. There's no permutation?
 
Levido said:
Thanks Dr Peterson ?

I could whinge that they could have said digits, but then it’s probably imprecise in some way. For example does decimal digits then exclude the infinite 0’s after the decimal point? Not sure, this feels like a question for a semantics forum rather than a maths one
Click to expand...
Since they are explicitly talking about integers, there's really only one way to interpret it that makes sense. But, yes, they could have said it differently.

AvgStudent said:
Isn't the question also failing to mention that the number of decimal of n must be greater than 1?

For example, for [imath]n \in \{1,2,...,9\}[/imath]. There's no permutation?
Click to expand...
No, there's only one permutation of such a number (namely, the number itself) ... and the difference will always be zero, which is ... hmmm, not exactly composite, is it? But it is divisible by anything.

Also, I don't think they really meant "integer", but probably positive integer. So, yes, it could be stated more clearly, apart from the fact that we are expected to interpret it in a way that makes sense.
 
I think there's another case we should consider where the integer includes 0.
For example, n=10, a permutation would 01.
Do we interpret 01 as 1?
 
It is a very badly worded problem. I suspect that they mean if n is a positive integer and m is a positive integer formed by any permutation of n's decimal digits, then |n - m| is a composite number.

Worded that way, the problem with one-digit numbers does not come up.

I have not tried to solve this, but the way I would likely start is to work on the case of two-digit numbers. First, it may help me see the mechanism that makes this proposition true. Second, it may provide the base for a proof by induction.

P.S. The case for two digits is truly simple. It is an old bookkeepers trick.
 
Last edited:
JeffM said:
It is a very badly worded problem. I suspect that they mean if n is a positive integer and m is a positive integer formed by any permutation of n's decimal digits, then |n - m| is a composite number.

Worded that way, the problem with one-digit numbers does not come up.

I have not tried to solve this, but the way I would likely start is to work on the case of two-digit numbers. First, it may help me see the mechanism that makes this proposition true. Second, it may provide the base for a proof by induction.

P.S. The case for two digits is truly simple. It is an old bookkeepers trick.
Click to expand...
proof by induction sounds promising, except while true for 10, it is not true for 11, or any number where all digits are the same for exactly the same reason with digits less than 10. Can you set up proof by induction but missing out certain cases? Am I being daft or can it not work

I’m curious, I think the number theory problem for 2 digits is simple, how did bookkeepers use it?
(I don’t know how to do spoilers, but labelling it as 9* something, assuming that’s the proof you’re talking about)
 
Last edited:
Levido said:
proof by induction sounds promising, except while true for 10, it is not true for 11, or any number where all digits are the same for exactly the same reason with digits less than 10. Can you set up proof by induction but missing out certain cases?

I’m curious, I think the number theory problem for 2 digits is simple, how did bookkeepers use it?
(I don’t know how to do spoilers, but labelling it as 9* something, assuming that’s the proof you’re talking about)
Click to expand...
So double entry bookkeeping is about finding errors. Everything is calculated two ways. So when you are done, totals should match. If they don't, divide the difference by 9. If it is an even number, you probably reversed two adjacent digits. It does not identify where the error is, but it tells you what kind of error is most probable.

As for your other question, that is addressable in a number of ways. Probably easiest is to say |n - m| is either composite or zero.

Upon reflection, the proof may be by infinite descent, which is sort of induction combined with contradiction.
 
Again, I have not worked this out, but here is a hint.

[math]\text {Given } j, \ n \text { are integers, } j \ge 1, \ 10^j \le n < 10^{(j+1)}, \text { and}\\ m \text { is an integer expressible by permuting the decimal digits of } n,\\ \text {Prove } m = n \text { or } |n - m| \text { is composite.}[/math]
Prove for j = 1. Then assume true if j = k. In the k + 1 case, what happens when we consider all the permutations that happen if we do not permute the high order digit. Then what?

Give it a try. It looks promising.
 
AvgStudent said:
I think there's another case we should consider where the integer includes 0.
For example, n=10, a permutation would 01.
Do we interpret 01 as 1?
Click to expand...
That's worth considering; did you consider it?

It turns out not to matter; 10 - 1 = 9, which is still composite. (But yes, 01 definitely means 1.)

If you found that that case didn't work, then you would want to reword the problem. (For instance, this wouldn't work in base 2, where 10 - 1 = 1, which is not composite!)

@Levido: By the way, the whole idea is simple if you know "casting out nines", but otherwise can be hard to talk about without using modular arithmetic. Since you call it number theory, perhaps you know both? What topics have been covered so far?

[This answer was delayed an hour while I was locked out of the site.]
 
Dr.Peterson said:
By the way, the whole idea is simple if you know "casting out nines", but otherwise can be hard to talk about without using modular arithmetic. Since you call it number theory, perhaps you know both? What topics have been covered so far?
Click to expand...
That was a good hint. I've managed to show it, but don't want to hijack the OP's thread. I'll leave the OP a hint:
Look at divisibility by 9
This takes care where n has 1 digit and the one where n includes 0's.
 
AvgStudent said:
Isn't the question also failing to mention that the number of decimal of n must be greater than 1?

For example, for [imath]n \in \{1,2,...,9\}[/imath]. There's no permutation?
Click to expand...
The arrangement that leaves the number the same IS a permutation and is called the identity permutation.
This means that one (and the only one) permutation of 9 is 9

If you permute the letters in cat there will be 3! or 6 permutations, one of which will be cat.

cat: act, atc, tac, tca, cat, cta
 
JeffM said:
It is a very badly worded problem. I suspect that they mean if n is a positive integer and m is a positive integer formed by any permutation of n's decimal digits, then |n - m| is a composite number.

Worded that way, the problem with one-digit numbers does not come up.

I have not tried to solve this, but the way I would likely start is to work on the case of two-digit numbers. First, it may help me see the mechanism that makes this proposition true. Second, it may provide the base for a proof by induction.

P.S. The case for two digits is truly simple. It is an old bookkeepers trick.
Click to expand...
Jeff,
Am I missing something or the way you worded the problem does allow n to be a digit?
Steven
 
Steven G said:
The arrangement that leaves the number the same IS a permutation and is called the identity permutation.
This means that one (and the only one) permutation of 9 is 9

If you permute the letters in cat there will be 3! or 6 permutations, one of which will be cat.

cat: act, atc, tac, tca, cat, cta
Click to expand...
That's how I saw it at first; but clearly they mean "another" permutation, since the difference 0 is not a composite. If we take it that way, then single digits are excluded. Another instance of poor wording.

@Levido, I located the problem in the book you must be reading:

www.google.com

The Mathematical Olympiad Handbook

Begun in Hungary in the nineteenth century, Mathematical Olympiads are now held for high school students throughout the world. They feature problems which, though they require only high school mathematics, seem very difficult because they are unpredictable and have no obvious starting point...
www.google.com

I see that a couple pages earlier it talked about some related examples; but it doesn't look like they've taught enough to do a genuine proof. I imagine they want just some explanation. I haven't read much of it, though.
 
Steven G said:
Jeff,
Am I missing something or the way you worded the problem does allow n to be a digit?
Steven
Click to expand...
Steven

No. But if you allow j to be zero, then it will address the one digit case. The reason that I worded it the way I did is because the one digit case is of no use for the inductive proof (the composite case does not arise with one digit). You need to go to the two digit case to get a base case useful for induction.
 
JeffM said:
@Dr.Peterson

So this definitely is not a homework problem?
Click to expand...
It could be (for an Olympiad prep class?); in any case, I'm still thinking of it as if it were, since someone who wants to participate in such contests needs to learn not to depend on other people ...
 
You must log in or register to reply here.
Top