Digits in a circle

Suppose we place K 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. 7. What's the maximum possible value of K ? K?

For example, the diagram to the right illustrates a solution for K = 3. 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.

3 4 5 6 7

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

Stephen Mellor
Jan 29, 2018

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. 12489 ( 1 ) 12489(1) which satisfies so the answer is 5 \boxed{5} .

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

Bhimsen Padalkar - 3 years, 4 months ago

Log in to reply

"Each pair of adjacent digits read clockwise or anti-clockwise direction", so the last pair can be read as 91.

Pranav Rao - 3 years, 4 months ago

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.

Christian Mann - 3 years, 3 months ago

91 91 , not 19 19 . 12489 12489 indeed works. Also, he meant [ 0 , 7 ] [0,7] and [ 3 , 5 , 6 ] [3,5,6] are two distinct cycles, as can be seen by his graph.

Ivo Zerkov - 3 years, 4 months ago

I think so: the diagramm above is not oriented

Andrea Bortolussi - 3 years, 4 months ago

As other people have kindly pointed out, 91 = 7 × 13 91 = 7 \times 13 .

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

Stephen Mellor - 3 years, 4 months ago

What an elegant solution! Didn't thought about that :o

Bernard Peh - 3 years, 4 months ago

Log in to reply

Thank you!

Stephen Mellor - 3 years, 4 months ago

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

Jonas Steiner - 3 years, 4 months ago

Log in to reply

How is the longest closed path of length 3?

Stephen Mellor - 3 years, 4 months ago

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 ;)

Jonas Steiner - 3 years, 4 months ago

I have fixed up your graph to be easier to read.

Jason Dyer Staff - 3 years, 4 months ago

Log in to reply

Thank you, it was only made in Microsoft Paint beforehand!

Stephen Mellor - 3 years, 4 months ago

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. :-)

Danny Lade - 3 years, 4 months ago

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)

Stephen Mellor - 3 years, 4 months ago

Log in to reply

and then with k=5. The way he did it k=6 tho he wrote k=5

Mark Brown - 3 years, 4 months ago

I missed 84.

Muhammad Rasel Parvej - 3 years, 4 months ago

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-...

Steve Gualtieri - 3 years, 4 months ago

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.

Mark Brown - 3 years, 4 months ago

Log in to reply

No, they intended the numbers to be placed around the circle. Each digit has two adjacent digits.

Brian Egedy - 3 years, 1 month ago

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

Meneghin Mauro - 3 years, 4 months ago

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 :)

Steve Gualtieri - 3 years, 4 months ago

I used similar argument:

Write down multiples of 7 7 with less then three digits. They go: 07, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98. \text{07, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98.} It's easy to see that sequence 35, 56, 63 \text{35, 56, 63} is closed - we can not prolong it to get a new multiple. Sequence 07, 70, 77 \text{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) \text{2 1 9 4 8 (2)} Hence, maximum possible value of K K is 5 5 .

Uros Stojkovic - 3 years, 4 months ago

Log in to reply

I think you meant 49, 98 and not 48, 99!

A Former Brilliant Member - 3 years, 4 months ago

Log in to reply

Yes, thanks for correction.

Uros Stojkovic - 3 years, 4 months ago

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.

Mark Brown - 3 years, 4 months ago

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.

Stephen Mellor - 3 years, 4 months ago

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

Mark Brown - 3 years, 4 months ago

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")

Stephen Mellor - 3 years, 4 months ago

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 :) !

J.J. The Great - 3 years, 4 months ago

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.

Ken Gene Quah - 3 years, 4 months ago

Excellent visual representation of the process I went through in my head to solve this.

Thomas Sutcliffe - 3 years, 3 months ago

Log in to reply

Thank you!

Stephen Mellor - 3 years, 3 months ago

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.

Stephan E - 3 years, 2 months ago

Log in to reply

"Distinct digits" is in the question

Stephen Mellor - 3 years, 2 months ago

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.

Stephan E - 3 years, 2 months ago

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...

Stephen Mellor - 3 years, 2 months ago
Ruth Mckinlay
Feb 9, 2018

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.

Jerry Barrington - 3 years, 4 months ago
Bilal Baig
Feb 7, 2018

Matt Parker from Numberphile explains the graph solution very nicely. [This YouTube video] (https://www.youtube.com/watch?v=G1m7goLCJDY)

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...