SudokuSolver Forum

_________________
I have 81 brain cells left, I think.

Well, seems Glyn has also found the reasons. In case others are still puzzled, try to find the special property of 8549176320 (no, the next brainteaser is not it, nor my origin ).

Okay let me put up my next one ahead of schedule. I think the digit game is getting old so let's have a change of format:

The 6 golden measuring rods

The King once ordered the goldsmith to make 21 shafts of pure gold, all having lengths of integers in units. And then he asked the goldsmith to join them into 6 straight rods, each formed with a different number of shafts. He specially required that the 6 finished rods can only have marks at the joints between shafts, and no other marks. And most importantly, he demanded the goldsmith to join them in such a way that using the 6 rods as measuring tools, he could measure each length from 1 to 56 units, either with a whole rod or a section of a rod.

Can you help the goldsmith on how to join the shafts together into the 6 measuring rods?

Warning:
It's a very hard one, and one probably need a computer and some programming skills to find the answer. However, extra kudos to the ones who manage to tackle it manually.

_________________
ADYFNC HJPLI BVSM GgK Oa m

Matt

To avoid the problem being trivial I think one or both of these two conditions should be applied.

1) All original 21 shafts should have different lengths.
2) All 6 rods must be used for a measurement.
Could you clarify that?

Don't assume that I will be answering soon, as it is going to be a manual one for me this time.
Edit
On further reflection the query on condition 2) changes to :- Is one rod, or a combo of rods allowed for a measurement, all rods simultaneously makes it even more mind-blowing.

_________________
I have 81 brain cells left, I think.

This condition is unnecessary because if 2 shafts are of the same length then it's trivially impossible to make the 6 rods. Note rod-1 has 1 possible measurement, rod-2 has (1+2), rod-3 has (1+2+3)... So all together the 6 rods have a total of 56 possible measurements. So basically no section can be repeated.


Nope, each time only a single rod can be used to measure, either with its whole length or partial length (partitioned by the joint marks). No combo of rods is allowed.

Hope it clears up a bit.

_________________
ADYFNC HJPLI BVSM GgK Oa m

EDIT: Note added to avoid the confusion that this might be a new poser, this is related to Matt's Six Golden Measuring Rods poser.

On a stock-take at the palace the following was found:- 15 shafts of silver of integer length totalling 56 units.

The king being a superstitious man said:"Call for the wizard who advised my goldsmith that he make make a set of measuring rods for my two favourite sons".

Told he had left for Oz, they called his apprentice. The apprentice was not sure what to do, but observing what the wizard had done he offered to make 2 miniature sets for each son complying to the same rules, but pointing out there would be some pieces left over.

"Then make a spare set for my other son to same rules, he'll probably melt them down to waste on booze anyway".

Here's what the apprentice did, I hope the wizard would have approved.

The two favourite sons received different sets of rods (well we don't want them to get mixed up). Each set could measure all distances to length 10 and consisted of 6 shafts assembled into 3 rods.
Their sets were {{2,1,7}{4,5}{6}} and {{1,3,6}{2,5}{8}}.
The wastrel son received a set measuring to length 4 consisting of 3 shafts assembled into 2 rods.
His set was {{1,3}{2}}

The numbers highlighted in red might help in your quest, but only the wizard can confirm that. The ones in blue may interest the wizard, but are probably of little assistance here.

_________________
I have 81 brain cells left, I think.

_________________
ADYFNC HJPLI BVSM GgK Oa m

All apprentices trying to solve this probem may find help in this Excel spreadsheet.

For each rod you can join up to 6 shafts.
Vertically under each rod are the units listed it can measure.

Horizontal of Measure are all units all rods can measure sorted.
Every time you change a shaft are the lists of the units each rod can measure and Measure recalculated automatically.

When you have all the numbers 1 through 56 and have not used more than 21 shafts, you have solved the problem.

_________________
Quis custodiet ipsos custodes?

Normal: [D  Y-m-d,  G:i]     PM->email: [D, d M Y H:i:s]

I will have to give way to the programmers on this one.

I would suggest testing a program on the smaller cases first before embarking on the intensive one.

Here is a hopefully useful table:-
3 rods The longest rod is 10 units made of 3 shafts, 4 combos x 3 permutations = 12 possibles.
4 rods The longest rod is 20 units made of 4 shafts, 23 combos x 12 permutations = 276 possibles.
5 rods The longest rod is 35 units made of 5 shafts, 192 combos x 60 permutations = 11,520 possibles.
6 rods The longest rod is 56 units made of 6 shafts, 2172 combos x 360 permutations = 781,920 possibles.

Many possibles for each rod with have duplicated measurements which can be filtered out first. Only matching rods which avoid redundancy need be constructed. The rods are highly optimized there must be no duplication of measurement over all rods.

This is a brute force method. There may be a shortcut but with limited data I can't speculate what that is yet. Finding 2 solutions to the 3 rod case was a bit of a blow as it reduces the scope for predicting an optimum length for the next rod. I will try to investigate 4 rods to see if a pattern emerges.

_________________
I have 81 brain cells left, I think.

If I did not have far better and profitable things to do, I would have attempted to make a brute force algorithm.

Perhaps my lazy apprentice version helps? Now everything is nicely sorted and zeros are removed.

_________________
Quis custodiet ipsos custodes?

Normal: [D  Y-m-d,  G:i]     PM->email: [D, d M Y H:i:s]

Unless I;m mis-reading the problem, I think there are (at least) 5 solutions to the 3 rods adding up to 10

Rod(1) {10}
Rod(2) {7, 1}
Rod(3) {4, 2, 3}

Rod(1) {9}
Rod(2) {6, 4}
Rod(3) {5, 2, 1}

Rod(1) {8}
Rod(2) {5, 2}
Rod(3) {6, 3, 1}

Rod(1) {7}
Rod(2) {8, 2}
Rod(3) {5, 1, 3}

Rod(1) {6}
Rod(2) {5, 4}
Rod(3) {7, 1, 2}

which makes things even worse