Problem 1887. Graceful Graph: Wichmann Rulers

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This Challenge is to find maximum size Graceful Graphs via Wichmann Rulers for P&gt;13. This Challenge is related to the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.azspcs.net/Contest/GracefulGraphs\"><w:r><w:t>Graceful Graph Contest</w:t></w:r></w:hyperlink><w:r><w:t> which Rokicki completed in 97 minutes. The Wichmann Conjecture is that no larger solutions exist for P&gt;13.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>An Optimal ruler is defined as having end points at 0 and Max with P-2 integer points between [0,Max] such that the distances 1 thru Max exist by deltas between points. An</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://oeis.org/A193802\"><w:r><w:t>Optimal Wichmann Ruler</w:t></w:r></w:hyperlink><w:r><w:t> readily creates solutions that can be tested for number of points and existence of all expected deltas.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Wichmann difference vector is [Q(1,r), r+1, Q(2r+1,r), Q(4r+3,s), Q(2r+2,r+1), Q(1,r)] where Q(a,b) is b a's, e.g. Q(2,3) is [2 2 2]. The max value is L=4r(r+s+2)+3(s+1) for Points P=4r+s+3, (r and s &gt;=0 and integer).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For W(r,s), W(2,3) creates the difference sequence [1 1 3 5 5 11 11 11 6 6 6 1 1]. The points on the ruler are the cumsum of W with a zero pre-pended to produce S=[0 1 2 5 10 15 26 37 48 54 60 66 67 68], P=14. All deltas from 1 thru 68 can be realized.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> P (Number of Points on the ruler)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> S (Vector of length P of locations on the ruler, 0 thru Max Value and can generate all deltas 1:S(end))</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Notes:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[1) A W(r,s) does not guarantee all deltas can be generated\n2) For any P there are multiple W(r,s) solutions \n3) P=5 solution is 9, readily solved by brute force\n4) P=13 Wichmann is 57 but the best solution is 58. Too big for brute force\n5) Create Connectivity Graph for Cases, like Final Matlab Competition, for Fun]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This Challenge is to find maximum size Graceful Graphs via Wichmann Rulers for P>13. This Challenge is related to the <a href = "http://www.azspcs.net/Contest/GracefulGraphs">Graceful Graph Contest</a> which Rokicki completed in 97 minutes. The Wichmann Conjecture is that no larger solutions exist for P>13.An Optimal ruler is defined as having end points at 0 and Max with P-2 integer points between [0,Max] such that the distances 1 thru Max exist by deltas between points.
An <a href = "http://oeis.org/A193802">Optimal Wichmann Ruler</a> readily creates solutions that can be tested for number of points and existence of all expected deltas.The Wichmann difference vector is [Q(1,r), r+1, Q(2r+1,r), Q(4r+3,s), Q(2r+2,r+1), Q(1,r)] where Q(a,b) is b a's, e.g. Q(2,3) is [2 2 2]. The max value is L=4r(r+s+2)+3(s+1) for Points P=4r+s+3, (r and s >=0 and integer).For W(r,s), W(2,3) creates the difference sequence [1 1 3 5 5 11 11 11 6 6 6 1 1]. The points on the ruler are the cumsum of W with a zero pre-pended to produce S=[0 1 2 5 10 15 26 37 48 54 60 66 67 68], P=14. All deltas from 1 thru 68 can be realized.Input: P (Number of Points on the ruler)Output: S (Vector of length P of locations on the ruler, 0 thru Max Value and can generate all deltas 1:S(end))Notes:<pre class="language-matlab">1) A W(r,s) does not guarantee all deltas can be generated
2) For any P there are multiple W(r,s) solutions 
3) P=5 solution is 9, readily solved by brute force
4) P=13 Wichmann is 57 but the best solution is 58. Too big for brute force
5) Create Connectivity Graph for Cases, like Final Matlab Competition, for Fun 
</pre>

Solve

Solution Stats

22 Solutions
5 Solvers

Last Solution submitted on Jun 01, 2019

Last 200 Solutions

Problem Recent Solvers5

Problem Tags

difference sequence graphs oeis physics radio astronomy wichmann ruler

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1887. Graceful Graph: Wichmann Rulers

Solution Stats

Last 200 Solutions

Problem Recent Solvers5

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Problem 1887. Graceful Graph: Wichmann Rulers

Solution Stats

Last 200 Solutions

Problem Recent Solvers5

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Players