Digits in a circle
Suppose we place K distinct digits around a circle such that each pair of adjacent digits (read either clockwise or counterclockwise) forms a number that's divisible by 7 . What's the maximum possible value of K ?
For example, the diagram to the right illustrates a solution for K = 3 . Note that 35, 56, and 63 are all multiples of 7.
Note : Not all pairs of digits need to be read in the same direction. Some pairs may be read clockwise and others may be read counterclockwise.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
I don't think 12489 is the right combination..
Formed pairs can be 98, 84, 42, 21 and finally 19.. And 19 is not divisible by 7..
Same goes for 07356
Log in to reply
"Each pair of adjacent digits read clockwise or anti-clockwise direction", so the last pair can be read as 91.
Log in to reply
When I read the problem, I thought you could read in either direction, just as long as you were consistent with the order throughout the entire circle.
9 1 , not 1 9 . 1 2 4 8 9 indeed works. Also, he meant [ 0 , 7 ] and [ 3 , 5 , 6 ] are two distinct cycles, as can be seen by his graph.
I think so: the diagramm above is not oriented
As other people have kindly pointed out, 9 1 = 7 × 1 3 .
Also, you will notice that when listing the subgraphs, there is a space, meaning that 0,7 and 3,5,6 are separate. Even if this was missed, you can see this from the graph
What an elegant solution! Didn't thought about that :o
I figured the same out about the longest graph being the one containing (1,2,4,8,9), but still the longest closed path is of length 3. for example 21->42->14 or 84->28->42 or 98->49->84
Log in to reply
How is the longest closed path of length 3?
Log in to reply
because in my understanding of the problem you cant go both ways in the graph. For example you could go from 4 to 1, forming 14 (in my version of the graph), but going from 1 to 4 would not create 14 but 41 instead. I do know now that "either clockwise or counterclockwise" does not necessarily mean you have to read ALL numbers on the edge in clockwise direction, or ALL numbers in counterclockwise direction. My bad ;)
I have fixed up your graph to be easier to read.
Log in to reply
Thank you, it was only made in Microsoft Paint beforehand!
I just played a little bit with all possible pairs dividable by 7 and backwards (eg 14,41 or 21,12) and found:
14,42,28,84,49,91 (K=5)
But I really like the graph-solution. :-)
Log in to reply
Thank you. (By the way, the problem specifies distinct digits, so your example could simply replace the 84,49 with a 98 and it would be a valid example)
Log in to reply
and then with k=5. The way he did it k=6 tho he wrote k=5
I missed 84.
I had also found 91-14-42-28-84-49 But it says "distinct digits" so I can't use twice the 4 nor the 8. Which makes sense, otherwise the answer would be infinite as using just any number of 7s would give me 77-77-77-77-...
Log in to reply
it is a poorly written problem. the author meant for the numbers to be placed inside a circle not around a circle.
Log in to reply
No, they intended the numbers to be placed around the circle. Each digit has two adjacent digits.
With your numbers if you write around the circle 9,1,4,2,8 (that are 5 distinct numbers), you can create 91-14-42-28-98 all divisible by 7
Log in to reply
my bad then. i was sure to have read "note that all pair of digits..." instead of "not all...", so to me that would have read 89 which is no multiple of 7 :)
I used similar argument:
Write down multiples of 7 with less then three digits. They go: 07, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98. It's easy to see that sequence 35, 56, 63 is closed - we can not prolong it to get a new multiple. Sequence 07, 70, 77 is also self-sufficient and moreover disobeys condition that digits must be distinct. Of remaining digits, we can make following cycle: 2 1 9 4 8 (2) Hence, maximum possible value of K is 5 .
Log in to reply
I think you meant 49, 98 and not 48, 99!
poorly written. "around a circle" implies on the edge of the circle NOT inside a circle regardless of how many may have supposed the authors desired interpretation correctly. the example given with 3-5-6 reinforces the interpretation being meant for around the edge of the circle.
Log in to reply
I don't understand your point. The author used the word "around" both in words and in their diagram. Also, I interpreted it as around.
Log in to reply
i don't understand your point. you are correct...the author used it is the diagram and in words. the diagram shows the digits on the edge of the circle so no digit has more than two adjacent digits. BUT the solution to get 5 involves "4" having 4 adjacent digits
Log in to reply
@Mark Brown – I agree that in my diagram, the 4 does have 4 possibilities to link to. However, all that matters is that the 2 adjacent digits around the circle satisfy. (I have also noticed that the title of the problem does say "in")
I totally did not understand the question. By "distinct digits", I thought that meant that you cannot use a particular number more than once. I thought it was asking that if you could put "distinct" (different) digits around the clock, how many digits does the largest number you can produce which is divisible by 7. So I started with the largest of the multiple choice possibilities: 7. I first tested 1234567 by dividing it by 7. When I saw that the answer had a decimal part of .7143, I multiplied that by 7 - recognizing a remainder of 5 - which tells me that I need to add 2 to the number which I tested. So then I did 1234567 + 2 = 1234569. Then, I decided that by 7, and BINGO! It was divisible by 7: in addition to all 7 digits being "distinct". This is why I chose 7 for my answer, regardless of how one is to place these digits around the clock. Why is it wrong?... As I said, I feel like I am not understanding the question. Thanks :) !
Log in to reply
The question says each pair of adjacent digits. Also there are plenty of 10 digit numbers with all digits distinct that are divisible by 7, eg. 9856314720.
Excellent visual representation of the process I went through in my head to solve this.
If they chain of digits on the circle is 421428498491 then the requirements are satisfied (aren't they?) for K=12. And this is more than 5.
Log in to reply
"Distinct digits" is in the question
Log in to reply
Sorry, I was misunderstanding the term "distinct". But it means "different" ("unterschiedlich") rather than "determined" ("bestimmt" in German). Thank you, I learned something new.
Log in to reply
@Stephan E – Yes it means different. Also, if they were not distinct, an infinite number of digits could be placed. For example 142142142...
Start by writing all the multiples of 7 that are 2 digits:
14 21 28 35 42 49 56 63 70 77 84 91 98
next, list the numbers in ascending order along with the digits they can be paired with:
1:- 4,2,9
2:- 1,8,4
3:- 5,6
4:- 1,2,8,9
5:- 3,6
6:- 3,5
7:- 0
8:- 2,4,9
9:- 1,4,8
Next, start making deductions.
7 can only be paired with 0 so cannot loop with other numbers. 3,5 and 6 can only be paired with each other so cannot be used in a loop larger than 3
This leaves numbers 1,2,4,8 & 9, which we can make into a loop (eg 4-1-2-8-9 then back round to 4) Therefore k cannot be larger than 5.
Nothing in the problem prevents 7 and 0 from being in a loop of size 2. They are simply adjacent to each other on both sides.
Matt Parker from Numberphile explains the graph solution very nicely. [This YouTube video] (https://www.youtube.com/watch?v=G1m7goLCJDY)
Look at the network below with all the possible digits as vertices and the possible 2 digit multiples of 7 that can be made, represented by edges.
It is clear that we have 3 unconnected subgraphs, 0,7 , 3,5,6 and 1,2,4,8,9. Therefore, the maximum is 5, since we cannot find a cycle which traverses multiple unconnected subgraphs. We can easily find a cycle using these digits e.g. 1 2 4 8 9 ( 1 ) which satisfies so the answer is 5 .